Chinaunix首页 | 论坛 | 博客

hml1006的ChinaUnix博客hml1006.blog.chinaunix.net

首页　| 　博文目录　| 　关于我

hml1006

  • 博客访问： 198639
  • 博文数量： 34
  • 博客积分： 130
  • 博客等级： 入伍新兵
  • 技术积分： 427
  • 用 户 组： 普通用户
  • 注册时间： 2011-09-16 00:34
文章分类

全部博文（34）

文章存档

2013年（28）

2012年（6）

我的朋友
最近访客
推荐博文
相关博文
STL源码剖析---红黑树原理详解上

分类： C/C++

2013-09-22 15:35:08

STL源码剖析---红黑树原理详解上

分类： STL源码剖析 2012-07-12 16:31 7146人阅读 评论(6) 举报
数据结构null

目录(?)[+]

转载请标明出处，原文地址：http://blog.csdn.net/hackbuteer1/article/details/7740956
一、红黑树概述

     红黑树和我们以前学过的AVL树类似，都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。不过自从红黑树出来 后，AVL树就被放到了博物馆里，据说是红黑树有更好的效率，更高的统计性能。这一点在我们了解了红黑树的实现原理后，就会有更加深切的体会。
     红黑树和AVL树的区别在于它使用颜色来标识结点的高度，它所追求的是局部平衡而不是AVL树中的非常严格的平衡。学过数据结构的人应该都已经领教过AVL树的复杂，但AVL树的复杂比起红黑树来说简直是小巫见大巫，红黑树才是真正的变态级数据结构。
     由于STL中的关联式容器默认的底层实现都是红黑树，因此红黑树对于后续学习STL源码还是很重要的，有必要掌握红黑树的实现原理和源码实现。
     红黑树是AVL树的变种，红黑树通过一些着色法则确保没有一条路径会比其它路径长出两倍，因而达到接近平衡的目的。所谓红黑树，不仅是一个二叉搜索树，而且必须满足一下规则：
     1、每个节点不是红色就是黑色。
     2、根节点为黑色。
     3、如果节点为红色，其子节点必须为黑色。
     4、任意一个节点到到NULL（树尾端）的任何路径，所含之黑色节点数必须相同。
上面的这些约束保证了这个树大致上是平衡的，这也决定了红黑树的插入、删除、查询等操作是比较快速的。 根据规则4，新增节点必须为红色；根据规则3，新增节点之父节点必须为黑色。当新增节点根据二叉搜索树的规则到达其插入点时，却未能符合上述条件时，就必须调整颜色并旋转树形，如下图：

假设我们为上图分别插入节点3、8、35、75，根据二叉搜索树的规则，插入这四个节点后，我们会发现它们都破坏了红黑树的规则，因此我们必须调整树形，也就是旋转树形并改变节点的颜色。

二、红黑树上结点的插入

      在讨论红黑树的插入操作之前必须要明白，任何一个即将插入的新结点的初始颜色都为红色。这一点很容易理解，因为插入黑点会增加某条路径上黑结点的数目，从 而导致整棵树黑高度的不平衡。但如果新结点的父结点为红色时（如下图所示），将会违反红黑树的性质：一条路径上不能出现相邻的两个红色结点。这时就需要通 过一系列操作来使红黑树保持平衡。

      为了清楚地表示插入操作以下在结点中使用“新”字表示一个新插入的结点；使用“父”字表示新插入点的父结点；使用“叔”字表示“父”结点的兄弟结点；使用“祖”字表示“父”结点的父结点。插入操作分为以下几种情况：
1、黑父
     如下图所示，如果新节点的父结点为黑色结点，那么插入一个红点将不会影响红黑树的平衡，此时插入操作完成。红黑树比AVL树优秀的地方之一在于黑父的情况比较常见，从而使红黑树需要旋转的几率相对AVL树来说会少一些。

2、红父
     如果新节点的父结点为红色，这时就需要进行一系列操作以保证整棵树红黑性质。如下图所示，由于父结点为红色，此时可以判定，祖父结点必定为黑色。这时需要 根据叔父结点的颜色来决定做什么样的操作。青色结点表示颜色未知。由于有可能需要根结点到新点的路径上进行多次旋转操作，而每次进行不平衡判断的起始点 （我们可将其视为新点）都不一样。所以我们在此使用一个蓝色箭头指向这个起始点，并称之为判定点。

2.1 红叔
当叔父结点为红色时，如下图所示，无需进行旋转操作，只要将父和叔结点变为黑色，将祖父结点变为红色即可。但由于祖父结点的父结点有可能为红色，从而违反红黑树性质。此时必须将祖父结点作为新的判定点继续向上（迭代）进行平衡操作。

需要注意的是，无论“父节点”在“叔节点”的左边还是右边，无论“新节点”是“父节点”的左孩子还是右孩子，它们的操作都是完全一样的（其实这种情况包括4种，只需调整颜色，不需要旋转树形）。
2.2 黑叔
当叔父结点为黑色时，需要进行旋转，以下图示了所有的旋转可能：
Case 1:

Case 2:

Case 3:

