C++ STL源码剖析之红黑树

0.导语

在STL源码中有两段话，简单翻译后如下：

STL中Red-black tree（红黑树）class,用来当做SLT关系式容器（如set,multiset,map, multimap）.里面所用的insertion和deletion方法以《Introduction to Algorithms》一书为基础,但是有以下两点不同:

(1)header不仅指向root,也指向红黑树的最左节点,以便用常数时间实现begin(),并且也指向红黑树的最右边节点,以便 set相关泛型算法（如set_union等等）可以有线性时间表现.

(2)当要删除的节点有两个子节点时，其后继节点连接到其位置，而不是被复制，因此，唯一使无效的迭代器是引用已删除节点的迭代器。

上述话翻译成图，如下，相比于普通的红黑树多了一个header节点，并且为红色。普通的红黑树是以100节点开始的，且满足下面五条性质：- 每个节点或是红色的,或是黑色的.- 根节点是黑色的.- 每个叶节点（NULL）是黑色的.- 如果一个节点是红色的，则它的两个孩子节点都是黑色的.- 对每个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点.

当然这里的rb_tree也是一样满足这几条性质，迭代器的begin指向红黑树根节点，也就是header的父亲，而end指向header节点。

st.png。图中省略号表示节点没有画完，还有其他节点，所以省略。

1.红黑树节点基类

红黑树基类，非常简单，在文件开头定义了颜色标记。

基类中包含了指向自己的指针，分别定义了left、right、parent，同时包含了一个颜色标记常量，而里面有两个核心函数，目的是获取红黑树中最小节点与最大节点。我们知道对于二分搜索树获取最小节点就是左子树一直往下搜，最大节点就是右子树一直往下搜即可。

  1. // 颜色标记
  2. enum _Rb_tree_color { _S_red = false, _S_black = true };
  4. // 基类
  5. struct _Rb_tree_node_base
  6. {
  7. // typedef重命名
  8. typedef _Rb_tree_node_base* _Base_ptr;
  10. // 颜色
  11. _Rb_tree_color  _M_color;
  12. // 指向父亲
  13. _Base_ptr       _M_parent;
  14. // 指向左孩子
  15. _Base_ptr       _M_left;
  16. // 指向右孩子
  17. _Base_ptr       _M_right;
  19. // 求红黑树的最小节点
  20. static _Base_ptr
  21. _S_minimum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
  22. {
  23.     while (__x->_M_left != 0) __x = __x->_M_left;
  24.     return __x;
  25. }
  27. // 求红黑树最大节点
  28. static _Base_ptr
  29. _S_maximum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
  30. {
  31.     while (__x->_M_right != 0) __x = __x->_M_right;
  32.     return __x;
  33. }
  35. };

2.红黑树节点

红黑树节点继承自红黑树基类。

  1. template<typename _Val>
  2. struct _Rb_tree_node : public _Rb_tree_node_base
  3. {
  4.     typedef _Rb_tree_node<_Value>* _Link_type;//节点指针,指向数据节点
  5.     _Value _M_value_field;//节点数据域,即关键字
  6. };

3.红黑树迭代器

红黑树迭代器里面有一个红黑树基类成员，然后通过该成员进行迭代器的相关操作。同时，我们可以知道该迭代器属于bidirectional_iterator_tag。

里面也包含了萃取机相关需要的typedef。

  1. template<typename _Tp>
  2. struct _Rb_tree_iterator
  3. {
  4.     typedef _Tp  value_type;
  5.     typedef _Tp& reference;
  6.     typedef _Tp* pointer;
  8.     typedef bidirectional_iterator_tag iterator_category;
  9.     typedef ptrdiff_t                  difference_type;
  11.     typedef _Rb_tree_iterator<_Tp>        _Self;
  12.     typedef _Rb_tree_node_base::_Base_ptr _Base_ptr;
  13.     typedef _Rb_tree_node<_Tp>*           _Link_type;
  15.     _Base_ptr _M_node;
  16. };

