数据结构-B树与红黑树

本篇介绍B树（B-树），B+树和红黑树，参考自陈小玉，《趣学数据结构》。

1. B树

二叉搜索树可以将搜索效率提高到 $O(H)$，H 为树高，如果使其平衡，那么搜索效率可以进一步限制到 $O(log n)$，B树是一种在此基础上继续提高搜索效率的方法。

B树的思路是在每个节点不限于存储一个关键字，并保持它二叉搜索树的特性和平衡性，这样可以进一步降低树高，从而提高搜索效率。这样的一棵树就称为多路平衡搜索树，如下图所示。

1.1 定义

B树，也叫做B-树，多路平衡二叉树。一棵 m 阶的 B 树，或者为空树，或者满足如下性质

1. 每个节点最多有 m 棵子树；
2. 根节点至少有两颗子树；
3. 内部节点（除根和叶子之外的节点）至少有 $\ulcorner m/2 \urcorner$（向上取整）棵子树；
4. 终端节点（叶子）在同一层上，并且不带信息（空指针），通常称为失败节点；
5. 非终端节点的关键字个数比子树个数少1；

所以上面的图其实少了一层空指针叶子节点，一个完整的3阶B树例子如下图所示。根据定义，内部节点的子树个数为 2~3，所以每个节点可能有 1~2 个关键字，2~3棵子树，所有空指针叶子节点都在最后一层，该树又称为2-3树（因为子树个数范围为 2~3）。

B 树中所有叶子节点都在最后一层，所以是平衡的，B树同样遵循中序有序的特性，且每个节点可以有多个分支。

1.2 树高与性能

要知道B树的性能，就要知道它的树高，m阶B树的树高计算方法如下。

首先，根结点至少有两棵子树，那么第二层至少有2个节点，所有内部节点至少有 $\ulcorner m/2 \urcorner$（向上取整）棵子树，那么第三层至少有 $2\ulcorner m/2 \urcorner$ 个节点……依此类推，第 h+1 层至少有 $2\ulcorner m/2 \urcorner^{h-1}$ 个节点，也就是叶子节点的个数，注意这里叶子节点为查找失败的空指针

假设该树含有 n 个关键字，查找失败的可能性有 n+1 种（每个间隔），空指针叶子节点的含义就是查找失败，因此空指针叶子节点的数目应小于等于查找失败的可能性，公式表达和推导如下 $$ n+1 \ge 2\ulcorner m/2 \urcorner^{h-1} \ log_{\ulcorner m/2 \urcorner}{\frac{n+1}2} \ge h-1 \ h \le log_{\ulcorner m/2 \urcorner}{\frac{n+1}2} + 1 = O(log_mn) $$ 所以一棵含有 n 个关键字的 m 阶 B 树的最大高度为 $O(log_mn)$。对于对数函数来说，m 越大，越靠近 x 轴，所以值就越小，时间复杂度就越低。

1.3 查找

B树通常用于大规模数据的分级存储搜索，就是将内存的「高速度」和外存的「大容量」结合起来，从而提高搜索效率。其原理是这样的，当数据规模较大时，无法全部放入内存进行搜索，就需要频繁访问外存，因为外存的访问速度通常比内存要慢好几个数量级，搜索的效率就会大幅降低。

由于外存访问时，访问一个数据和访问一段连续存储的数据时间差别不大，B树将多个关键词包含在一个节点中，一次读入内存比多次访问不同的关键字就会节省很多时间。一个节点中的多个关键词同时读入内存后，再利用顺序或折半查找等方式进行搜索。

仍以下面这张图为例，查找数字80。

1. 首先将根结点65读入内存，与80比较，80>65，进入根结点的第二个子树；
2. 当前节点不是空指针叶子节点，将75和90一次读入内存，80>75，80<90，进入当前节点的第二个子树；
3. 当前节点仍不是空指针叶子节点，将80读入内存，80=80，查找成功。

注意，在任何时刻，通常只有当前节点在内存，其它节点都在外存，需要时才会调入内存。

B树的查找时间包括将节点从外存调入内存和在内存中当前节点进行查找两个过程，由于内存操作与外存访问时间差距比较大，我们可以只考虑外存访问操作，整个过程外存最多走一条根结点到叶子节点的路径，因此时间复杂度就是树高 $O(log_mn)$，其中 n 为关键字个数，m 为树的阶数。

1.4 插入

