数据结构相关知识点总结-欢迎游览、点赞

大家好,我是20届阿里校招生,非常谢谢牛客给我这么好的平台,在这里,为了反补牛客,我整理一下如下数据库和数据结构与算法相关的面经,希望大家动动手指、加油点赞。
最后,贴一下我们部门的招聘群,欢迎加入。

1. 数据库结构与算法

1.1 几种重要的排序

快排
1:基本思想-选择一个基准元素,将比基准元素小的元素放在其前面,比基准元素大的 元素放在其后面,然后:再将小于其基准值元素的子数列和大于基准元素的子数列按原来的 方法排序。
2:优点-极快,数据移动少。缺点-不稳定(相同值的相对位置有发生改变)。
3:效率分析-此排序算法的效率在序列越乱的时候,效率越高。在数据有序时,会退化 成冒泡排序。
4:对于基准的选择-三数(low、mid、high)中取、随机选取基准。
5:优化方法-a.当待排序序列的长度分割到一定大小后,使用插入排序(对于很小和部 分有序的数组,快排不如插排好)。b.再一次分割结束后,可以把与 key 相等的元素聚集在 一起,继续下次分割时,不必再对于 key 相等的元素分割。
6:最坏的时候(O(n 2))也就是在随机快速排序的 partition 过程的时候每次选取标志 数的时候都大或者最小值。
堆排序
1:二叉堆定义-二叉堆是完全二叉树或近似完全二叉树。满足特性 a.父节点的键值总大 于或等于(小于或等于)任何一个子节点的键值。b.每个节点的左子树和右子树都是一个二 叉堆。
2:堆的存储-一般用数组来表示堆,i 结点的父节点下标是(i-1)/2,它的左右节点的下 标分别是 2*i+1 和 2*i+2。
3:应用-寻找 M 个数中前 k 个最小的数并保持有序。时间复杂度:O(K)[创建 K 个元素 最大堆的时间复杂度] +(M-K)*log(K)[对剩余 M-K 个数据进行比较并每次对最大堆进行 从新最大堆化]。
4:不稳定(相同值的相对位置有发生改变);
冒泡排序
1:基本原理在要排序的一组数中,对目前还未排好序的范围内的全部数,自上而下对 相邻的两个数依次进行比较,让较大的数往下沉,较小的往上冒。
2:优点:-稳定。缺点-慢。
直接插入排序
1:基本思想-将一个记录插入到已排序好的有序表中,从而得到一个新的,记录数增 1 的有序表。
2:优点-稳定,快。缺点-比较次数不一定,比较次数较少,插入后点的数据移动较多, 特别是数据量庞大的时候。
希尔排序
1:基本思想-先将整个待排序元素序列分割成若干个子序列分别进行直接插入排序,然 后依次缩减增量再进行排序,待整个序列中的元素基本有序时,在对全体元素进行一次直接 插入排序(因为直接插入排序在元素基本有序的情况下,效率很高)。
2:适用场景-比较在希尔排序中是最主要的操作,不是交换。用已知最好的步长序列的 希尔排序比直接插入排序要快,甚至在小数组中比快速排序和堆排序还快,但在涉及大量数 据是希尔排序还是不如快排。
简单选择排序(选择最大值位置下标)

1.2 优先队列

二叉堆:
最常用,最简单的堆实现,因为二叉堆是完全二叉树,所有可以使用顺序存储结构,也 就是说,数组来保存数据。二叉堆主要基于上滤与下滤操作来维持堆序(任意节点大与等于 或小于等于他的子节点)而完全二叉树基本是平衡树,所以这些操作都是 log2 N 的时间复 杂度,最后顺便一提,二叉堆可用于实现堆排序的算法。

1.3 胜者树和败者树

