SGI-STL源码剖析之RB-tree


  1. 二叉搜索树
  2. 平衡二叉搜索树
  3. AVL tree(Adelson-Velskii-Landistree)
  4. RB tree( 红黑树 )
    1. RB-tree 迭代器
    2. RB-tree 的数据结构
    3. 调整 RB-tree

二叉搜索树

二叉搜索树 (binary search tree) ,可提供对数时间 (10garithmictime)3 的元素插入和访问。二叉搜索树的节点放置规则是:任何节点的键值一定大干其左子树中的每一个节点的键值,并小于其右子树中的每一个节点的键值。因此,从根节点一直往左走,直至无左路可走,即得最小元素:从根节点一直往右走,直至无右路可走,即得最大元素。

查找
要在一棵二叉搜索树中找出最大元素或最小元素,是一件极简单的事:就像上述所言,一直往左走或一直往右走即是。

插入
插人新元素时,可从根节点开始,遇键值较大者就向左,遇键值较小者就向右,一直到尾端,即为插人点。

删除
欲删除旧节点A,情况可分两种。如果 A 只有一个子节点,我们就直接将 A 的子节点连至 A 的父节点,并将 A 删除。如果 A 有两个子节点,我们就以右子树内的最小节点取代 A 。注意,右子树的最小节点极易获得:从右子节点开始 ( 视为右子树的根节点 ) ,一直向左走至底即是。

平衡二叉搜索树

所谓树形平衡与否,并没有一个绝对的测量标准。“平衡”的大致意义是:没有任何一个节点过深 ( 深度过大 ) 。不同的平衡条件,造就出不同酌效率表现,以及不同的实现复杂度。 (每一种平衡树都有不同于其他平衡树的平衡条件,但是所有的平衡树都满足二叉搜索树的条件) 。

AVL tree(Adelson-Velskii-Landistree)

AVL tree是一个“加上了额外平衡条件”的二叉搜索树。其平衡条件的建立是为了确保整棵树的深度为O(logN) 。直观上的最佳平衡条件是每个节点的左右子树有着相同的高度,但这未免太过严苛。 AVL tree 于是退而求其次,其平衡条件为:任何节点的左右子树高度相差最多 1 。这是一个较弱的条件,但仍能够保证“对数深度 (logarithmic depth) ”平衡状态。

由于只有“插入点至根节点”路径上的各节点可能改变平衡状态,因此,只要调整其中最深的那个节点,便可使整棵树重新获得平衡

假设该最深节点为X ,由于节点最多拥有两个子节点,而所谓“平衡被破坏”意味着 X 的左右两棵子树的高度相差 2 ,因此我们可以轻易将情况分为四种:

1.插人点位于 X 的左子节点的左子树——左左。
2.插入点位于 X 的左子节点的右子树——左右。
3.插入点位于 X 的右子节点的左子树——右左。
4.插入点位于 X 的右子节点的右子树——右右。

情况1, 4 彼此对称,称为外侧 (outside) 插入,可以采用单旋转操作 (singlerotation) 调整解决。情况 2 , 3 彼此对称,称为内侧 (inside) 插入,可以采用双旋转操作 (doublerotation) 调整解决。

stl-rbtree-1.png

RB tree( 红黑树 )

RB— tree 不仅是一个二叉搜索树,而且必须满足以下规则 ( 即平衡条件 ) :
1. 每个节点不是红色就是黑色
2 .根节点为黑色。
3 .如果节点为红,其子节点必须为黑。
4.任一节点至 NULL( 树尾端 ) 的任何路径,所含之黑节点数必须相同。

根据规则 4 ,新增节点必须为红:根据规则 3 ,新增节点之父节点必须为黑。当新节点根据二叉搜索树的规则到达其插入点,却未能符合上述条件时,就必须调整颜色并旋转树形。

假设新节点为X ,其父节点为P ,祖父节点为 G ,伯父节点 ( 父节点之兄弟节点 ) 为 S ,曾祖父节点为 GG 。现在,根据二叉搜索树的规则,新节点 X 必为叶节点。根据红黑树规则 4 , X 必为红。所以,所有需要调整树形(或者颜色)的情况中, P 必定为红 (如此违反了规则 3 ,才会调整树形)。根据规则 3 可知父子节点不能同时为红,所以 G必为黑 (因为未插入新节点 X之前该树为 RB — tree,必须遵循规则 3)。 需要调整树形的情况仅仅与 X 的插入位置及外围节点 (S 和 GG) 的颜色有关 ( 由,前面可知 X,P,G 的颜色已经推定 ) ,故有以下四种考虑:

状况 1: S 为黑且 X 为外侧插入。对此情况,我们先对 P,G 做一次单旋转再更改 P,G 颜色,即可重新满足红黑树的规则 3 。如图:
stl-rbtree-2.png

