概述

数据结构与算法

二叉树

其中每个结点都不能有多于两个子结点：

• 满二叉树：若设二叉树的高度为$h$，除第$h$层外，其它各层(1～h-1) 的结点数都达到最大个数，最后一层都是叶子结点，且叶子结点都是从左到右依次排布，结点总数为$2^n-1$
• 完全二叉树：所有叶子结点都在最后一层或倒数第二层，且最后一层的叶子结点在左边连续，倒数第二层的叶子结点在右边连续。和堆联系比较紧密
• 平衡二叉树：AVL树（区别于AVL算法），是一棵二叉排序树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，且左右两个子树都是一棵平衡二叉树。

满二叉树

完全二叉树

关于二叉树的一些基础算法题，可参考面试+算法之二叉树(Java)。

二叉搜索树

Binary Search Tree，BST，又称为二叉查找树、二叉排序树。

特点：任何一个结点的值都大于其左子树的所有结点的值，任何一个结点的值都小于其右子树的所有结点的值。

二叉搜索树平均时间复杂度可以认为是树的高度$O(h)$。理论上，二叉搜索树的查询、插入和删除操作的时间复杂度均为$O(logN)$。极端情况下，高度达到最大时，二叉搜索树退化成链表，此时查询、插入和删除元素，时间复杂度变成$O(N)$。

平衡二叉搜索树

为了解决极端情况下二叉搜索树退化成链表的问题，引入旋转操作维护树的平衡。

Balanced Binary Search Tree（BBST，平衡二叉搜索树），也叫Balanced Binary Tree（BBT，平衡二叉树），包括AVL树和红黑树。

定义：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。其时间复杂度为$O(logN)$；

平衡，Balance，即当结点数量固定时，左右子树的高度越接近，这棵二叉树越平衡，即高度越低。最理想的平衡就是完全二叉树/满二叉树，高度最小的二叉树。

遍历

二叉树的遍历有两种：按照结点遍历与层次遍历

结点遍历，一般递归实现：

• 前序遍历：遍历到一个结点后，即刻输出该结点的值，并继续遍历其左右子树(根左右)
• 中序遍历：遍历一个结点后，将其暂存，遍历完左子树后，再输出该结点的值，然后遍历右子树(左根右)
• 后序遍历：遍历到一个结点后，将其暂存，遍历完左右子树后，再输出该结点的值(左右根)。

层次遍历

• 深度优先遍历：实际上就是上面的前序、中序和后序遍历，也就是尽可能去遍历二叉树的深度。
• 广度优先遍历：实际上就是一层一层的遍历，按照层次输出二叉树的各个结点。

二叉堆

二叉堆是一棵完全二叉树或是近似完全二叉树，还满足堆的特性：父结点的键值总是保持固定的序关系于任何一个子结点的键值，且每个结点的左子树和右子树都是一个二叉堆。经常被用来构造优先队列(Priority Queue),当你需要找到队列中最高优先级或者最低优先级的元素时，使用堆结构可以帮助你快速的定位元素。

结构性质：堆是一棵被完全填满的二叉树，有可能的例外是在底层，底层上的元素从左到右填入。这样的树称为完全二叉树。

分类

• 最大堆：父结点的键值总是大于或等于任何一个子结点的键值
• 最小堆：父结点的键值总是小于或等于任何一个子结点的键值

二叉堆可以用数组实现也可以用链表实现，观察上述的完全二叉树可以发现，是比较有规律的，所以完全可以使用一个数组而不需要使用链。下面用数组来表示上图所对应的堆结。

对于数组中任意位置i的元素，其左儿子在位置2i上，右儿子在左儿子后的单元(2i+1)中，它的父亲则在位置[i/2上面]

红黑树

Red Black Tree，一种自平衡的二叉搜索树（Self Balancing Binary Search Tree），又叫平衡二叉B树（Symmetric Binary B-tree）。

定义：红黑树是一种含有红黑结点，并能自平衡的二叉查找树。插入，删除，查找的复杂度都是$O(logN)$

满足二叉搜索树的性质外，还要满足如下性质：

