二叉搜索树

定义

空树是二叉搜索树
左子树的值都小于根节点
右子树的值都大于根节点
左右子树均为二叉搜索树

二叉搜索树的操作效率与高度成正比，某些情况下可能退化为链表。因此引出平衡树，通过一定操作维持树的高度（平衡性）来降低操作复杂度。

平衡树

不同平衡树对「平衡性」有不同的定义。二叉搜索树常见的平衡性定义：每一个节点的左右子树高度差最多为 1。

Splay 树：对任意节点的访问操作都会把节点移动到根位置。
AVL 树：每一个节点的左右子树高度差最多为 1。
B 树：每个节点保持一个预定义范围的关键字数量。

平衡的调整操作

AVL 中使用。分为左旋（zag）和右旋（zig）。

旋转操作

右旋：对节点 A 进行右旋，把左儿子向右上旋转，这样 A 成为 B 的右儿子，而 B 原来的右子树变为 A 的左子树。
左旋：同理。

一个简单的思路，为了调整平衡性就要把深度更深的子树提上来，然后相应调整其它节点关系。

下面引用 oi-wiki 的左右旋代码。

TreeNode* rotateLeft(TreeNode* root) {
  TreeNode* newRoot = root->right;
  root->right = newRoot->left;
  newRoot->left = root;
  // 更新相关节点的信息
  updateHeight(root);
  updateHeight(newRoot);
  return newRoot;  // 返回新的根节点
}

TreeNode* rotateRight(TreeNode* root) {
  TreeNode* newRoot = root->left;
  root->left = newRoot->right;
  newRoot->right = root;
  updateHeight(root);
  updateHeight(newRoot);
  return newRoot;
}

先暂存新的根节点
再调整原来根节点的指针指向新根节点某个子树
调整新根节点的儿子指向原根节点
返回新根节点

基本的链表操作思想。

AVL 每次插入都检查是否失衡（高度差大于 1）。失衡有四种情况：LL，RR，LR，RL。前两种都是单次旋转，后两种两次旋转。这里不展开赘述。

B 树

B 树即 m 路平衡搜索树，非常适合用于在相对小内存中实现对大规模数据的高效操作，实现分级存储思想。

B 树有两种节点：内部节点和外部节点，其中外部节点深度相同。由于 B 树的外部节点并不一定表示搜索失败，而是可能表示目标存在于更低一层存储结构，因此计算 B 树高度时需要算上外部节点。

B 树要求所有叶子节点高度相同。

多路搜索树

为了 减少外存操作，将根节点与它的左右孩子合并成一个“大节点”，保留左右孩子的指针，那么这个大节点就有 4 个指针。对一棵二叉搜索树都进行此操作，就变成了一棵四路搜索树。

一般地，以 \(k\) 层为间隔如此重组，就能将一棵二叉搜索树转换为等价的 \(2^k\) 路搜索树，统称多路搜索树。

为什么是以 \(k\) 层为间隔？一棵 \(k\) 层二叉树合并成一个节点，就会有 \(2^{k-1}\) 个叶子节点，每个叶子节点有两个指针。

多路平衡搜索树

回到 B 树。B 树每个大节点中包含的关键码数量并不确定。一棵 \(m\) 阶 B 树每个内部节点存有不超过 \(m-1\) 个关键码，用以指示对应分支的引用不超过 \(m\) 个。进一步地，分支的数量在 \([\lceil m/2 \rceil,m]\) 之间，所以 \(m\) 阶 B 树也叫 (\(\lceil m/2 \rceil,m\)) 树。

B 树通过合并节点的操作，搜索每下降一层，都以“大节点”为单位从外存读取一组而不是一个关键码，且这一组关键码在逻辑与物理上都相邻，可以一次性读出。只有在切换和更新节点时才会从外存 I/O，而在节点内部查找则在内存进行，且数量通常较小（1e3）级别，直接顺序查找即可。对于活跃的 B 树，根节点会常驻在内存，且任一时刻 只有 1 个 节点留驻在内存，称为当前节点。

