当先锋百科网

首页 1 2 3 4 5 6 7

通俗易懂看RB-tree（一）

RB-tree

首先RB-tree是一颗二叉搜索树。

特点：

  • 结点非红即黑。
  • 根节点为黑。
  • 如果结点为红，则子结点必为黑。
  • 任一结点至NULL的任何路径，所含黑结点树必须相同。

由规则3可知：新增结点之父结点必为黑。
由规则4可知：新增结点必为红。

插入结点

  • 状况1：状况1：S为黑且X为外侧插入，对此情况，我们先对P,G做一次单旋转，并更改P,G颜色，即可重新满足规则3。

这里写图片描述

  • RB-tree的搜索平均效率和AVL-tree几乎相等。
  • 状况2：S为黑且X为内侧插入。对此，需先对P,X做一次单旋转，并改变G,X颜色，再讲结果对G做单旋转。即可满足规则3。

这里写图片描述

  • 状况3：S为红且X为外侧插入。对此，先对P和G做一次单旋转，并改变X颜色，此时GG为黑。但如果GG为红，见状况4。

这里写图片描述

  • 状况4：S为红且X为外侧插入。对此，先对P，G做一次单旋转，并改变X颜色，此时若GG还为红，持续向上做，知道不再有父子连续为红为止。

这里写图片描述

为避免“父子结点皆为红色”的情况持续向RB-tree上层结构发展，可以施行一个由上而下的程序：假设新增加点为A，那么就沿着A的路径，*只要看到有某结点X的两个子结点皆为红色，就把X改为红色，并把两个子结点改为黑色。*

特别注意init()的实现技巧:

void init()
{
    header=get_node();//产生一个结点空间，令header指向它；
    color(header)=rb_tree_red;

    root()=;
    leftmost()=header;//header左子结点为自己
    rightmost()=header;//header右子结点为自己
}

我们知道，树状结构的各种操作，最需注意的是边界情况的产生，也就是到根节点时要有特殊的处理。为了简化处理，为根节点再设计一个父节点，名为header，令初始状态如图所示：

这里写图片描述