1. 每个结点要么是黑色，要么是红色
2. 根结点是黑色
3. 每个叶子结点（NIL）是黑色
4. 每个红色结点的两个子结点一定都是黑色
5. 任意一结点到每个叶子结点的路径都包含数量相同的黑结点
6. 从根结点到叶子结点的最长路径不多于最短路径的长度的两倍

左倾红黑树，即红色结点都是父结点的左子树
右倾红黑树，

平衡

维持平衡的三种操作：变色、左旋、右旋。

左旋指的是以某个结点作为支点（旋转结点），其右子结点变为旋转结点的父结点，右子结点的左子结点变为旋转结点的右子结点，左子结点保持不变。不考虑结点颜色，可以看到左旋只影响旋转结点和其右子树的结构，把右子树的结点往左子树移动。

右旋指的是以某个结点作为支点（旋转结点），其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左子结点，右子结点保持不变。不考虑结点颜色，可以看到右旋只影响旋转结点和其左子树的结构，把左子树的结点往右子树移动。

变色指的是结点的颜色由红变黑或由黑变红。

将左旋、右旋和变色结合起来，得到一套变换规则。
变色：如果当前结点的父结点和叔父结点是红色，那么：

• 把父结点和叔父结点变为黑色
• 把祖父结点变为红色
• 把指针定义到祖父结点

左旋：当前结点是右子树，且父结点是红色，叔父结点是黑色，对它的父结点左旋。

右旋：当前结点是左子树，且父结点是红色，叔父结点是黑色，那么：

• 把父结点变为黑色
• 把祖父结点变为红色
• 对祖父结点右旋

搜索

由于红黑树本来就是平衡二叉搜索树，并且搜索也不会破坏树的平衡，所以搜索算法也与平衡二叉搜索树一致：

具体步骤：

• 从根结点开始检索，把根结点设置为当前结点
• 若当前结点为空，返回nil
• 若当前结点不为空，比较当前结点Key与搜索Key的大小
• 若当前结点Key等于搜索Key，则该Key是搜索目标，返回当前结点
• 若当前结点Key大于搜索Key，把当前结点的左子结点设置为当前结点，重复步骤2
• 若当前结点Key小于搜索Key，把当前结点的右子结点设置为当前结点，重复步骤2

插入

删除

AA树

AA树是一种用于高效存储和检索有序数据的平衡树形结构，Arne Andersson教授于1993年在其论文Balanced Search Trees Made Simple中介绍，设计的目的是减少红黑树考虑的不同情况。AA树的查找，插入和删除等操作的时间复杂度都是$O(logN)$。

AA树是红黑树的一种变体，与红黑树不同，AA树上的红色结点只能作为右子结点。AA树模拟2-3树，从而极大地简化维护操作。红黑树的维护算法需要考虑七种不同的情况来正确平衡树。因为红色结点只能作为右子结点，AA树只需要考虑两种情况。

AVL树

不平衡的二叉树性能差，需要在插入、删除结点时保证其平衡，即减小树的高度，引入AVL树。AVL Tree，缩写取自G.M. Adelson-Velsky和E.M. Landis两位教授的名字。

AVL树，首先是一棵二叉搜索树，每个结点的左右子树的高度之差的绝对值最多为1。这个高度差就叫平衡因子，Balance Factor，某结点的左右子树的高度差；显然，叶子结点的平衡因子是0。

AVL树的特点：

1. 每个结点的平衡因子只可能是-1、0、1（如果绝对值超过1则是失衡）
2. 每个结点的左右子树高度差不超过1
3. 搜索、插入、删除等操作在平均和最坏情况下的时间复杂度都是$O(logN)$

如上图是一个AVL树。如下图，往这颗树里插入一个结点T：

从T往上找，它的父结点是U，U的两颗子树的高度差为1，满足AVL树的规则。再往上查找，父结点是S，S的两颗子树的高度差为1，满足AVL树的平衡规则。再往上，S的父结点是V，V的两颗子树的高度差为2，不满足规则。此时，需要一个自平衡的过程。

维持树的平衡的一种可能的旋转过程如下，其中红色结点表示旋转的轴，经过两次旋转，再次变成AVL树：

