第 2 周:红黑树和 B+ 树¶
红黑树¶
红黑树是满足下面五个条件的二叉树:
- 所有的结点要么是红色,要么是黑色。
- 根节点是黑色的。
- 叶子节点都是 NIL,并且都是黑色的。
- 红色的节点的子节点是黑色的。
- 对于某一个节点,所有从它走到它下面的叶子节点的路径中,黑色结点的数量是相同的。
第 3 条和第 5 条配合起来,会压低树的高度。
第 4 条和第 5 条是为了让红黑树可以和 B 树对应:实际上把红色节点插进它的黑色祖先里后就会变成一个 B 树,而所有叶子节点的深度还刚好相同。
【定理】一个有 n 个(非 NIL)节点的红黑树的高度最多是 \(2 \ln (n + 1)\)。
插入¶
新的节点先设成红色,因为这样的话后期调整的次数总会比设成黑色的少。
如果新的结点是红色,就破坏了红黑树的性质,这个时候需要调整结点的颜色。
父节点一层都是红色的¶
那就翻转父节点一层和祖父结点的颜色,递归。
父节点一层一黑一红¶
假设插入了红色节点 x,上面是红色父节点 p 和黑色祖父节点 g。
如果现在 x 是 p 的左子节点,p 是 g 的左子节点(方向不同的话就转一下 x),那就转一下 p 让它成为黑节点,x 和 g 变成它的左右节点。镜像同理。
删除¶
删除的是个叶子?变成 NIL 就好了。
删除的点度数为 1?子树接上来就好了。
度数为 2 的话,拿左子树的最大节点或者右子树的最小节点把原节点夺舍了,所以我们删除的节点就变成了一个叶子节点。
但是,这个时候我们还得维护红黑树(的第 5 条限制)。如果这个节点是黑色节点,那么我们要把节点的颜色修改一下,否则和这个点相关的路径就会少一个黑色节点。现在当前节点(这个叶子节点)是父节点的左子节点。
兄弟节点是红色的¶
把兄弟节点变成黑色,父节点变成红色,之后把兄弟节点旋上去两次。然后当前节点有了新的兄弟节点。因为之前的兄弟节点的子节点一定都是黑色的,情况会变成下面三个中的一个。
兄弟节点的两个子节点都是黑色的¶
把兄弟节点变成红色。
如果现在的父节点是红色,那把它变成黑色后就可以结束了;如果是黑色的,那还要对父节点进行递归。
兄弟节点的左子节点是红色,右子节点是黑色¶
把兄弟节点变成红色,它的左子节点变成黑色,然后把它的左子节点旋上来。这样会到达下面这个情况。
兄弟节点的右子节点是红色¶
把兄弟节点的右子节点变成黑色,然后把兄弟节点旋上来。
把兄弟节点的颜色变成原来的父节点的颜色,把原来的父节点变成黑色。
复杂度¶
红黑树在插入后最多转 2 次就可以调整完;删除的话最多转 3 次。