红黑树 | Personal Blog

红黑树

发表于

红黑树的性质

  1. 结点不是红色就是黑色
  2. 根结点是黑色
  3. 叶子结点是黑色
  4. 红色结点的子结点是黑色的
  5. 对每一个结点，从该结点到其所有后代结点的简单路径上，有相同数量的黑色结点

旋转

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
27

LEFT-ROTATE(T,x)//左旋
{
    y=x.right;//y指向x的右子树
    x.right=y.left;//x的新右子树是y原来的左子树
    if(y.left!=T.nil)//y有左子树
    {
        y.left.p=x;//则将y原来的左子树的父结点指针指向x
    }
    y.p=x.p;//y取代x的位置，将y的父结点指针指向父结点

    if(x.p==T.nil)//若x是根结点
    {
        T.tool=y;//y就是新的根结点
    }
    else if(x==x.p.left)//x是左孩子
    {
        x.p.left=y;//x的父结点的左孩子指针指向y
    }
    else
    {
        x.p.right=y;
    }
    y.left=x;//x作为y的新的左子树
    x.p=y;
}

综上，左旋的操作结果导致：

  1. 右孩子替换原来结点的位置
  2. 原来结点作为右孩子的左孩子
  3. 右孩子的左孩子是原来结点新的右孩子

插入

插入新结点的指导思想

  1. 尽可能少地违反性质
  2. 将违反性质的结点不断上移
  3. 先解决孩子的问题，再解决双亲的问题

插入的步骤

  1. 根据指导思想1，新插入的结点须赋给红色；因为赋给黑色时违反性质5，而赋给红色时可能不违反性质，也可能违反性质2或性质4(最多违反一种);赋给红色违反性质的可能性小
  2. 若新结点违反性质2，则将其变为黑色，结束插入
  3. 若新结点违反性质4，说明新结点的父结点是红色的，进一步说明新结点的祖父结点是黑色的；进行如下操作：

为了方便叙述，将新结点称为N，新结点的父结点称为F，新结点的叔结点称为U，新结点的祖父结点称为G

情况1：新结点的叔结点是红色的

  1. 根据指导思想2、3，解决N的问题，可以将F置为黑色，新结点就不违反性质了
  2. 但是此时F违反了性质5，因为以F为根结点的子树增加了一个黑色结点，为了消除影响，只好将G置为红色
  3. 此时U又违反了性质5，因为少了一个黑色结点，只好将U置为黑色
  4. 此时N,F,U均不违反性质，唯一可能违反性质的就是G，且G只能违反性质4，于是将G视为新插入的结点

情况2：新结点的叔结点是黑色的，且新结点是右孩子

  1. 根据指导思想2，将F左旋
  2. 根据指导思想3，解决此时F的问题，将F视为新插入的结点

情况3：新结点的叔结点是黑色的，且新结点是左孩子

  1. 将F置为黑色，于是N就不违反性质了
  2. 但此时F违反性质5，因为多了一个黑色结点，于是将G置为红色
  3. 此时U违反性质5，于是将G右旋
  4. 现在唯一有可能违反性质的就是U，且U只能违反性质4，于是将U视为新插入的结点