由此可总结出AVL树的缺点：

• 插入、删除元素时维持平衡比较复杂且代价高，树越大，写操作占比越高（操作无外乎读或写，写包括插入和删除），性能影响越大
• 需要存储每个结点的平衡因子，增加额外的内存消耗
• 结点数很多时，不够直观（还能接收）

因为这些缺点，大师们又提出各种经过优化的平衡树。

AVL算法

AVL树使用的算法，即树的自平衡旋转方式，目标是用尽量少的调整次数达到适度平衡。

多叉树

也叫多路树，用于搜索场景的树，叫做多路搜索树，简单分类：

• 普通多路搜索树
• 平衡多路搜索树

B树

磁盘IO操作的效率很低。当在大量数据存储中，查询时不能一下子将所有数据加载到内存中，只能逐一加载磁盘页，每个磁盘页对应树的结点。造成大量磁盘IO操作（最坏情况下为树的高度）。平衡二叉树由于树深度过大而造成磁盘IO读写过于频繁，进而导致效率低下。

为减少磁盘IO次数，必须降低树的深度：

• 每个结点存储多个元素
• 摒弃二叉树结构，采用多叉树

引出一个新的查找树结构：多路查找树，一颗平衡多路查找树，可使得数据的查找效率保证在$O(logN)$时间复杂度。

Balanced Tree，一种平衡的多路搜索（查找，排序）树，多用于文件系统、数据库的实现。有些资料也叫B-树（对应的英文是B-Tree），实际上是同一种数据结构。

B树的阶：所有结点的孩子结点的最大值。

一个$m$阶（$m\ge 2$）的B树特点如下：

• 所有叶子结点都在同一层级；
• 每一个结点最多有$m$个子结点；
• 如果根结点不是叶子结点，则它至少有两个子结点；
• 有$k$个子结点的非叶子结点拥有$k-1$个键；
• 每一个非叶子结点（除根结点）最少有$\lceil m/2\rceil$个子结点，也就是中间结点最少有$\lceil m/2\rceil$个子结点。

两个取整：

• Ceiling：向上取整，指的是取比自己大的最小整数，用数学符号$\lceil \rceil$表示；
• Floor：向下取整，指的是取比自己小的最大整数，用数学符号$\lfloor \rfloor$表示。

假设一个结点存储的元素个数为$x$，则如果这个结点是：

• 根结点：$1\le x\le m-1$
• 非根结点：$\lceil m/2\rceil -1\le x\le m-1$

如果有子结点，子结点个数为$y=x+1$，则如果这个结点是：

• 根结点：$2\le y\le m$
• 非根结点：$\lceil m/2\rceil \le y\le m$

m取值不同时：

• m=3，叶子结点个数$2\le y\le 3$，可称为$(2,3)$树、2-3树、3阶B树。
• m=4，叶子结点个数$2\le y\le 4$，可称为$(2,4)$树、2-3-4树、4阶B树。
• m=5，叶子结点个数$3\le y\le 5$，可称为$(3,5)$树、3-4-5树、5阶B树。

同样地，还有2-3-4-5-6树、3-4-5-6树，无穷无尽，统一都叫B树。

结论：

• B树和二叉搜索树，在逻辑上是等价的
• 多代结点合并，可以获得一个超级结点，且n代合并的超级结点，最多拥有$2^n$个子结点（至少是$2^n$阶B树）

应用场景：

1. B树主要用于文件系统及部分数据库索引，如MongoDB。而大部分关系数据库则使用B+树做索引，如MySQL；
2. 从查找效率考虑一般要求B树的阶数$m>=3$；
3. B树算法的执行时间主要由读、写磁盘的次数来决定，故一次I/O操作应读写尽可能多的信息。因此B-树的结点规模一般以一个磁盘页为单位。一个结点包含的关键字及其孩子个数取决于磁盘页的大小。

操作

B树的操作，无非查询、插入、删除三种。

查询

插入

删除

2-3树

2-3树，是指每个具有子结点的结点（内部结点，Internal Node），要么有2个子结点和1个数据元素，要么有3个子结点和2个数据元素的自平衡的树，所有叶子结点都具有相同的高度。即，2-3树的非叶子结点都具有两或三个分支。