胜者树和败者树都是完全二叉树,是树形选择排序的一种变型。每个叶子结点相当于 一个选手,每个中间结点相当于一场比赛,每一层相当于一轮比赛。 不同的是,胜者树的中间结点记录的是胜者的标号;而败者树的中间结点记录的败者 的标号。 胜者树与败者树可以在 log(n)的时间内找到最值。任何一个叶子结点的值改变后,利 用根性中间结点的信息,还是能够快速地找到最值。在 k 路归并排序中经常用到。 详情见:https://blog.csdn.net/whz_zb/article/details/7425152

1.4 K 路归并

K 路归并排序作为经典的外部排序算法,,是程序员必须要掌握的。主要思想: 在 k 个 已排序的文件中, 选择第一个值, 采用败者树, 更新二叉树结构, 最终选择最优值。(胜者 树实现没想出来!!!)

1.5 B 树、B+树

B 树是为实现高效的磁盘存取而设计的多叉平衡搜索树。这个概念在文件系统,数据库 系统中非常重要。
B 树
1:基本原理
首先,简单说一下 B 树产生的原因。B 树是一种查找树,我们知道,这一类树(比如二 叉查找树,红黑树等等)最初生成的目的都是为了解决某种系统中,查找效率低的问题。B 树也是如此,它最初启发于二叉查找树,二叉查找树的特点是每个非叶节点都只有两个孩子 节点。然而这种做***导致当数据量非常大时,二叉查找树的深度过深,搜索算法自根节点 110 向下搜索时,需要访问的节点也就变的相当多。如果这些节点存储在外存储器中,每访问一 个节点,相当于就是进行了一次 I/O 操作,随着树高度的增加,频繁的 I/O 操作一定会降低 查询的效率。
这里有一个基本的概念,就是说我们从外存储器中读取信息的步骤,简单来分,大致 有两步:
1:找到存储这个数据所对应的磁盘页面,这个过程是机械化的过程,需要依靠磁臂的 转动,找到对应磁道,所以耗时长。
2:读取数据进内存,并实施运算,这是电子化的过程,相当快。
综上,对于外存储器的信息读取最大的时间消耗在于寻找磁盘页面(关键)。那么一个 基本的想法就是减少这种读取的次数,在一个磁盘页面上,多存储一些索引信息。B 树的基 本逻辑就是这个思路,它要改二叉为多叉,每个节点存储更多的指针信息,以降低 I/O 操作 数。
2:基本结构
B 树的定义:不同的资料在表述上有所差别。我在这里采用《算导》中的定义,用最小 度 t 来定义 B 树。一棵最小度为 t 的 B 树是满足如下四个条件的平衡多叉树: 1:每个节点最多包含 2t−1 个关键字;除根节点外的每个节点至少有 t−1 个关键字 (t≤2),根节点至少有一个关键字; 2:一个节点 u 中的关键字按非降序排列:u.key1≤u.key2≤…u.keyn ; 3:每个节点的 n 个关键字对其子树的范围分割,节点 u 有 n+1 个指针,指向其 n+1 棵 子树,指针为 u.p1,…u.pn 关键字 ki 为 u.pi 所指的子树中的关键字,有 k1≤u.key1≤k2≤u.key2… 成立;4:所有叶子节点具有相同的深度,即树的高度 h。这表明 B 树是平衡的。平衡性其实 正是 B 树名字的来源,B 表示的正是单词 Balanced。
3:搜索算法 一棵已经建立好的 B 树如下图所示,我们的目的是查找关键字为 29 的文件:
先简单对上图说明一下:
1:图中的小红方块表示对应关键字所代表的文件的存储位置,实际上可以看做是一个 地址,比如根节点中 17 旁边的小红块表示的就是关键字 17 所对应的文件在硬盘中的存储 地址;
2:P 是指针,不用多说了,需要注意的是:指针(指向子树),关键字,以及关键字所 代表的 data 域地址这三样东西合起来构成了 B 树的一个节点,这个节点存储在一个磁盘块 上。
下面,看看搜索关键字的 29 的文件的过程:
1:从根节点开始,读取根节点信息,根节点有 2 个关键字:17 和 35。因为 17 < 29 <35, 所以找到指针 P2 指向的子树,也就是磁盘块 3(1 次 I/0 操作)
2:读取当前节点信息,当前节点有 2 个关键字:26 和 30。26 < 29 < 30,找到指针 P2 指向的子树,也就是磁盘块 8(2 次 I/0 操作)
3:读取当前节点信息,当前节点有 2 个关键字:28 和 29。找到了!(3 次 I/0 操作)
由上面的过程可见,同样的操作,如果使用平衡二叉树,那么需要至少 4 次 I/O 操作, B 树比之二叉树的这种优势,还会随着节点数的增加而增加。另外,因为 B 树节点中的关键 字都是排序好的,所以,在节点中的信息被读入内存之后,可以采用二分查找这种快速的查 找方式,更进一步减少了读入内存之后的计算时间,由此更能说明对于外存数据结构来说, I/O 次数是其查找信息中最大的时间消耗,而我们要做的所有努力就是尽量在搜索过程中减 112 少 I/O 操作的次数。
4:B 树中插入关键字 向 B 树种插入关键字的过程与向二叉查找树中插入关键字的过程类似,但是要稍微复 杂一点,因为根据上面 B 树的定义,我们可以看出,B 树每个节点中关键字的个数是有范围 要求的,同时,B 树是平衡的,所以,如果像二叉查找树那样,直接找到相关的叶子,插入 关键字,有可能会导致 B 树的结构发生变化而这种变化会使得 B 树不再是 B 树。
所以,我们这样来设计 B 树种对新关键字的插入:首先找到要插入的关键字应该插入 的叶子节点(为方便描述,设这个叶子节点为 u),如果 u 是满的(恰好有 2t-1 个关键字), 那么由于不能将一个关键字插入满的节点,我们需要对 u 按其当前排在中间关键字 u.keyt 进行分裂,分裂成两个节点 u1,u2 ;同时,作为分裂标准的关键字 u.keyt 会被上移到 u 的 父节点中,在 u.keyt 插入前,如果 u 的父节点未满,则直接插入即可;如果 u 的父节点已 满,则按照上面的方法对 u 的父节点分裂,这个过程如果一直不停止的话,最终会导致 B 树的根节点分裂,B 树的高度增加一层。