由上面描述可知，B 树继承了搜索树的性质，即左边节点的关键码均小于右边节点，且合并时保持了节点内关键码的顺序，因此每个节点内部的关键码是有序的。

查找

与二叉搜索树类似，如果在节点内找到了关键码则成功，否则沿对应指针向下继续查找。

插入

B 树的插入总是在最底层的内部节点上。

定位关键码位置并插入对应节点
如果当前节点溢出，则需要进行分裂。
如果分裂后父节点溢出，对父节点重复分裂过程。如果分裂到达根节点，则 B 树高度加 1。

删除

删除要考虑的情况比较多。假设删除关键字 \(k\)。

令节点的关键字数量下限 \(l=\lceil m/2 \rceil -1\)，\(k\) 所在节点 \(v\) 关键字数量 \(c\)。

\(v\) 不是叶节点，那么它的直接前驱/后继一定是叶节点。用直接前驱/后继 \(k'\) 替换 \(k\)，问题转化为从叶节点删除 \(k'\)。
\(v\) 是叶节点
- 直接删除：\(c>l\)，直接删除
- 兄弟够借：\(c=l\)，且兄弟节点关键字个数大于 \(l\)，从父节点拿一个放入 \(k\) 中，再从兄弟节点中选一个最小/大的关键字放入父节点。
- 兄弟不够借：\(c=l\)，且左右兄弟节点关键字个数均为 \(l\)，则将 \(k\) 删除后与兄弟节点及父节点中关键字进行合并。

合并操作：

父节点关键字个数会减 1
如果父节点是根且关键字个数减少到 0，删除根节点，合并后的新节点成为根
如果父节点不是根，且关键字个数减少到 \(l-1\)，则重复操作。

插入、删除操作实现时，考虑上溢和下溢的情况。小心维护性质即可。

B+ 树

关键字仅存在于叶子节点，内部节点为索引节点，因此每次查找必须到叶子节点
叶子节点通过指针形成（双向）链表，由于数据只在叶节点上，所以可以通过链表顺序查找
节点子树个数与关键字数量相等，一个关键字对应一棵子树，表示子树中的最大/小值。

红黑树

自平衡二叉搜索树，各种时间复杂度都是 \(O(\log n)\)。其采用“适度平衡”标准：任一节点左右子树的高度，相差不得超过两倍。

规则

每个节点是红色或黑色
根节点是黑色的，叶子节点（虚构的外部节点）是黑色的
红色节点的子节点都是黑色
任一节点到叶子的路径上黑色节点数量相同（黑高）

插入

用于维护平衡性的旋转操作与 AVL 一致。

新插入的节点初始为红色（不影响到黑高规则）
违反规则就需要重新着色+旋转

特别的，如果插入节点是唯一的节点，只需要将其改为黑色即可。主要需要修复双红冲突。以下图为例进行说明，假设 N 是新插入节点，其它节点关系如图。

二叉树

U 是红色的，P 是 G 的孩子：由于 U 是红色，那么 G 必须是黑色。同时 N 是红色的，出现双红冲突说明 P 也是红色的。此时只需要染色，把 G 染红，P 和 U 染黑，然后向上检查性质是否满足即可。
（左左/右右）U 是黑色，P 是左（右）孩子，N 也是左（右）孩子。此时 P 和 N 都是红色。此时需要将 P 染黑，G 染红，对 G 右（左）旋。
（左右/右左）U 是黑色，P 是左（右）孩子，N 是右（左）孩子。此时 P 和 N 都是红色。此时对 P 进行左旋后，转化为上一情况。

注意到，情况 2 和 3 在插入前已经不符合黑高规则，因此不是插入导致的规则破坏，而是情况 1 调整后出现的情况。

删除操作需要进行双黑修复，较为复杂，这里略过。由于所有情况下，旋转操作后修复完成旋即就会完成，因此双红修复和双黑修复均仅涉及常数次的拓扑结构调整（与 AVL 不同）。

进阶：红黑树与 B 树之间存在极其密切的关系，经过适当转化两者等价。如红、黑染色的性质与 B 树节点分裂关系密切。