获取数据

  1. reference
  2. operator*() const _GLIBCXX_NOEXCEPT
  3. { return *static_cast<_Link_type>(_M_node)->_M_valptr(); }
  5. pointer
  6. operator->() const _GLIBCXX_NOEXCEPT
  7. { return static_cast<_Link_type> (_M_node)->_M_valptr(); }

重载++操作符

  1. _Self&
  2. operator++() _GLIBCXX_NOEXCEPT
  3. {
  4.     _M_node = _Rb_tree_increment(_M_node);
  5.     return *this;
  6. }

而_Rb_tree_increment底层是local_Rb_tree_increment，如下实现：

  1. static _Rb_tree_node_base *
  2. local_Rb_tree_increment( _Rb_tree_node_base* __x ) throw ()
  3. {
  4.     if ( __x->_M_right != 0 )       /* 存在右子树,那么下一个节点为右子树的最小节点 */
  5.     {
  6.         __x = __x->_M_right;
  7.         while ( __x->_M_left != 0 )
  8.             __x = __x->_M_left;
  9.     }else  {                        
  10.         /* 不存在右子树,那么分为两种情况：自底往上搜索,当前节点为父节点的左孩子的时候,父节点就是后继节点； */
  11. /* 第二种情况:_x为header节点了,那么_x就是最后的后继节点. 简言之_x为最小节点且往上回溯,一直为父节点的右孩子,直到_x变为父节点,_y为其右孩子 */
  12.         _Rb_tree_node_base *__y = __x->_M_parent;
  13.         while ( __x == __y->_M_right )
  14.         {
  15.             __x = __y;
  16.             __y = __y->_M_parent;
  17.         }
  18.         if ( __x->_M_right != __y )
  19.             __x = __y;
  20.     }
  21.     return (__x);
  22. }

重载—操作符：

  1. _Self&
  2. operator--() _GLIBCXX_NOEXCEPT
  3. {
  4.     _M_node = _Rb_tree_decrement(_M_node);
  5.     return *this;
  6. }

同理，而_Rb_tree_decrement底层是local_Rb_tree_decrement，如下实现：

  1. static _Rb_tree_node_base *
  2. local_Rb_tree_decrement( _Rb_tree_node_base * __x )
  3. throw ()
  4. {
  5. /* header节点 */
  6.     if ( __x->_M_color ==
  7.          _S_red
  8.          && __x
  9.          ->_M_parent->_M_parent == __x )
  10.         __x = __x->_M_right;
  11.     else if ( __x->_M_left != 0 ) /* 左节点不为空,返回左子树中最大的节点 */
  12.     {
  13.         _Rb_tree_node_base *__y = __x->_M_left;
  14.         while ( __y->_M_right != 0 )
  15.             __y = __y->_M_right;
  16.         __x = __y;
  17.     }else  {
  18. /* 自底向上找到当前节点为其父节点的右孩子,那么父节点就是前驱节点 */
  19.         _Rb_tree_node_base *__y = __x->_M_parent;
  20.         while ( __x == __y->_M_left )
  21.         {
  22.             __x = __y;
  23.             __y = __y->_M_parent;
  24.         }
  25.         __x = __y;
  26.     }
  27.     return
  28.         (__x);
  29. }

重载==与!=操作符，直接判断节点指针是否相等。

  1. bool
  2. operator==(const _Self& __x) const _GLIBCXX_NOEXCEPT
  3. { return _M_node == __x._M_node; }
  5. bool
  6. operator!=(const _Self& __x) const _GLIBCXX_NOEXCEPT
  7. { return _M_node != __x._M_node; }

其他重要函数，黑节点统计：

  1. unsigned int
  2. _Rb_tree_black_count(const _Rb_tree_node_base *__node,
  3.                      const _Rb_tree_node_base *__root) throw() {
  4.     if (__node == 0)
  5.         return 0;
  6.     unsigned int __sum = 0;
  7.     do {
  8.         if (__node->_M_color == _S_black)
  9.             ++__sum;
  10.         if (__node == __root)
  11.             break;
  12.         __node = __node->_M_parent;
  13.     } while (1);
  14.     return __sum;
  15. }