注意,此时可能产生不乎衡状态(高度相差l 以上 ) 。例如图中的 A 和 B 为 null , D 或 E 不为 null 。这倒没关系,因为 RB — tree 的平衡性本来就比 AVL — tree 弱。然而 RB — tree 通常能够导致良好的平衡状态:是的,经验告诉我们, RB — tree 的搜寻平均效率和 AVL — tree 几乎相等。

状况 2: S为黑且 X 为内侧插入。对此情况,我们必须先对 P , X 做一次单旋转并更改 G , x 颜色,再将结果对 G 做一次单旋转,即可再次满足红黑树规则 3 。
stl-rbtree-3.png

《 STL 源码剖析》原文中的状况 3,4 **
**状况 3:
S为红且 X 为外侧插入。对此情况,先对 P 和 G 做一次单旋转,并改变 X 的颜色:此时如果 GG 为黑,一切搞定。如下图,但如果 GG 为红,则问题就比较大些,见状况 4 .
stl-rbtree-4.png

状况 4: S 为红且 X 为外侧插入。对此情况,先对 P 和 G 做一次单旋转,并改变 X 的颜色、此时如果 GG 亦为红,还得持续往上做,直到不再有父子连续为红的情况。
stl-rbtree-5.png

备注:状况 3 和 4 为 STL 源码剖析原文中给出的情况。观察源码便知,此处与源码不符。参考《勘误 <STL 源码剖析 > 》,作者做出的解释十分牵强,并不具有任何说服力。

自己理解的状况 3,4 **
**状况 3:
S 为红且 X 为外侧插入,或者为内侧插入。对此情况,改变 P,G,S 颜色,此时如果 GG 为黑,一切搞定。如果 GG 为红,见状况 4 。
stl-rbtree-6.png

状况 4: S 为红且 X 为外侧插入,或者为内侧插入。对此情况,改变 P,G,S 颜色,此时如果 GG 为红持续往上做,直到不再有父子连续为红的情况。
stl-rbtree-7.png

RB-tree 迭代器

void increment ()
{
    if (node—>right!=0)       // 如果有右子节点。 状况 <A>
    {
        node=node—>right ;    // 就向右走
            while(node—>left! ; )// 然后一直往左子树走到底
                node=node—>left ; // 即是解答
    }else {                       // 没有右子节点。 状况 <B>
        base_ptr y=node—>parent ; // 找出父节点
            while (node==y—>right){   // 如果现行节点本身是个右子节点
                node=y ;            // 就一直上溯,直到不为右子节点为止
                y=y->parent ;
            }
            if (node—>right!=y)        // 若此时的右子节点不等于此时的父节点
                node=y ;              // 状况 <C> 此时的父节点即为解答
                                      // 否则此时的 node 为解答 状况 <D>
    }
    // 注意,以上判断 “ 若此时的右子节点不等于此时的父节点 ” ,是为了应付一种
    // 特殊情况:我们欲寻找根节点的下一节点,而恰巧根节点无右子节点
    // 当然,以上特殊做法必须配合 RB—tree 根节点与特殊之 header 之间的
    // 特殊关系
}

void decrement ()
{
    if (node—>color==_rbtree_red&&          // 如果是红节点,且
        node—>parent—>parent==node)      // 父节点的父节点等于自己,
        node=node—>right ;               // 状况 <A> 右子节点即为解答
        // 以上情况发生于 node 为 header 时亦即 node 为 end() 时 )
        // 注意, header 之右子节点即 most right ,指向整棵树的 max 节点
    else if (node—>left!=0){          // 如果有左子节点。 状况 <B>
        base_ptry=node—>left ;     // 令 y 指向左子节点
            while (y—>right!=0)     // 当 y 有右子节点时
                y=y—>right ;      // 一直往右子节点走到底
                node=y ;         // 最后即为答案
    } else {     // 既非根节点,亦无左子节点
        base_ptry=node—>parent ;          // 找出父节点 状况 <C>
            while (node 二二 y—>left){       // 当现行节点身为左子节点
                node=y ;                 // 一直交替往上走,直到现行节点
                y=y—>parent ;            // 不为左子节点
            }
            node=y ; // 此时之父节点即为答案
    }
}

increment() 和 decrement() 两函数中,较为令人费解的是前者的状况< D >和后者的状况< A >,他们分别发生在下图所展示的状态下:
stl-rbtree-8.png

RB-tree 的数据结构

树状结构的各种操作,最需要关注的就是边界情况的发生,也就是走到根节点时要有特殊的处理。为了简化处理,SGI STL 特别为根节点再设计一个父节点,名为header ,并令其初始状态如下图所示:
stl-rbtree-9.png

调整 RB-tree

