红黑树Red-Black Tree(R B-tree)

性质

本质是一个有限制的二叉搜索树BST,即每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。
通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。

红黑树示例
红黑树示例

  • 每个结点不是红色就是黑色
  • 根节点一定是黑色
  • 红色结点的子节点一定全部都是黑色
  • 每个叶子节点(叶结点即指树尾端NIL指针或NULL结点)一定是黑色
  • 对于任意一个节点，其到叶子节点NIL的路径中黑色节点的个数都是相同的
    (确保没有一条路径会比其他路径长出俩倍。因而，红黑树是相对是接近平衡的二叉树)

一棵含有n个节点的红黑树的高度至多为2log(n+1)

操作

树的左旋与右旋

  • 左旋指的是该节点旋转后，变为左孩子，该节点的右孩子变为其父亲
  • 右旋指的是该节点旋转后，变为右孩子，该节点的左孩子变为其父亲

不论左旋还是右旋指的都是该被旋转节点变为左或右孩子

左旋与右旋
左旋与右旋

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
LEFT-ROTATE(T, x)  
 y ← right[x]            // 前提：这里假设x的右孩子为y。下面开始正式操作
 right[x] ← left[y]      // 将 “y的左孩子” 设为 “x的右孩子”，即 将β设为x的右孩子
 p[left[y]] ← x          // 将 “x” 设为 “y的左孩子的父亲”，即 将β的父亲设为x
 p[y] ← p[x]             // 将 “x的父亲” 设为 “y的父亲”
 if p[x] = nil[T]       
 then root[T] ← y                 // 情况1：如果 “x的父亲” 是空节点，则将y设为根节点
 else if x = left[p[x]]  
           then left[p[x]] ← y    // 情况2：如果 x是它父节点的左孩子，则将y设为“x的父节点的左孩子”
           else right[p[x]] ← y   // 情况3：(x是它父节点的右孩子) 将y设为“x的父节点的右孩子”
 left[y] ← x             // 将 “x” 设为 “y的左孩子”
 p[x] ← y                // 将 “x的父节点” 设为 “y”
 RIGHT-ROTATE(T, y)  
 x ← left[y]             // 前提：这里假设y的左孩子为x。下面开始正式操作
 left[y] ← right[x]      // 将 “x的右孩子” 设为 “y的左孩子”，即 将β设为y的左孩子
 p[right[x]] ← y         // 将 “y” 设为 “x的右孩子的父亲”，即 将β的父亲设为y
 p[x] ← p[y]             // 将 “y的父亲” 设为 “x的父亲”
 if p[y] = nil[T]       
 then root[T] ← x                 // 情况1：如果 “y的父亲” 是空节点，则将x设为根节点
 else if y = right[p[y]]  
           then right[p[y]] ← x   // 情况2：如果 y是它父节点的右孩子，则将x设为“y的父节点的左孩子”
           else left[p[y]] ← x    // 情况3：(y是它父节点的左孩子) 将x设为“y的父节点的左孩子”
 right[x] ← y            // 将 “y” 设为 “x的右孩子”
 p[y] ← x                // 将 “y的父节点” 设为 “x”

插入节点

插入节点一共有有3步
→1. [插入]把红黑树当做二叉查找树，插入节点
→2. [着色]把插入的节点置为红色

  • 插入节点的父节点为黑色，结束
  • 插入节点的父节点为红色，进入3修复

→3. [修复]根据5种情况进行旋转，使之成为符合要求的红黑树
前提是父节点红色

插入情况
插入情况

删除节点

将红黑树内的某一个节点删除。需要执行的操作依次是：
首先，将红黑树当作一颗二叉查找树，将该节点从二叉查找树中删除；
然后，通过”旋转和重新着色”等一系列来修正该树，使之重新成为一棵红黑树。

详细描述如下：
第一步：将红黑树当作一颗二叉查找树，将节点删除。
这和”删除常规二叉查找树中删除节点的方法是一样的”。分3种情况：
① 被删除节点没有儿子，即为叶节点。那么，直接将该节点删除就OK了。
② 被删除节点只有一个儿子。那么，直接删除该节点，并用该节点的唯一子节点顶替它的位置。
③ 被删除节点有两个儿子。那么，先找出它的后继节点；然后把“它的后继节点的内容”复制给“该节点的内容”；之后，删除“它的后继节点”。在这里，后继节点相当于替身，在将后继节点的内容复制给”被删除节点”之后，再将后继节点删除。
这样就巧妙的将问题转换为”删除后继节点”的情况了，下面就考虑后继节点。 在”被删除节点”有两个非空子节点的情况下，它的后继节点不可能是双子非空。既然”的后继节点”不可能双子都非空，就意味着”该节点的后继节点”要么没有儿子，要么只有一个儿子。若没有儿子，则按”情况① “进行处理；若只有一个儿子，则按”情况② “进行处理。

第二步：通过”旋转和重新着色”等一系列来修正该树，使之重新成为一棵红黑树。
因为”第一步”中删除节点之后，可能会违背红黑树的特性。所以需要通过”旋转和重新着色”来修正该树，使之重新成为一棵红黑树。

① 情况说明：x是“红+黑”节点。
处理方法：直接把x设为黑色，结束。此时红黑树性质全部恢复。
② 情况说明：x是“黑+黑”节点，且x是根。
处理方法：什么都不做，结束。此时红黑树性质全部恢复。
③ 情况说明：x是“黑+黑”节点，且x不是根。
处理方法：这种情况又可以划分为4种子情况。这4种子情况如下：

Case 1 x是”黑+黑”节点，x的兄弟节点是红色。(此时x的父节点和x的兄弟节点的子节点都是黑节点)。
(01) 将x的兄弟节点设为“黑色”。
(02) 将x的父节点设为“红色”。
(03) 对x的父节点进行左旋。
(04) 左旋后，重新设置x的兄弟节点。

Case 2 x是“黑+黑”节点，x的兄弟节点是黑色，x的兄弟节点的两个孩子都是黑色。
(01) 将x的兄弟节点设为“红色”。
(02) 设置“x的父节点”为“新的x节点”。

Case 3 x是“黑+黑”节点，x的兄弟节点是黑色；x的兄弟节点的左孩子是红色，右孩子是黑色的。
(01) 将x兄弟节点的左孩子设为“黑色”。
(02) 将x兄弟节点设为“红色”。
(03) 对x的兄弟节点进行右旋。
(04) 右旋后，重新设置x的兄弟节点。

Case 4 x是“黑+黑”节点，x的兄弟节点是黑色；x的兄弟节点的右孩子是红色的，x的兄弟节点的左孩子任意颜色。
(01) 将x父节点颜色 赋值给 x的兄弟节点。
(02) 将x父节点设为“黑色”。
(03) 将x兄弟节点的右子节设为“黑色”。
(04) 对x的父节点进行左旋。
(05) 设置“x”为“根节点”。

参考

红黑树插入删除动画演示
July红黑树总结
深度好文 -> JDK 源代码研究 TreeMap 红黑树算法实现