1.6 AVL 树

定义:AVL 树本质上是一颗二叉搜索树,但是它又具有以下特点:它是一棵空树或它的 左右两个子树的高度差的绝对值不超过 1,并且左右两个子树都是一棵平衡二叉树。在 AVL 树中任何节点的两个子树的高度最大差别为一,所以它也被称为平衡二叉树。 平衡因子(bf):结点的左子树的深度减去右子树的深度,那么显然-1<=bf<=1。 作用:减小各操作时间复杂度。

1.7 红黑树

红黑树与 AVL 树的比较: 1.AVL 树的时间复杂度虽然优于红黑树,但是对于现在的计算机,CPU 太快,可以忽 略性能差异 2.红黑树的插入删除比 AVL 树更便于控制操作 3.红黑树整体性能略优于 AVL 树(红黑树旋转情况少于 AVL 树)
红黑树的性质: 红黑树是一棵二叉搜索树,它在每个节点增加了一个存储位记录节点的颜色,可以是 RED,也可以是 BLACK;通过任意一条从根到叶子简单路径上颜色的约束,红黑树保证最 长路径不超过最短路径的二倍,因而近似平衡。
具体性质如下:(inportant) 1:每个节点颜色不是黑色,就是红色 2:根节点是黑色的 3:如果一个节点是红色,那么它的两个子节点就是黑色的(没有连续的红节点) 4:对于每个节点,从该节点到其后代叶节点的简单路径上,均包含相同数目的黑色节 点

#实习##面经##阿里云##数据库工程师#
全部评论

相关推荐

9 56 评论
分享
牛客网
牛客企业服务