后面来阐述最重要的插入操作。

4.红黑树操作

比较重要的是，里面使用节点基类来声明了一个指针。还包含了一个_Rb_tree_impl用来对红黑树初始化操作与内存管理操作。里面还包含了两种迭代器，一个rbtree，另一个是reverse，说明支持rbegin,rend操作。

  1. template<typename _Key, typename _Val, typename _KeyOfValue,
  2.            typename _Compare, typename _Alloc = allocator<_Val> >
  3. class _Rb_tree
  4. {
  6. protected:
  7.     typedef _Rb_tree_node_base*         _Base_ptr;
  9.  template<typename _Key_compare, 
  10.     bool _Is_pod_comparator = __is_pod(_Key_compare)>
  11.     struct _Rb_tree_impl : public _Node_allocator
  12.     {
  13.       _Key_compare      _M_key_compare;
  14.       _Rb_tree_node_base    _M_header;
  15.       size_type         _M_node_count; // Keeps track of size of tree.
  17.       _Rb_tree_impl()
  18.       : _Node_allocator(), _M_key_compare(), _M_header(),
  19.         _M_node_count(0)
  20.       { _M_initialize(); }
  22.       _Rb_tree_impl(const _Key_compare& __comp, const _Node_allocator& __a)
  23.       : _Node_allocator(__a), _M_key_compare(__comp), _M_header(),
  24.         _M_node_count(0)
  25.       { _M_initialize(); }
  27.     private:
  28.       void
  29.       _M_initialize()
  30.       {
  31.         this->_M_header._M_color = _S_red;
  32.         this->_M_header._M_parent = 0;
  33.         this->_M_header._M_left = &this->_M_header;
  34.         this->_M_header._M_right = &this->_M_header;
  35.       }  
  37.     };
  38. public: 
  39.     typedef _Rb_tree_iterator<value_type>       iterator;
  40.     typedef std::reverse_iterator<iterator>     reverse_iterator; 
  41. private:
  42. _Rb_tree_impl<_Compare> _M_impl;
  43. };

获取红黑树根节点、最左与最右节点

回到一开始的图：rbt.png。

  1. // 图中100 节点
  2.  _Base_ptr&
  3. _M_root() _GLIBCXX_NOEXCEPT
  4. { return this->_M_impl._M_header._M_parent; }
  6. // 图中most left标记
  7. _Base_ptr&
  8. _M_leftmost() _GLIBCXX_NOEXCEPT
  9. { return this->_M_impl._M_header._M_left; }
  12. // 图中most right标记
  13.  _Base_ptr&
  14. _M_rightmost() _GLIBCXX_NOEXCEPT
  15. { return this->_M_impl._M_header._M_right; }
  16.  _Link_type
  18.  // 图中begin()标记
  19. _M_begin() _GLIBCXX_NOEXCEPT
  20. { return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); }
  22. // 图中end()标记
  23. _Link_type
  24. _M_end() _GLIBCXX_NOEXCEPT
  25. { return reinterpret_cast<_Link_type>(&this->_M_impl._M_header); }

我们再看代码是不是非常清晰！

5.红黑树插入

5.1 旋转过程

左旋转是将该节点的右节点设置为它的父节点，该节点将变成刚才右节点的左孩子

直接看源码中的图与代码对比即可。