插入的前置操作是查找，如果查找成功，那么不进行插入，如果查找失败，则将关键字插入到失败节点的双亲节点中。例如，在上面的3阶B数种插入59，应该放在58和60中间。

这里要考虑到每个节点的关键字个数有个上限 m-1，插入关键字后如果仍满足该条件，插入成功，如果超过了该上限到了m，那么发生了上溢，需要采取一定的办法解除上溢，使整棵树重新满足 m 阶B树的条件。

解除上溢的操作叫做分裂，即取当前节点中间的关键字 $k_s, s=m/2$，将其上升到父节点 P，左右两部分作为 $k_s$ 的左右孩子，如下图

如果分裂操作导致父节点同样产生了上溢，则继续分裂操作向上，最远会到达树根，如果树根也发生上溢，那么将树根分裂，根结点的中间关键字分裂成新的树根，此时树的高度加1。

插入操作除了查找插入位置需要 $O(log_mn)$ 时间，如果发生上溢，分裂操作的个数不会超过树高，因此最终的插入操作时间复杂度为 $O(log_mn)$

1.5 删除

删除操作相似，如果找不到，不进行删除，如果找到了，接下来的操作与二叉搜索树类似。

1. 如果待删除关键字的子树非空，则使用左子树的最大值（直接前驱）或右子树的最小值（直接后继）代替；
2. 如果待删除关键字子树为空，直接删除关键字即可。

与插入相反，删除操作可能出现的问题叫做下溢，因为内部节点至少应有 $\ulcorner m/2 \urcorner - 1$ 个关键字，下溢的处理方法有三种：左借，右借和合并。

首先，如果下溢节点 V 的左兄弟至少包含 $\ulcorner m/2 \urcorner$ 个关键字，少一个也可以维持条件，因此可以借出，借出的方法是，上溢节点向父节点拿一个关键字，然后父节点再向 V 的左兄弟拿一个关键字。如下图

如果 V 的左兄弟关键字不足 $\ulcorner m/2 \urcorner$ 个，无法借出，而右兄弟关键字的个数足够，则从右兄弟借，方法相似，先向父节点拿一个关键字，然后父节点从右兄弟拿一个关键字。

最麻烦的情况是左右兄弟关键字的个数都不够，这时候要做的事情是将父节点的一个关键字下移，然后和左兄弟、当前节点合并，组成新节点，然后删除多余指针，如果左兄弟不存在，就和右兄弟合并。

合并后父节点少了一个关键字，如果不再满足条件，同样用上面的三种方法分情况处理，最远也会到达根，如果根结点也发生下溢，最终会使树高减一。

删除操作的时间复杂度为 $O(log_mn)$

2. B+树

B+树是B树的变种，一般用于索引系统。

2.1 定义

B+树的定义如下，一棵m阶B+树，或者为空树，或者满足如下条件

1. 每个节点最多有 m 棵子树；
2. 根节点至少有两颗子树；
3. 内部节点（除根和叶子之外的节点）至少有 $\ulcorner m/2 \urcorner$（向上取整）棵子树；
4. 终端节点（叶子）在同一层上，并且不带信息（空指针），通常称为失败节点；
5. 非终端节点的关键字个数与子树个数相同；
6. 倒数第二层节点包含了全部的关键字，节点内部有序且节点间按升序顺序链接；
7. 所有非终端节点只作为索引部分，节点仅含子树中的最大（或最小）关键字；

B+树定义的不同之处在于最后3条，一棵 m 阶的B+树，根结点至少有两个关键字，其它非终端节点关键字个数范围为 $[\ulcorner m/2 \urcorner，m]$ ，关键字个数等于子树个数，而B树关键字个数比子树少一个。

例如，一棵3阶B+树，其内部节点的子树个数2≤k≤3，关键字个数也是2≤n≤3，如下图所示。一般有两个指针，一个指向树根，一个指向倒数第二层关键字最小的节点。

2.2 查找

B+树支持两种方式的查找，可以利用 t 指针从树根向下索引查找，也可以利用 r 指针从最小关键字向后顺序查找。尽管如此，仍不建议顺序查找，因为其时间复杂度为 O(n)，而索引查找效率要高得多。

若从树根向下查找，则首先在根节点中查找，然后在子树中查找，即使查找成功，也会继续向下，直到最后一层。也就是说，每次查找都要走一条从树根到叶子的路径，时间复杂度为树高$O(log_mn)$。

