jlearning.cn

《数据结构与算法分析》(3)——红黑树

红黑树

红黑树是具有下列着色性质的二叉查找树(AVL树):
  1. 每一个节点或者着成红色,或者着成黑色。
  2. 根是黑色的
  3. 如果一个节点是红色,那么它的子节点必须是黑色。
  4. 从一个节点到一个NULL指针的每一条路径必须包含相同数目的黑色节点。

对红黑树的操作在最坏情形下花费$O(logN)$时间,而且一种慎重的递归实现可以相对容易地完成。

在红黑树的插入操作中,通常把新项作为树叶放到树中。如果涂成黑色,肯定违反4。所以必须是红色。如果父节点是红色,违反3。这种情况下必须调整该树来确保条件3满足。

自底向上插入

父亲是红色节点,兄弟是黑色的情形(NULL节点被认为是黑色的)

自底向上插入

X是新加的树叶,为了一般,考虑的是插入一个子树。

在S是黑色的情况下,GPX有一字型和Z字形两种情况(上图中的左上和左下),旋转之后变为右上和右下。这两种情况下都完成了亮点:

  • 子树的根都是黑色的,所以不需要关心曾祖的颜色。不可能出现红红相邻的情况。
  • 通向ABC路径上黑色节点的数目,旋转之后和旋转之前保持不变。

自顶向下红黑树

现在来考虑兄弟节点是红色的情况。

  • 在向下地过程中,当我们看到一个节点X有两个红儿子的时候,我们让X成为红的而让它的两个儿子是黑的。
  • 当X的父节点P也是红的时候,这种反转将破坏红黑的法则,可以用上图中的适当旋转。
  • 如果X的父节点P的兄弟也是红的呢,这种可能已经被自顶向下过程中处理过了,所以不可能出现。

经验指出,平均红黑树大约和平均AVL树一样神,从而查找时间一般接近最优。

执行插入所需要的开销相对较低,实践中发生的旋转相对较少。

自顶向下删除

首先将红黑树当作一颗二叉查找树,将该节点从二叉查找树中删除:

  1. 被删除节点没有儿子,即为叶节点。那么,直接将该节点删除就OK了。
  2. 被删除节点只有一个儿子。那么,直接删除该节点,并用该节点的唯一子节点顶替它的位置。
  3. 被删除节点有两个儿子。那么,先找出它的后继节点;然后把“它的后继节点的内容”复制给“该节点的内容”;之后,删除“它的后继节点”。在这里,后继节点相当于替身,在将后继节点的内容复制给”被删除节点”之后,再将后继节点删除。这样就巧妙的将问题转换为”删除后继节点”的情况了,下面就考虑后继节点。 在”被删除节点”有两个非空子节点的情况下,它的后继节点不可能是双子非空。既然”的后继节点”不可能双子都非空,就意味着”该节点的后继节点”要么没有儿子,要么只有一个儿子。若没有儿子,则按”情况① “进行处理;若只有一个儿子,则按”情况2”进行处理。

然后通过“旋转和着色”来修正树,使其成为一颗红黑树