红黑树

R-B Tree，全称Red-Black Tree，又称红黑树，它是一种特殊的二叉查找树。
红黑树的每个节点上都有存储位表示节点的颜色，可以是红或黑。

特征

1. 每个节点或黑色或红色
2. 根节点是黑色
3. 每个叶子节点（NIL）是黑色。[ 这里是叶子节点，是指为空(NIL或NULL)的叶子节点]
4. 如果一个节点是红色的，则它的子节点必须是黑色的
5. 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点数。

注意

1. 特性3中的叶子节点，是只为空(NIL或null)的节点。
2. 特征5中，确保没有一条路径比其他路径长2倍。因此，红黑树是最接近平衡的二叉树。

应用

红黑树的应用比较广泛，主要用它存储有序的数据
它的时间复杂度O(logn)，效率非常高
eg：java的TreeSet和TreeMap，linux虚拟内存都是用红黑树去实现的

时间复杂度

红黑树的时间复杂度：O(lgn)

通过数学归纳法对红黑树的时间复杂度进行证明
定理：一颗含有n个节点的红黑树的高度至多为2log(n+1)

旋转

红黑树的平衡操作是通过旋转操作来实现的，分为左旋和右旋

左旋（顺时针）

Y为根结点，A为Y的右孩子，以Y-A为轴进行左旋，A为新的根结点，Y为A的左孩子，A原左孩子B为旋转后Y的右子，Y的左子和A的右子不变

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”

理解左旋之后，再看个更鲜明的例子

右旋（逆时针）

Y为根结点，X为Y的左孩子，以Y-X为轴进行右旋，X为新的根结点，Y为X的右孩子，X原右孩子R为旋转后Y的左子，Y的右子和X的左子不变。

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”

理解右旋之后，再看个更鲜明的例子

如何区分左旋和右旋

• 左旋转（以x为节点进行左旋）

                                  z
  x                             /                  
  / \      --(左旋)-->  x
  y   z                      /
                         y

  对x轴左旋，将x的右孩子设为x的父节点
  因此左旋中的’左’，意味着’被旋转的节点将变成一个左节点’

• 右旋转（以x为节点进行右旋）

                             y
  x                            \                 
  / \      --(右旋)-->     x
  y   z                              \
                                      z

  对x轴右旋，将x的左孩子变成x的父节点
  因此右旋中的’右’，意味着’被旋转的节点将变成一个右节点’

添加

将红黑树当作一颗二叉查找树，将节点插入；
然后，将节点着色为红色；
最后，通过旋转或重新着色等方法来修正该树，使之重新成为一颗红黑树

第一步：将红黑树当作一颗二叉查找树，将节点插入

• 红黑树本身就是一颗二叉查找树，将节点插入后，该树仍是一颗二叉查找树。
• 也就意味着，树的键值对仍然是有序的。
• 并且不管是左旋还是右旋，旋转前是二叉树，旋转后还是二叉树。
• 也就是说，不管转换还是着色都是一颗二叉树

第二步：将插入的节点着色为"红色"
为什么要着色为红色？首先查看红黑树的特性：

1. 每个节点要么黑色要么红色
2. 根节点是黑色的
3. 每个叶子节点是黑色的（叶子就是说NULL，NIL）
4. 如果一个节点是红色，则它的其他节点必须是黑色
5. 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点
   

   将插入的节点着色为红色，不会违背特征5
   少违背一条特性，就意味着我们需要处理的情况越少。
   然后就尽量满足其他性质，这样就又变成红黑树了。

第三次：通过一系列的旋转或着色等操作，使之重新称为一颗红黑树

1. 不违背。已涂红
2. 不违背。插入操作不会改变根节点
3. 不违背。查非空对空值节点没影响
4. 可能违背。因为插入的是红节点
5. 不违背。因为插入的是红节点

so，被插入的节点就有这些可能出现的问题。

上面三种情况case的核心处理问题思路是：将红色的节点移到根节点；然后，将根节点变成黑色

1，(case1)叔叔是红色

1.1 现象说明

当前节点（也就是被插入的节点）的父节点是红色，且当前节点的祖父节点的另一个子节点（叔叔节点）也是红色。

1.2 处理策略

1. 将"父节点"变成黑色
2. 将"叔叔节点"变成黑色
3. 将"祖父节点"变成红色
4. 将"祖父节点"变成当前节点（即红色节点）；即，之后继续对"当前节点"进行操作

1.3 处理原因

首先，插入的节点何父节点都是红色，违背特征4，所以需要将"父节点"变成黑色。
其次，父节点变成黑色后，就违背特征5，导致包含"父节点"的分支的黑色节点的总数增加1。

so，解决方案

1. 祖父节点之前是黑色。因为父节点是红色，所以祖父节点必须是黑色
2. 将祖父变成红色，叔叔节点变成黑色，能解决包含"父节点"的分支的黑色节点的总书增加1，这样包含"祖父节点"的分支的黑色节点总数也增加1，"叔叔节点"也变成黑色，就能节点这个问题。
   

   总结

按照上述操作处理后，当前节点，"父节点"和"叔叔节点"之间都不会违背红黑树特性，但"祖父节点"就不一定了。
如果"祖父节点"是根节点，直接将"祖父节点"变成黑节点.
如果"祖父节点"不是根节点，那么我们需要将"祖父节点"设成"新的当前节点"，直接对"新的当前节点"进行分析。

1.4 示意图

2，（case2）叔叔是黑色，且当前节点是右孩子

2.1 现象说明

当前节点（也就是被插节点）的父节点是红色，叔叔节点是黑色，且当前节点是其父节点的右孩子

2.2 处理策略

1. 将"父节点"作为新的当前节点
2. 将新的当前节点作为支点进行左旋

2.3 处理原因

首先，将"父节点"作为新的节点。
其次，将"当前节点"为支点进行左旋

红黑树的核心思想：
将红色的节点移到根节点，然后将根节点变成黑色。
既然是"将红色的节点移到根节点"
那就说要不断的将破坏红黑树特性的红色节点上移（即根节点方向）
即：将"父节点"作为"新的节点"

2.4 示意图

3，（case3）叔叔是黑色，且当前节点是左孩子

3.1 现象说明

当前节点（被插入的节点）的父节点是红色，叔叔节点是黑色，且当前节点是其父节点的左孩子

3.1 处理策略

1. 将"父节点"变成"黑色"
2. 将"祖父节点"变成"红色"
3. 以"祖父节点"为支点进行右旋

3.1 处理原因

儿子节点和父节点都是红色，就违背了红黑树的特性4；
将父节点由红色变成黑色，能解决违背4，但违背5；
因为这样所有经过父节点的黑色节点个数增加1；
那么如果解决所有经过父节点的分支的黑色节点的个数增加1的问题，就将祖父节点由黑色变成红色，并已祖父节点作为支点进行右旋。

3.1 示意图

分享到：

赞(0) 打赏