例如，在一棵3阶B+树中查找70，首先和65比较，70>65；再和98比较，70<98，到98的左分支查找；和70比较，相等，继续到70的左分支查找；和68比较，70>68，继续比较，找到70，查找成功，如下图

B+树不仅支持单个关键字查找，还支持范围查找。例如，查找范围在[a, b]之间的关键字，首先查找a所在的位置，从根到最后一层，查找等于或大于a的关键字。如果找到，则继续在a所在的节点查找；如果未发现大于b的关键字，就可以沿着该节点的最后一个指针查找下一个节点，直到找到一个等于或大于b的关键字停止。

例如，在一棵3阶B+树中查找[60, 80]之间的关键字，首先查找60所在的位置，从根到最后一层，查找等于或大于60的关键字，未找到60，则找到比它大的关键字65；继续在该节点查找，在下下个节点找到了等于80的关键字，查找成功，如下图

可以看到，范围查找是直接在叶子间进行移动的，这是因为所有叶子节点之间有连接，所以事实上，B+树已经不属于树的范围了。

2.3 插入

m阶B+树仅在最后一层节点插入，因为除了最后一层节点，其他非终端节点都表示索引。又因为m阶B+树的关键字个数要求不超过m，如果插入后节点的关键字个数超过m，则发生上溢，需要分裂操作。只不过分裂时，和B-树的分裂不同，上升到父节点的关键字，子节点中仍然保留。

刚刚发生上溢的节点V，插入之前满足条件（关键字个数小于等于m），插入之后大于m，因此V节点现在恰好有m+1个关键字。将该关键字进行分裂操作：取V节点中间的关键字ks（s=m+1/2），将ks上升到其父节点P，左右两部分作为ks的左右孩子，如下图

中间关键字上升到父节点后，需要检查父节点是否发生上溢，如果发生上溢，则继续分裂，一直向上传递，最远到达树根。如果根节点发生上溢，则需要做以下特殊处理。

树根分裂操作需要分裂的两个子节点的最大关键字一起上升，生成一个新的节点作为新树根，此时树高增1，如下图

2.4 删除

m阶B+树的删除只在最后一层进行，首先通过查找确定待删除关键字的位置，删除之，然后判断该节点是否发生下溢，还要判断是否需要更新父节点的关键字。如果关键字个数小于$\ulcorner m/2 \urcorner$，则发生下溢。如果发生下溢，则需要像B-树那样左借、右借或合并以解除下溢。解除下溢时要特别注意父节点中的最大关键字更新。

含有n个关键字的m阶B+树，查找、插入和删除操作的时间复杂度均为树的高度$O(log_mn)$。

3. 红黑树

AVL 树可以保证在最坏情况下，查找、插入、删除的时间复杂度均为 $O(logn)$，但插入和删除后重新调整平衡可能需要多达 $O(logn)$ 次旋转。红黑树通过放宽平衡条件：左右子树高度差不超过两倍，使任何不平衡都可以在3次旋转以内解决，因此红黑树被广泛应用。

3.1 定义

红黑树（red-black tree）是满足如下性质的二叉搜索树。

1. 每个节点是红色或黑色的；
2. 根结点是黑色的；
3. 每个叶子节点是黑色的（红黑树的叶子节点仍然指的是空指针叶子节点）；
4. 如果一个节点为红色，则其孩子节点必为黑色；
5. 从任一节点到其后代叶子的路径上，均包含相同数目的黑节点。

一棵红黑树示例如下

由于最后两条性质，从任一节点到叶子的路径上，可能都是黑节点，也可能黑节点和红节点交替出现，这就导致了对于任何一个节点，其左右子树的高度差不超过两倍。所以红黑树不是严格的平衡树，这里的平衡条件被放宽了。

从某个节点 x （不包含该节点）到叶子的任意一条路径上黑色节点的个数称为该节点的黑高，红黑树的黑高就是根结点的黑高，如上图，该红黑树的黑高为2。

3.2 树高与性能

红黑树放宽了平衡条件，但是查找、插入、删除的复杂度仍然是 $O(logn)$，证明如下：