在tree.cc源码中实现函数为local_Rb_tree_rotate_left与local_Rb_tree_rotate_right。下面我们将源码进行剖析成比较容易理解的代码，具体见注释。大家会发现函数名与变量名与源码不同，是因为下面是当时自己实现的，但是不影响源码阅读，就直接拿来对比了。

  1. /**
  2. * 当前节点的左旋转过程
  3. * 将该节点的右节点设置为它的父节点，该节点将变成刚才右节点的左孩子
  4. * @param _x
  5. */
  6. //    _x                      _y
  7. //  /   \     左旋转         /  \
  8. // T1   _y   --------->   _x    T3
  9. //     / \              /   \
  10. //    T2 T3            T1   T2
  11. void leftRotate(Node *_x) {
  12.     // step1 处理_x的右孩子
  13.     // 右节点变为_x节点的父亲节点,先保存一下右节点
  14.     Node *_y = _x->right;
  15.     // T2变为node的右节点
  16.     _x->right = _y->left;
  17.     if (NULL != _y->left)
  18.         _y->left->parent = _x;
  20.     // step2 处理_y与父亲节点关系
  21.     _y->parent = _x->parent;      // 原来_x的父亲变为_y的父亲
  22.     // 说明原来_x为root节点,此时需要将_y设为新root节点
  23.     // 或者判断NULL == _y->parent
  24.     if (_x == root)
  25.         root = _y;
  26.     else if (_x == _x->parent->left)    // 原_x的父节点的左孩子连接新节点_y
  27.         _x->parent->left = _y;
  28.     else // 原_x的父节点的右孩子连接新节点_y
  29.         _x->parent->right = _y;
  31.     // step3 处理_x与_y关系
  32.     _y->left = _x;      // _y的左孩子为_x
  33.     _x->parent = _y;    // _x的父亲是_y
  34. }

同理，右旋转如下：

  1. //        _x                      _y
  2. //      /   \     右旋转         /  \
  3. //     _y    T2 ------------->  T0  _x
  4. //    /  \                         /  \
  5. //   T0  T1                       T1  T2
  6. void rightRotate(Node *_x) {
  7.     // step1 处理_x的左孩子
  8.     // 左节点变为_x节点的父亲节点,先保存一下左节点
  9.     Node *_y = _x->left;
  10.     // T1变为_x的左孩子
  11.     _x->left = _y->right;
  12.     if (NULL != _y->right)
  13.         _y->right->parent = _x;
  15.     // step2 处理_y与父节点之间的关系
  16.     // 或者判断_x->parent==NULL
  17.     if (_x == root)
  18.         root = _y;
  19.     else if (_x == _x->parent->right)
  20.         _x->parent->right = _y;
  21.     else
  22.         _x->parent->left = _y;
  24.     // step3 处理_x与_y关系
  25.     _y->right = _x;     // _y的右孩子为_x
  26.     _x->parent = _y;    // _x的父亲是_y
  27. }

case 1.1: 父节点为红色且其叔叔节点也为红色，则将父亲、叔叔置为黑色，祖父置为红色。

rb_1.png

case 1.2 若无叔叔节点或者其叔叔节点为黑色分为下面两种：

情况1.2.1：x的叔叔节点y是黑色且x是一个右孩子

rb1.2.1.png

情况1.2.2：x的叔叔节点y是黑色且x是一个左孩子

rb1.2.2.png

对应源代码中：

  1. _Rb_tree_node_base *const __y = __xpp->_M_right;    // 得到叔叔节点
  2. if (__y && __y->_M_color == _S_red)     // case1: 叔叔节点存在，且为红色
  3. {
  4.     /**
  5.         * 解决办法是：颜色翻转，父亲与叔叔的颜色都变为黑色,祖父节点变为红色,然后当前节点设为祖父，依次网上来判断是否破坏了红黑树性质
  6.         */
  7.     __x->_M_parent->_M_color = _S_black;    // 将其父节点改为黑色
  8.     __y->_M_color = _S_black;               // 将其叔叔节点改为黑色
  9.     __xpp->_M_color = _S_red;               // 将其祖父节点改为红色
  10.     __x = __xpp;                            // 修改_x,往上回溯
  11. } else {        // 无叔叔或者叔叔为黑色
  12.     if (__x == __x->_M_parent->_M_right) {          // 当前节点为父亲节点的右孩子
  13.         __x = __x->_M_parent;
  14.         local_Rb_tree_rotate_left(__x, __root);     // 以父节点进行左旋转
  15.     }
  16.     // 旋转之后,节点x变成其父节点的左孩子
  17.     __x->_M_parent->_M_color = _S_black;            // 将其父亲节点改为黑色
  18.     __xpp->_M_color = _S_red;                       // 将其祖父节点改为红色
  19.     local_Rb_tree_rotate_right(__xpp, __root);      // 以祖父节点右旋转
  20. }