空间复杂度为$O(N)$，搜索、插入、删除等操作的时间复杂度都是$O(logN)$。

2-3树把数据存储在叫做元素的单独单元中，元素组合成结点。有2结点和3结点两种。

2结点：包含1个元素和2个子结点

3结点：包含2个元素和3个子结点

2–3树和AA树是等距同构的，意味着它们是同一种数据结构。对于每个2–3树，都至少存在1种AA树和它的元素排列是相同的。2–3树是平衡树，意味着右边，左边，中间的子树的元素数量都是相同或接近的。

一棵树T为2–3树的三种情况：

• T为空：即T不包含任何结点；
• T为拥有数据元素a的2结点。若T的左子结点为L、右子结点为R，则：
  • L和R是等高的2–3树；
  • a大于L中的所有数据元素；
  • a小于等于R中的所有数据元素。
• T为拥有数据元素a和b的3结点，且$a<b$。若T的左子结点为L、中子结点为M、右子结点为R，则：
  • L、M、和R是等高的2–3树；
  • a大于L中的所有数据元素，且小于等于M中的所有数据元素；
  • b大于M中的所有数据元素，且小于等于R中的所有数据元素。

上面这颗树就是一个2-3树。此时，如果要插入一个元素K，它会先找到I J这个结点；插入元素K，形成临时结点I J K，不符合2-3树的规则。

不同于AVL树，不满足树的规则时，需要对树进行旋转，2-3树则需要进行分裂操作。

J往上移，F H这个结点变成F H J，也不符合2-3树的规则。继续上移H，根结点变为D H。同时，上移的过程中，子结点也要相应的分裂，过程大致如下：

图片来自于红黑树。

在上面自平衡的过程中，出现一种结点，它具有四个子结点和三个数据元素，即4结点。如果4结点允许存在，则引出另一种树：2-3-4树。

另外，B树的平衡过程叫分裂，相比于AVL树的旋转，更直观易懂，效率更高。

2-3-4树

与2-3树类似，多了一种4结点：包含3个元素和4个子结点。

2-3-4树是有序的：每个元素必须大于或等于它左边的和它的左子树中的任何其他元素。每个子结点因此成为由它的左和右元素界定的一个区间。

2-3-4树的空间复杂度为$O(N)$，搜索、插入、删除等操作的时间复杂度都是$O(logN)$。

2-3-4树在多数编程语言中实现起来相对困难，因为在树上的操作涉及大量特殊情况。红黑树实现起来更简单一些，可用它来替代。

2-3-4树是红黑树的一种等同，这意味着它们是等价的数据结构。对于每个2-3-4树，都存在着至少一个数据元素是相同次序的红黑树。在2-3-4树上的插入和删除操作也等价于在红黑树中的颜色翻转和旋转。这使得它成为理解红黑树背后逻辑的重要工具。

B+树

B+树是B树的变种，但不同资料（以及实现里）中B+树的定义各有不同，其差异在于结点中关键字个数和孩子结点个数。

B+树的特点：

• 每个结点中子结点的个数不能超过N，也不能小于$N/2$（不然会造成页分裂或页合并）
• 根结点的子结点个数可以不超过$m/2$
• m叉树只存储索引，并不真正存储数据，只有最后一行的叶子结点存储行数据
• 通过链表将叶子结点串联在一起，方便按区间查找

这种在叶结点存放一整行记录的索引被称为聚簇索引，其他的就称为非聚簇索引。

一个$m$阶的B+树具有如下几个特征：

• 有$k$个子树的中间结点包含有k个元素（B树中是$k-1$个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子结点；
• 所有的叶子结点中包含全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接；
• 所有的中间结点元素都同时存在于子结点，在子结点元素中是最大（或最小）元素

B+树通常有两个指针，一个指向根结点，另一个指向关键字最小的叶子结点。对于B+树进行查找有两种算法：一种是从最小关键字起顺序查找，另一种是从根结点开始，进行随机查找。

对比B树