Case 4:


      可以观察到，当旋转完成后，新的旋转根全部为黑色，此时不需要再向上回溯进行平衡操作，插入操作完成。需要注意，上面四张图的“叔”、“1”、“2”、“3”结点有可能为黑哨兵结点。
      其实红黑树的插入操作不是很难，甚至比AVL树的插入操作还更简单些。红黑树的插入操作源代码如下：
[cpp] view plaincopy
  1. // 元素插入操作  insert_unique()  
  2. // 插入新值：节点键值不允许重复，若重复则插入无效  
  3. // 注意，返回值是个pair，第一个元素是个红黑树迭代器，指向新增节点  
  4. // 第二个元素表示插入成功与否  
  5. template<class Key , class Value , class KeyOfValue , class Compare , class Alloc>  
  6. pair<typename rb_tree::iterator , bool>  
  7. rb_tree::insert_unique(const Value &v)  
  8. {  
  9.     rb_tree_node* y = header;    // 根节点root的父节点  
  10.     rb_tree_node* x = root();    // 从根节点开始  
  11.     bool comp = true;  
  12.     while(x != 0)  
  13.     {  
  14.         y = x;  
  15.         comp = key_compare(KeyOfValue()(v) , key(x));    // v键值小于目前节点之键值？  
  16.         x = comp ? left(x) : right(x);   // 遇“大”则往左，遇“小于或等于”则往右  
  17.     }  
  18.     // 离开while循环之后，y所指即插入点之父节点（此时的它必为叶节点）  
  19.     iterator j = iterator(y);     // 令迭代器j指向插入点之父节点y  
  20.     if(comp)     // 如果离开while循环时comp为真（表示遇“大”，将插入于左侧）  
  21.     {  
  22.         if(j == begin())    // 如果插入点之父节点为最左节点  
  23.             return pairbool>(_insert(x , y , z) , true);  
  24.         else     // 否则（插入点之父节点不为最左节点）  
  25.             --j;   // 调整j，回头准备测试  
  26.     }  
  27.     if(key_compare(key(j.node) , KeyOfValue()(v) ))  
  28.         // 新键值不与既有节点之键值重复，于是以下执行安插操作  
  29.         return pairbool>(_insert(x , y , z) , true);  
  30.     // 以上，x为新值插入点，y为插入点之父节点，v为新值  
  31.   
  32.     // 进行至此，表示新值一定与树中键值重复，那么就不应该插入新值  
  33.     return pairbool>(j , false);  
  34. }  
  35.   
  36. // 真正地插入执行程序 _insert()  
  37. template<class Key , class Value , class KeyOfValue , class Compare , class Alloc>  
  38. typename::_insert(base_ptr x_ , base_ptr y_ , const Value &v)  
  39. {  
  40.     // 参数x_ 为新值插入点，参数y_为插入点之父节点，参数v为新值  
  41.     link_type x = (link_type) x_;  
  42.     link_type y = (link_type) y_;  
  43.     link_type z;  
  44.   
  45.     // key_compare 是键值大小比较准则。应该会是个function object  
  46.     if(y == header || x != 0 || key_compare(KeyOfValue()(v) , key(y) ))  
  47.     {  
  48.         z = create_node(v);    // 产生一个新节点  
  49.         left(y) = z;           // 这使得当y即为header时，leftmost() = z  
  50.         if(y == header)  
  51.         {  
  52.             root() = z;  
  53.             rightmost() = z;  
  54.         }  
  55.         else if(y == leftmost())     // 如果y为最左节点  
  56.             leftmost() = z;          // 维护leftmost()，使它永远指向最左节点  
  57.     }  
  58.     else  
  59.     {  
  60.         z = create_node(v);        // 产生一个新节点  
  61.         right(y) = z;              // 令新节点成为插入点之父节点y的右子节点  
  62.         if(y == rightmost())  
  63.             rightmost() = z;       // 维护rightmost()，使它永远指向最右节点  
  64.     }  
  65.     parent(z) = y;      // 设定新节点的父节点  
  66.     left(z) = 0;        // 设定新节点的左子节点  
  67.     right(z) = 0;       // 设定新节点的右子节点  
  68.     // 新节点的颜色将在_rb_tree_rebalance()设定（并调整）  
  69.     _rb_tree_rebalance(z , header->parent);      // 参数一为新增节点，参数二为根节点root  
  70.     ++node_count;       // 节点数累加  
  71.     return iterator(z);  // 返回一个迭代器，指向新增节点  
  72. }  
  73.   
  74.   
  75. // 全局函数  
  76. // 重新令树形平衡（改变颜色及旋转树形）  
  77. // 参数一为新增节点，参数二为根节点root  
  78. inline void _rb_tree_rebalance(_rb_tree_node_base* x , _rb_tree_node_base*& root)  
  79. {  
  80.     x->color = _rb_tree_red;    //新节点必为红  
  81.     while(x != root && x->parent->color == _rb_tree_red)    // 父节点为红  
  82.     {  
  83.         if(x->parent == x->parent->parent->left)      // 父节点为祖父节点之左子节点  
  84.         {  
  85.             _rb_tree_node_base* y = x->parent->parent->right;    // 令y为伯父节点  
  86.             if(y && y->color == _rb_tree_red)    // 伯父节点存在，且为红  
  87.             {  
  88.                 x->parent->color = _rb_tree_black;           // 更改父节点为黑色  
  89.                 y->color = _rb_tree_black;                   // 更改伯父节点为黑色  
  90.                 x->parent->parent->color = _rb_tree_red;     // 更改祖父节点为红色  
  91.                 x = x->parent->parent;  
  92.             }  
  93.             else    // 无伯父节点，或伯父节点为黑色  
  94.             {  
  95.                 if(x == x->parent->right)   // 如果新节点为父节点之右子节点  
  96.                 {  
  97.                     x = x->parent;  
  98.                     _rb_tree_rotate_left(x , root);    // 第一个参数为左旋点  
  99.                 }  
  100.                 x->parent->color = _rb_tree_black;     // 改变颜色  
  101.                 x->parent->parent->color = _rb_tree_red;  
  102.                 _rb_tree_rotate_right(x->parent->parent , root);    // 第一个参数为右旋点  
  103.             }  
  104.         }  
  105.         else          // 父节点为祖父节点之右子节点  
  106.         {  
  107.             _rb_tree_node_base* y = x->parent->parent->left;    // 令y为伯父节点  
  108.             if(y && y->color == _rb_tree_red)    // 有伯父节点，且为红  
  109.             {  
  110.                 x->parent->color = _rb_tree_black;           // 更改父节点为黑色  
  111.                 y->color = _rb_tree_black;                   // 更改伯父节点为黑色  
  112.                 x->parent->parent->color = _rb_tree_red;     // 更改祖父节点为红色  
  113.                 x = x->parent->parent;          // 准备继续往上层检查  
  114.             }  
  115.             else    // 无伯父节点，或伯父节点为黑色  
  116.             {  
  117.                 if(x == x->parent->left)        // 如果新节点为父节点之左子节点  
  118.                 {  
  119.                     x = x->parent;  
  120.                     _rb_tree_rotate_right(x , root);    // 第一个参数为右旋点  
  121.                 }  
  122.                 x->parent->color = _rb_tree_black;     // 改变颜色  
  123.                 x->parent->parent->color = _rb_tree_red;  
  124.                 _rb_tree_rotate_left(x->parent->parent , root);    // 第一个参数为左旋点  
  125.             }  
  126.         }  
  127.     }//while  
  128.     root->color = _rb_tree_black;    // 根节点永远为黑色  
  129. }  
  130.   
  131.   
  132. // 左旋函数  
  133. inline void _rb_tree_rotate_left(_rb_tree_node_base* x , _rb_tree_node_base*& root)  
  134. {  
  135.     // x 为旋转点  
  136.     _rb_tree_node_base* y = x->right;          // 令y为旋转点的右子节点  
  137.     x->right = y->left;  
  138.     if(y->left != 0)  
  139.         y->left->parent = x;           // 别忘了回马枪设定父节点  
  140.     y->parent = x->parent;  
  141.   
  142.     // 令y完全顶替x的地位（必须将x对其父节点的关系完全接收过来）  
  143.     if(x == root)    // x为根节点  
  144.         root = y;  
  145.     else if(x == x->parent->left)         // x为其父节点的左子节点  
  146.         x->parent->left = y;  
  147.     else                                  // x为其父节点的右子节点  
  148.         x->parent->right = y;  
  149.     y->left = x;  
  150.     x->parent = y;  
  151. }  
  152.   
  153.   
  154. // 右旋函数  
  155. inline void _rb_tree_rotate_right(_rb_tree_node_base* x , _rb_tree_node_base*& root)  
  156. {  
  157.     // x 为旋转点  
  158.     _rb_tree_node_base* y = x->left;          // 令y为旋转点的左子节点  
  159.     x->left = y->right;  
  160.     if(y->right != 0)  
  161.         y->right->parent = x;           // 别忘了回马枪设定父节点  
  162.     y->parent = x->parent;  
  163.   
  164.     // 令y完全顶替x的地位（必须将x对其父节点的关系完全接收过来）  
  165.     if(x == root)  
  166.         root = y;  
  167.     else if(x == x->parent->right)         // x为其父节点的右子节点  
  168.         x->parent->right = y;  
  169.     else                                  // x为其父节点的左子节点  
  170.         x->parent->left = y;  
  171.     y->right = x;  
  172.     x->parent = y;  
  173. }  

转载请标明出处，原文地址：http://blog.csdn.net/hackbuteer1/article/details/7740956
阅读(1982) | 评论(0) | 转发(1) |
0

上一篇：一步一步写平衡二叉树（AVL树）

下一篇：平衡二叉树——AVL树的实现

给主人留下些什么吧！~~
关于我们 | 关于IT168 | 联系方式 | 广告合作 | 法律声明 | 免费注册

Copyright 2001-2010 ChinaUnix.net All Rights Reserved 北京皓辰网域网络信息技术有限公司. 版权所有

感谢所有关心和支持过ChinaUnix的朋友们

16024965号-6