// 重新令树形平衡(改变颜色及旋转树形)
// 参数一为新增节点,参数二为 root
inline void
__rb_tree_rebalance (__rb_tree_node_base* x , __rb_tree_node_base*& root )
{
  x->color = __rb_tree_red;         // 新节点必为红
  while (x != root && x->parent->color == __rb_tree_red) { // 父节点为红
    // 父节点 P 为祖父节点 G 的左子节点 , 以下将进行已分析的四种状况。
    if (x->parent == x->parent->parent->left) { // 父节点为祖父节点之左子节点
      __rb_tree_node_base* y = x->parent->parent->right;     // 令 y 为伯父节点
      // 状态 3 :父节点为祖父节点之左节点,伯父节点存在且为红,下面的操作仅仅改变颜色,
      // 可以证明《 STL 源码剖析》状况 3 有错
      if (y && y->color == __rb_tree_red) {     // 伯父节点存在,且为红
        x->parent->color = __rb_tree_black;      // 更改父节点为黑
        y->color = __rb_tree_black;               // 更改伯父节点为黑
        x->parent->parent->color = __rb_tree_red;    // 更改祖父节点为红
        // 状态 4 :准备继续向上检查,即为状态 4 做检查准备工作 , 看到外层的 while 循环了吗?
        x = x->parent->parent;              
      }
      else {     // 无伯父节点,或伯父节点为黑
        // 状态 2 :无伯父节点,或伯父节点为黑, X 为父节点 P 的右子节点,即内侧插入,所以需要右旋转,
        // 然后继续向下完成左旋转
        if (x == x->parent->right) { // 如果新节点为父节点之右子节点
          x = x->parent;
          __rb_tree_rotate_left (x, root); // 第一参数为左旋点
        }

        // 状态 1 :无伯父节点,或伯父节点为黑, X 为父节点 P 的左子节点,即外侧插入,仅仅需要左旋转。
        // 状态 2 的左旋转同样在此完成
        x->parent->color = __rb_tree_black;   // 改变颜色
        x->parent->parent->color = __rb_tree_red;
        __rb_tree_rotate_right (x->parent->parent, root); // 第一参数为右旋点
      }
    }
    // 父节点 P 为祖父节点 G 的左子节点 , 类似上述四种状况。
    else {   // 父节点为祖父节点之右子节点
      __rb_tree_node_base* y = x->parent->parent->left; // 令 y 为伯父节点
      if (y && y->color == __rb_tree_red) {      // 有伯父节点,且为红
        x->parent->color = __rb_tree_black;       // 更改父节点为黑
        y->color = __rb_tree_black;              // 更改伯父节点为黑
        x->parent->parent->color = __rb_tree_red;    // 更改祖父节点为红
        x = x->parent->parent;    // 准备继续往上层检查 ...
      }
      else {     // 无伯父节点,或伯父节点为黑
        if (x == x->parent->left) {   // 如果新节点为父节点之左子节点
          x = x->parent;
          __rb_tree_rotate_right (x, root);    // 第一参数为右旋点
        }
        x->parent->color = __rb_tree_black;   // 改变颜色
        x->parent->parent->color = __rb_tree_red;
        __rb_tree_rotate_left (x->parent->parent, root); // 第一参数为左旋点
      }
    }
  }     // while 结束
  root->color = __rb_tree_black;    // 修正根节点,根节点永远为黑
}

// 新节点必为红节点。如果安插处之父节点亦为红节点,就违反红黑树规则,此时必须
// 做树形旋转(及颜色改变,在程序它处)。
inline void
__rb_tree_rotate_left (__rb_tree_node_base* x , __rb_tree_node_base*& root )
{
  // x 为旋转点
  __rb_tree_node_base* y = x->right;    // 令 y 为旋转点的右子节点
  x->right = y->left;
  if (y->left !=0)
    y->left->parent = x;         // 别忘了回马枪设定父节点
  y->parent = x->parent;
  // 令 y 完全顶替 x 的地位(必须将 x 对其父节点的关系完全接收过来)
  if (x == root)                    // x 为根节点
    root = y;
  else if (x == x->parent->left)    // x 为其父节点的左子节点
    x->parent->left = y;
  else                          // x 为其父节点的右子节点
    x->parent->right = y;  
         
  y->left = x;
  x->parent = y;
}

// 新节点必为红节点。如果安插处之父节点亦为红节点,就违反红黑树规则,此时必须
// 做树形旋转(及颜色改变,在程序它处)。
inline void
__rb_tree_rotate_right (__rb_tree_node_base* x , __rb_tree_node_base*& root )
{
  // x 为旋转点
  __rb_tree_node_base* y = x->left;     // y 为旋转点的左子节点
  x->left = y->right;
  if (y->right != 0)
    y->right->parent = x;   // 别忘了回马枪设定父节点
  y->parent = x->parent;

  // 令 y 完全顶替 x 的地位(必须将 x 对其父节点的关系完全接收过来)
  if (x == root)                    // x 为根节点
    root = y;
  else if (x == x->parent->right)   // x 为其父节点的右子节点
    x->parent->right = y;
  else                          // x 为其父节点的左子节点
    x->parent->left = y;

  y->right = x;
  x->parent = y;
}

本文作者:cyningsun
本文地址https://www.cyningsun.com/04-04-2011/stl-rbtree.html
版权声明:本博客所有文章除特别声明外,均采用 CC BY-NC-ND 3.0 CN 许可协议。转载请注明出处!

# STL