和B树一样，类似于二叉查找树。起始于根结点，自顶向下遍历树，选择其分离值在要查找值的任意一边的子指针。在结点内部典型的使用是二分查找来确定这个位置。

区别：

1. B树必须用中序遍历的方法按序扫库，而B+树直接从叶子结点逐个扫一遍就完；
2. B+树支持区间查询(Range Query)，而B树不支持。数据库选用B+树的最主要原因；
3. B+树中间结点没有卫星数据（索引元素所指向的数据记录），只有索引，而B树每个结点中的每个关键字都有卫星数据；即，同样大小磁盘页可以容纳更多结点元素，数据量相同时，B+树更加矮胖，IO操作更少
4. 因卫星数据的不同，导致查询过程也不同；B树的查找只需找到匹配元素即可，最好情况下查找到根结点，最坏情况下查找到叶子结点，性能很不稳定；B+树每次必须查找到叶子结点，性能稳定
5. 在范围查询方面，B+树的优势更加明显
   B树的范围查找需要不断依赖中序遍历。首先二分查找到范围下限，再不断通过中序遍历，直到查找到范围的上限即可。整个过程比较耗时。B+树的范围查找则简单许多。首先通过二分查找，找到范围下限，然后通过叶子结点的链表顺序遍历，直至找到上限即可，整个过程更简单，效率也更高。

面试题

• 为啥索引常用B+树作为底层的数据结构？
• 除了B+树索引，还有什么索引？
• 为啥推荐自增ID作为主键，自建主键不行吗？
• 什么是页分裂，页合并？
• 怎么根据索引查找行记录？

B*树

B+树的变体，区别：

• 在B+树的非根和非叶子结点再增加指向兄弟的指针；
• B*树定义非叶子结点关键字个数至少为$(2/3)\ast M$，即块的最低使用率为2/3，优于B+树的1/2；
• 分裂
  • B+树的分裂：当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针；B+树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针；
  • B*树的分裂：当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变）；如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针；
• B*树分配新结点的概率比B+树要低，空间使用率更高；

最小生成树

Minimum Spanning Tree，MST，最小权重生成树，是一副连通加权无向图中一棵权值最小的生成树。

哈夫曼树

Huffman Tree，最优二叉树，是一种带权路径长度最短的二叉树。树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的路径长度是从树根到每一结点的路径长度之和，记为$WPL=(W1\ast L1+W2\ast L2+W3\ast L3+...+Wn\ast Ln)$，$N$个权值$Wi(i=1,2,...,n)$构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为$Li(i=1,2,...,n)$。可证明霍夫曼树的WPL是最小的。

哈夫曼编码就是哈夫曼树的应用。

决策树

Decision Tree，也叫判定树，是一个类似于流程图的树结构：其中，每个内部结点表示在一个属性上的测试，每个分支代表一个属性输出，而每个树叶结点代表类或类分布。树的最顶层是根结点。

构造决策树的过程叫做决策树算法，常用于机器学习中的分类。

优点：直观，便于理解，小规模数据集有效

缺点：

• 处理连续变量不好
• 类别较多时，错误增加的比较快

Trie树与Radix树

参考Trie树、Radix树。

LSM树

Log-Structured Merge-Tree。适用于写入密集型的数据库系统，如LevelDB和RocksDB。
优势：提供非常高的写入性能和批处理能力，支持对数据的压缩。
劣势：因为涉及多层查找和合并操作，读取性能不如其他数据结构。

后缀树

Suffix Tree，用于字符串搜索、生物信息学等领域。
优势：可以快速解决多种字符串相关的问题，如查找子字符串出现的位置、查找最长重复子字符串等。
劣势：空间占用较大，构建过程复杂且耗时。

R树

R-Tree，适用于空间数据库中索引多维空间数据，如地理信息系统(GIS, Geographic Information System)。
优势：支持多维范围查询和最邻近搜索，适合存储空间数据。
劣势：更新成本高，查询性能依赖于数据分布。

对比

图片来源：https://bytebytego.com/

参考

• 全面分析二叉树
• 红黑树
• 面试必知的红黑树
• 面试必知B+树
• 最小生成树
• 红黑树
• AA树