假设n个节点的红黑树高度为 h，根到叶子节点至少一半是黑色节点，其黑高为 h/2，一个黑高为 h/2 的二叉树节点数为 $2^{h/2}-1$，剩下的 $n-(2^{h/2}-1)$ 个节点分布在后面 h/2 高的树内，由此得到不等式 $$ n - (2^{h/2}-1) >=0 $$ 推导得到 $n+1 \ge 2^{h/2}$，两边取对数就可以得到 $h \le 2log(n+1) = O(logn)$。查找、插入、删除的速度与树高成正比，因此红黑树的这三个操作时间复杂度还是 $O(logn)$。

3.3 查找

红黑树本身是「适度平衡」的二叉搜索树，其查找和二叉搜索树的查找一样。

3.4 插入

在红黑树中插入 x，首先进行查找，查找成功什么都不做，查找失败在失败位置创建 x 节点，置为红色（如果是树根，则置为黑色）。

如果插入的节点置黑色，可能改变黑高，从而违反最后一条性质，置红色不会，不过可能违反第4条性质（红节点必然有黑孩子）。

将插入分为两种情况

1. 新插入节点 x 的父亲为黑色，满足条件，插入成功；
2. 新插入节点 x 的父亲为红色，出现两个连续的红色，需要调整；

调整的方法是将 x 的父亲和祖父记为 p（parent）、g（grandpa），x 的叔叔记为 u（uncle），红黑树插入节点后调整分两种情况：u 为黑色和u 为红色，下面分别讨论

u 为黑色，如果 g 到 x 的路径为 LL，执行LL型旋转。如下图，将 g 右旋，然后将旋转后的根染黑，两个孩子染红。

而如果 g 到 x 的路径为 LR，执行 LR型旋转。如下图，先将 x 左旋，再将 g 右旋，然后将旋转后的根染黑，其两个孩子染红。

还有两种情况是 RR型和RL型，相似，不再赘述。

u 为红色，可以简单粗暴的将父亲和叔叔染黑，将祖父染红（保持黑高不变，如果祖父为树根，染黑），因为 g 的父亲有可能是红色，将 g 看作新插入的节点，采用同样的方法处理，每处理一次，上升两层，直到树根。

插入的几种方法总结如下

3.5 删除

在红黑树中删除x，首先通过查找，如果查找失败，什么也不做，直接返回。如果查找成功，则需要判断后处理：如果x节点仅有左子树（或右子树），则删除x节点，令其左子树（或右子树）子承父业代替其位置。如果x节点有左子树和右子树，则令x的直接前驱（或直接后继）代替其位置，然后删除其直接前驱（或直接后继）即可。在删除节点的过程中，有可能违反红黑树的性质2、4、5，即根为黑色，红节点必有黑孩子，左右子树黑高相等。简而言之，根为黑、无“双红”、黑高相等。

令r指向实际被删除节点s的接替者，p指向x的父亲。s必有一个孩子为空。

如果实际被删除节点s为红色，直接删除即可；如果s为黑色，则需要根据情况修正，因为黑色节点对黑高有影响，删除一个黑色节点，黑高会减少。

删除分以下3种情况

1. s 为红色：删除s后，r接替其位置，满足红黑树的条件（根为黑、无“双红”、黑高不变）。根据红黑树的性质，红节点必有黑孩子，s为红色，其两个孩子必为黑色，s的其中一个孩子为空，另一个孩子也必为空，因为左右子树黑高相等

   

2. s 为黑色，接替者r为红色：因为s为黑色，删除s后，黑高减少。又因为p为黑色或红色，接替者r为红色，有可能出现“双红”。可以直接将r置为黑色，既维护了黑高（删除一个黑色的s，置r为黑色，黑高不变），又避免了“双红

   

3. s为黑色，接替者r为黑色：接替者r为黑色，根据左右子树黑高相同原则，r必为空。因为s为黑色，删除s后，黑高减少。被删除节点及其两个孩子都为黑色，这种情况称为“双黑”。为维护红黑树特性，需要分情况处理。将s的兄弟记为b（brother）, s的父亲仍然为p，分以下4种情况

   1. b 为黑色，b有红孩子。LL路径则右旋，旋转后的根保留原树根颜色，两个孩子染黑，LR、RR、RL相似

      

   2. b为黑色，b 无红孩子，p为红色。简单粗暴，b、p直接换色

      

   3. b为黑色，b无红孩子，p为黑色。将 b 直接染成红色，此时等效于p的父节点被删除，继续双黑修正，直到根。

      

   4. b为红色。这种情况先右旋（LL），b、p换色，转换为第1种或第2种情况继续处理。

      

所有的删除方法总结如下表