另外一个是上述对称过程：

case 2.1: 父节点为红色且其叔叔节点也为红色，则将父亲、叔叔置为黑色，祖父置为红色。

rb2.1.png

case 2.2 若无叔叔节点或者其叔叔节点为黑色

rb2.2.1.png

情况2.2.1：x的叔叔节点y是黑色且x是一个左孩子

rb2.2.2.png

  1. _Rb_tree_node_base *const __y = __xpp->_M_left; // 保存叔叔节点
  2. if (__y && __y->_M_color == _S_red) {       // 叔叔节点存在且为红色
  3.     __x->_M_parent->_M_color = _S_black;    // 父亲节点改为黑色
  4.     __y->_M_color = _S_black;               // 祖父节点改为红色
  5.     __xpp->_M_color = _S_red;
  6.     __x = __xpp;
  7. } else {        // 若无叔叔节点或者其叔叔节点为黑色
  8.     if (__x == __x->_M_parent->_M_left) {   // 当前节点为父亲节点的左孩子
  9.         __x = __x->_M_parent;
  10.         local_Rb_tree_rotate_right(__x, __root);    // 以父节点右旋转
  11.     }
  12.     __x->_M_parent->_M_color = _S_black;        // 父节点置为黑色
  13.     __xpp->_M_color = _S_red;                   // 祖父节点置为红色
  14.     local_Rb_tree_rotate_left(__xpp, __root);   // 左旋转
  15. }

