Red-Black Trees & B+ Trees

红黑树¶

定义：

• 每个节点要么是红色要么是黑色
• 根节点为黑色
• 红黑树的叶节点定义为 NULL(NIL) ，叶节点都是黑色，不显式画出
• 如果一个节点是红色，那么它的孩子都应该为黑色
• 每个节点到它的后代叶节点的路径包含相同数量的黑色节点
  • 定义 black-height 为任一节点x到叶节点所经过的黑色节点数量（包括x）

Insert¶

插入的节点默认颜色为红色，以下的图片通过 Insert 4 来展示关于红黑树插入的所有情况。

其中应注意，节点 15 应该为红色，该图有错误

From Oneko 的笔记

红黑树插入的时间复杂度也为 \(O(\log N)\)

从 Empty Tree 开始，依次插入 41, 38, 31, 12, 19, 8

Delete¶

红黑树的删除分为两个步骤：

第一步：

• 删除叶子节点
  • 如果该节点为红色，使用 NIL 代替该节点，且无需进行第二步调整
  • 如果该节点为黑色，使用 NIL 代替该节点，且需进行第二步调整，将该 NIL 节点记为 x
• 删除度为 1 的节点
  • 用它的孩子代替该节点，并改为黑色，无需进行第二步调整
  • 这种情况，只可能是该节点为黑色，子节点为红色，否则会违反红黑树性质
• 删除度为 2 的节点
  • 与左子树中最大的节点或是右子树中最小的节点交换值，并对其调用删除，重新进入上述两种情况之一

第二步：

能进入第二步调整，说明最终删除的是黑色叶子节点，将用作替代的 NIL 记为 x，它的 sibling 记为 w ，它的父节点称为 p

Case 1：

节点 w 为红色节点，那么父节点一定是黑色节点。

调整操作为对节点 p 和 w 都进行变色，然后对节点 p 进行 Rotate：

此时需要继续调整，转入 Case 2，3，4

Case 2：

节点 w 为黑色节点，且 w 的两个子节点均为黑色节点

调整操作为将节点 w 变色为红色。若节点 p 为红色，直接将其变为黑色结束调整；若节点 p 为黑色，重新将其命名为节点 x ，需要继续调整，转入 Case 2，3，4

Case 3：

节点 w 为黑色节点，且它的唯一红色子节点与 w,p 构成 RL 关系（对称情况不列出）

调整操作为将节点 w 与其唯一红色子节点变色，并对节点 w 进行一次右旋，需要继续调整，转入 Case 4

Case 4：

节点 w 为黑色节点，且它存在红色子节点与 w,p 构成 RR 关系（对称关系不列出）

调整操作为将该红色子节点变色为黑色，节点 w 变色为父节点 p 的颜色，节点 p 变色为黑色，再对节点 p 进行一次左旋完成调整

Numbers Of Rotations：

1
2
3
4
5
6
7
8
9

typedef enum { red, black } colors;
typedef struct RBNode *PtrToRBNode;
struct RBNode{
    int Data;
    PtrToRBNode Left, Right, Parent;
    int BlackHeight;
    colors Color;
};
typedef PtrToRBNode RBTree;

B+ 树¶

一个 Order M 的 B+ 树定义如下：

• 根节点要么是叶节点，要么有 2 到 \(M\) 个子节点
• 所有除了根节点的非叶节点都有 \(\lceil \frac{M}{2} \rceil\) 到 \(M\) 个子节点
• 所有叶节点深度相同

• A 2-3 tree with 3 nonleaf nodes must have 18 keys at most. (T)
  • 一个非叶节点为根节点，其余两个节点最多有 2*3=6 个叶节点孩子；一个叶子存放 3 个 key，一共 18 个

B+ Tree 的插入如下：

以 2,3 树的插入为例，其主要思路概括如下：

（1）与内部节点所存键值比较，找到合适叶节点插入

（2）如果插入后该节点键数不超过3，则插入结束；若超过，继续（3）进行调整

（3）将4个键值按大小分为两个节点，并为它们的父节点增加一个键值

（4）如果父节点增加新键值后键数不超过2，则插入结束；若超过，则继续（5）进行调整

（5）将该节点分为两个节点，左节点继承 key[0]，右节点继承 key[2]，key[1]作为新的键值传递给父节点，回到步骤（4）