2 Red-Black Trees and B+ trees¶

文本统计：约 1488 个字

2.1 Red-Black Trees¶

性质¶

结构：

定义：

每个节点颜色或红或黑
根节点是黑的
每个叶子节点都指向NIL，颜色为黑
如果一个节点是红的，那么他的子节点都是黑的
对于每个节点，从节点到后代叶的所有简单路径都包含相同数量的黑节点。

Black-height : The black-height of any node x, denoted by bh(x), is the number of black nodes on any simple path from x (x not included) down to a leaf. bh(Tree) = bh(root). (自身是黑的不算，包含叶节点)

Internal node/External node：external node就是叶子节点（NIL），Internal node就是其他所有点

引理：一个包含N个内点的红黑树最大的树高为\(2\log (N+1)\), \(\text{sizeof}(x)\geq 2^{h/2}-1\)

用数学归纳法证明：\(\text{sizeof}(x)\geq 2^{bh(x)}-1\)

当\(h(x)=0\)时，x为NULL，满足条件

假设对于所有满足\(h(x)\leq k\)的x均成立

对于\(h(x)=k+1\)，\(bh(child)=bh(x)\ or\ bh(x)-1\)

借由归纳假设，可知\(\text{sizeof}(child)\geq 2^{bh(child)}-1\geq 2^{bh(x)-1}-1\)

进而\(\text{sizeof}(x)=1+2\text{ sizeof}(child) \geq 2^{bh(x)}-1\)

由红黑树的定义可知\(bh(Tree)\geq h(Tree)/2\) , 从而引理成立。

Insert（插入操作）¶

插入的节点染色为红。

Case 1: 插入的节点的父亲和叔叔均为红

Case 2: 出现zig-zag类似的情况，调整为直线型

Case 3: 插入的节点的父亲为红，叔叔为黑

复杂度：\(T=O(h)=O(\log N)\)

Case 3 的另一种方法是否正确

以上操作不能成立。

在题目中，各个节点均可能存在字数，暂时将其命名为A、B、C、D、E，且颜色未定，则该操作如下图所示。

则此时会出现两种矛盾：

1.违反第五条定律——各个到叶子节点路径的黑色节点数目不同。

由初始状态可知，bh(2) =bh(A) =bh(3) >=1 (由4节点为黑色节点可知)

而在最终状态下，bh(2) =bh(A) =bh(3)-1

则产生矛盾——bh(3) = bh(3) -1

因此该操作无法成立

2.可能违反第四条定律——红色节点的子节点必为黑色节点

如下图，若D、E节点其中一节点为红色节点（此处以E节点为例），则在初始状态该红黑树无矛盾，可能成立。

但在最终状态下，4节点为红色节点，下端连接红色节点E，则会产生红色节点下连接红色节点的矛盾。

Delete（删除操作）¶

先按照BST的删除方法，一直递归删除下去，总会删到叶节点的情况

如果删除的叶子节点是红色点，直接删除即可

如果删除的叶子节点是黑色点，

我们需要做的是将x的子树比兄弟节点的子树黑高大1，将其分为四种情况处理

case1: 删除的节点的兄弟节点为红色通过改色和旋转，转换成兄弟节点为黑色的情况

case2: 兄弟节点为黑色，子节点也都是黑色

如果父亲节点为红，直接改父亲节点为黑兄弟节点为红，从而安全地删除x
如果父亲节点为黑，将父亲节点作为操作删除地对象，递归向上使这棵子树的黑高加1（同样的操作），从而可以安全地删除x

case3: 兄弟节点为黑色，右节点为黑色，通过改色和旋转改到右节点为红色的情况

case4: 兄弟节点为黑色，右节点为红色，这样就可以通过改色和旋转使x所在的子树上黑高多1，从而安全地删除x

从而我们使x所在的子树比兄弟子树的黑高多了1，如果x是叶子节点，那么我们直接删除即可。

总的来说就是

case1 \(\rightarrow\) case 2,3,4

case3 \(\rightarrow\) case 4

Example

Note

一次删除操作最多进行三次旋转操作：case1->case3->case4

2.2 B+ Trees¶

定义：一个M阶B+树满足以下性质

根节点要么是叶节点要么含有2~M个子节点
所有非叶子节点（除了根节点）有\(\lceil M/2\rceil\)和\(M\)个子节点
所有叶子有着相同的深度

A B+ tree of order 4 (2-3-4 Tree)

Insert（插入操作）¶

由定义可以看出，对于一棵order为M的B+树来说，每个叶子中最多有M个keys，然后非叶子节点至多含有M-1个分割点（至多有M个孩子）。

所以整个操作流程是将插入的数据按照索引插入，假若一个叶子中的keys超过M个，那么对该叶子节点进行分裂，分裂为\(\lfloor M\rfloor\)和\(\lceil M\rceil\)并将分裂出来的第\(\lceil M\rceil\)个数作为索引拿到父亲节点上。假若父亲节点中keys的数量超过\(M-1\)，则将\(\lceil M-1\rceil\)位升到祖先节点上，依次类推……

具体代码详见Homework中的编程题。