_Rb_tree_insert_and_rebalance完整解析：

  1. void
  2. _Rb_tree_insert_and_rebalance(const bool __insert_left,
  3.                               _Rb_tree_node_base *__x,
  4.                               _Rb_tree_node_base *__p,
  5.                               _Rb_tree_node_base &__header) throw() {
  6.     _Rb_tree_node_base * &__root = __header._M_parent;
  8.     // Initialize fields in new node to insert.
  9.     __x->_M_parent = __p;
  10.     __x->_M_left = 0;
  11.     __x->_M_right = 0;
  12.     __x->_M_color = _S_red;
  14.     // 处理__header部分
  15.     // Insert.
  16.     // Make new node child of parent and maintain root, leftmost and
  17.     // rightmost nodes.
  18.     // N.B. First node is always inserted left.
  19.     if (__insert_left) {
  20.         __p->_M_left = __x; // also makes leftmost = __x when __p == &__header
  22.         if (__p == &__header) {
  23.             __header._M_parent = __x;
  24.             __header._M_right = __x;
  25.         } else if (__p == __header._M_left)
  26.             __header._M_left = __x; // maintain leftmost pointing to min node
  27.     } else {
  28.         __p->_M_right = __x;
  30.         if (__p == __header._M_right)
  31.             __header._M_right = __x; // maintain rightmost pointing to max node
  32.     }
  34.  // Rebalance.
  35.     while (__x != __root
  36.            && __x->_M_parent->_M_color == _S_red)   // 若新插入节点不是为RB-Tree的根节点，且其父节点color属性也是红色,即违反了性质4.
  37.     {
  38.         _Rb_tree_node_base *const __xpp = __x->_M_parent->_M_parent;        // 祖父节点
  40.         if (__x->_M_parent == __xpp->_M_left)   // 父亲是祖父节点的左孩子
  41.         {
  42.             _Rb_tree_node_base *const __y = __xpp->_M_right;    // 得到叔叔节点
  43.             if (__y && __y->_M_color == _S_red)     // case1: 叔叔节点存在，且为红色
  44.             {
  45.                 /**
  46.                  * 解决办法是：颜色翻转，父亲与叔叔的颜色都变为黑色,祖父节点变为红色,然后当前节点设为祖父，依次网上来判断是否破坏了红黑树性质
  47.                  */
  48.                 __x->_M_parent->_M_color = _S_black;    // 将其父节点改为黑色
  49.                 __y->_M_color = _S_black;               // 将其叔叔节点改为黑色
  50.                 __xpp->_M_color = _S_red;               // 将其祖父节点改为红色
  51.                 __x = __xpp;                            // 修改_x,往上回溯
  52.             } else {        // 无叔叔或者叔叔为黑色
  53.                 if (__x == __x->_M_parent->_M_right) {          // 当前节点为父亲节点的右孩子
  54.                     __x = __x->_M_parent;
  55.                     local_Rb_tree_rotate_left(__x, __root);     // 以父节点进行左旋转
  56.                 }
  57.                 // 旋转之后,节点x变成其父节点的左孩子
  58.                 __x->_M_parent->_M_color = _S_black;            // 将其父亲节点改为黑色
  59.                 __xpp->_M_color = _S_red;                       // 将其祖父节点改为红色
  60.                 local_Rb_tree_rotate_right(__xpp, __root);      // 以祖父节点右旋转
  61.             }
  62.         } else {        // 父亲是祖父节点的右孩子
  63.             _Rb_tree_node_base *const __y = __xpp->_M_left; // 保存叔叔节点
  64.             if (__y && __y->_M_color == _S_red) {       // 叔叔节点存在且为红色
  65.                 __x->_M_parent->_M_color = _S_black;    // 父亲节点改为黑色
  66.                 __y->_M_color = _S_black;               // 祖父节点改为红色
  67.                 __xpp->_M_color = _S_red;
  68.                 __x = __xpp;
  69.             } else {        // 若无叔叔节点或者其叔叔节点为黑色
  70.                 if (__x == __x->_M_parent->_M_left) {   // 当前节点为父亲节点的左孩子
  71.                     __x = __x->_M_parent;
  72.                     local_Rb_tree_rotate_right(__x, __root);    // 以父节点右旋转
  73.                 }
  74.                 __x->_M_parent->_M_color = _S_black;        // 父节点置为黑色
  75.                 __xpp->_M_color = _S_red;                   // 祖父节点置为红色
  76.                 local_Rb_tree_rotate_left(__xpp, __root);   // 左旋转
  77.             }
  78.         }
  79.     }
  80.     //若新插入节点为根节点,则违反性质2
  81.     //只需将其重新赋值为黑色即可
  82.     __root->_M_color = _S_black;
  83. }

5.2插入总结

根据上述插入过程与源码分析，我们得出下面三种：假设P代码父亲节点，N代表当前新插入节点，U代表叔叔节点，G代表祖父节点。

case 1:U为红色，P、N也都为红色，则可以通过改变颜色，自底向上递归调整，下次N就变味G，往上判断即可。如果碰巧将根节点染成了红色, 可以在算法的最后强制root改为黑。

1_1.png

case 2:U为黑色，考虑N是P的左孩子还是右孩子。

case2.1 如果是右孩子,先进行左旋转，再进入下一种情况。

2_1.png

case2.2 可能是上述情况变化而来，但不一定是！策略为：右旋转，改变颜色。

rb2_2.png

经过上述源码的分析得知，红黑树插入为镜像变换，另一种情况刚好相反。

删除操作，比较复杂，这里就暂时没分析了，后面补上。。。

6.使用

前面说了那么多，如何使用呢？

引入头文件：

  1. #include<map>或者<set>

类定义：

  1. _Rb_tree<int, int, _Identity<int>, less<int>> itree;

然后调用相应函数即可。