跳转至

第 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 次。