• STL 红黑树源码分析

    最近我们项目上因为STL的使用出了很多问题，尤其是对map的使用。map的底层与set一样同为STL红黑树，所以抽空将STL红黑树的源代码再学习学习。

    1. STL红黑树的节点

    STL的红黑树也属于红黑树（红黑树是一种自平衡的二叉查找树），所以具备普通红黑树的5个特性：

    1. 每个节点或是红色的或是黑色的
    2. 根节点是黑色的
    3. 每个叶节点（NULL）是黑色的
    4. 如果一个节点是红色的，则它的两个孩子节点都是黑色的（从每个叶子到根的所有路径上不能有两个连续的红色节点）
    5. 对每个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点

    STL的红黑树和普通的红黑树相比较，多了以下两点特性：

    1. header不仅指向root，也指向红黑树的最左节点，以便用常数时间实现begin()，并且也指向红黑树的最右边节点，以便 set相关泛型算法（如set_union等等）可以有线性时间表现
    2. 当要删除的节点有两个子节点时，其后继节点连接到其位置，而不是被复制，因此，唯一使无效的迭代器是引用已删除节点的迭代器

    可以看出，相比于普通的红黑树多了一个header节点，并且为红色。如下图所示，普通的红黑树是以100节点开始的，而STL的红黑树以header节点开始。迭代器的begin指向红黑树根节点，也就是header节点的父亲，而end指向header节点。

     注：此处的begin()和end()并不是指内置函数，而是指迭代器。begin()指向最左节点，图中标注的有错

    STL红黑树的数据存储类型为链式存储，因此存储单元为节点。因此，我们先看一下节点的定义。

    如下所示为红黑树节点基类_Rb_tree_node_base的源代码，可以看出定义了颜色标记_Rb_tree_color。基类中分别声明了_M_left、_M_right、_M_parent三个指针成员同时声明了一个颜色标记常量_M_color成员。

    1. // 颜色标记
    2. enum _Rb_tree_color { _S_red = false, _S_black = true };
    3.  
    4. // 基类，用来定义一个节点的属性
    5. struct _Rb_tree_node_base
    6. {
    7.     // typedef重命名
    8.     typedef _Rb_tree_node_base* _Base_ptr;
    9.     typedef const _Rb_tree_node_base* _Const_Base_ptr;
    10.  
    11.     // 节点的属性，颜色、指向父节点的指针、指向左右孩子节点的指针
    12.     _Rb_tree_color  _M_color;  // 颜色
    13.     _Base_ptr       _M_parent; // 指向父亲
    14.     _Base_ptr       _M_left;   // 指向左孩子
    15.     _Base_ptr       _M_right;  // 指向右孩子
    16.     
    17.     // 求节点__x的最小节点
    18.     static _Base_ptr
    19.     _S_minimum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
    20.     {
    21.         while (__x->_M_left != 0) __x = __x->_M_left;
    22.         return __x;
    23.     }
    24.  
    25.     // 求节点__x的最大节点
    26.     static _Base_ptr
    27.     _S_maximum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
    28.     {
    29.         while (__x->_M_right != 0) __x = __x->_M_right;
    30.         return __x;
    31.     }
    32. };

    同时，节点基类里面还定义了两个重要的函数，分别是获取红黑树中__x节点的最小节点的函数_S_minimum与最大节点的函数_S_maximum。

    由于STL红黑树是有序的，所以需要一个比较函数对象，该对象类型定义如下

    1. template<typename _Key_compare>
    2.   struct _Rb_tree_key_compare
    3.   {
    4.       // 成员变量就是我们提供给红黑树的仿函数对象
    5.       _Key_compare    _M_key_compare;
    6.   }

    当我们初始化一个空的红黑树对象的时候，也会初始化一个节点出来，该节点就是header节点，header节点的定义如下：

    1. // Helper type to manage
    2. // default initialization of node count and header.
    3. struct _Rb_tree_header
    4. {
    5.     _Rb_tree_node_base  _M_header; // 不存储数据
    6.     size_t    _M_node_count; // 用来统计红黑树中节点的数量
    7.     _Rb_tree_header()
    8.     {
    9.         _M_header._M_color = _S_red; // header节点一定是红色的
    10.         _M_reset();
    11.     }
    12.     void _M_reset()
    13.     {
    14.         _M_header._M_parent = 0;
    15.         _M_header._M_left = &_M_header;
    16.         _M_header._M_right = &_M_header;
    17.         _M_node_count = 0;
    18.     }
    19. }

    红黑树节点_Rb_tree_node继承自红黑树基类_Rb_tree_node_base。可以计算一下一个红黑树节点的大小为：4个指针+一个枚举+_Val。

    1. template<typename _Val>
    2. struct _Rb_tree_node : public _Rb_tree_node_base
    3. {
    4.     // 定义了一个节点类型的指针
    5.     typedef _Rb_tree_node<_Value>* _Link_type;
    6.     // 节点数据域，即节点中存储的值
    7.     _Val _M_value_field;
    8. };

    相关视频推荐

    源码阅读：STL 红黑树、散列表的实现

    5种红黑树的用途，从应用到内核场景的优缺点

    学习地址：c/c++ linux服务器开发/后台架构师

    需要C/C++ Linux服务器架构师学习资料加qun812855908获取（资料包括C/C++，Linux，golang技术，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK，ffmpeg等），免费分享

    2. STL红黑树

    STL红黑树的源代码如下所示，是一个模板类，_Key是key的类型，_Val是value的类型，_KeyOfValue是对的类型，_Campare是比较函数对象类型，_Alloc是空间配置器的类型，默认为标准的allocator分配器。

    包含了一个_Rb_tree_impl类型的成员变量_M_impl，对红黑树进行初始化操作与内存管理操作。_Rb_tree_impl继承了header节点_Rb_tree_header。

    STL红黑树包含两种迭代器分别为_Rb_tree_iterator和std::reverse_iterator，说明STL红黑树支持rbegin和rend操作。

    下面我们对rb-tree的源代码逐步进行解析。

    1. template<typename _Key, typename _Val, typename _KeyOfValue,
    2.            typename _Compare, typename _Alloc = allocator<_Val> >
    3. class _Rb_tree
    4. {
    5. public:
    6.     typedef _Key                  key_type;
    7.     typedef _Val                  value_type;
    8.     typedef value_type*           pointer;
    9.     typedef const value_type*     const_pointer;
    10.     typedef value_type&           reference;
    11.     typedef const value_type&     const_reference;
    12.     typedef size_t                size_type;
    13.     typedef ptrdiff_t             difference_type;
    14.     typedef _Alloc                allocator_type;
    15.     // 将节点类型_Rb_tree_node<_Val>与空间配置器_Alloc绑定
    16.     // 空间配置器具体为配置节点空间的_Node_allocator
    17.     typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
    18.     rebind<_Rb_tree_node<_Val> >::other _Node_allocator;
    19.     // 空间配置器萃取机为具体配置器_Node_allocator的萃取机
    20.     typedef __gnu_cxx::__alloc_traits<_Node_allocator> _Alloc_traits;
    21. protected:
    22.     typedef _Rb_tree_node_base*     _Base_ptr;  // 节点基类指针
    23.     typedef _Rb_tree_node<_Val>*    _Link_type; // 节点指针
    24.    
    25. protected:
    26.     // 包含一个_Rb_tree_impl对象，因此一个红黑树对象至少包含
    27.     // 一个header节点对象
    28.     // 一个具体配置器_Node_allocator的对象
    29.     _Rb_tree_impl<_Compare> _M_impl;
    30.  
    31.     // _Rb_tree_impl的定义如下，包含一个header节点
    32.     template<typename _Key_compare,
    33.        bool _Is_pod_comparator = __is_pod(_Key_compare)>
    34.     struct _Rb_tree_impl : public _Node_allocator
    35.                          , public _Rb_tree_key_compare<_Key_compare>
    36.                          , public _Rb_tree_header
    37.     {
    38.         typedef _Rb_tree_key_compare<_Key_compare> _Base_key_compare;
    39.         // 构造函数如下
    40.         _Rb_tree_impl() : _Node_allocator()
    41.         {}
    42.         
    43.         _Rb_tree_impl(const _Rb_tree_impl& __x)
    44.         : _Node_allocator(_Alloc_traits::_S_select_on_copy(__x))
    45.         , _Base_key_compare(__x._M_key_compare)
    46.         {}
    47.     };
    48. public:
    49.     typedef _Rb_tree_iterator<value_type>       iterator;
    50.     typedef std::reverse_iterator<iterator>     reverse_iterator;
    51.     
    52.     // 重要的函数
    53.     // _M_get_Node_allocator用来获取红黑树节点对象的空间配置器对象
    54.     _Node_allocator& _M_get_Node_allocator()
    55.     { return this->_M_impl; }
    56.     // 为节点对象分配空间，返回值为内存地址，每次分配一个空间
    57.     _Link_type _M_get_node()
    58.     { return _Alloc_traits::allocate(_M_get_Node_allocator(), 1); }
    59.     // 空间释放函数，将节点指针传进去
    60.     void _M_put_node(_Link_type __p)
    61.     { _Alloc_traits::deallocate(_M_get_Node_allocator(), __p, 1); }
    62.     // 构造节点的底层函数
    63.     template<typename... _Args>
    64.     void _M_construct_node(_Link_type __node, _Args&&... __args)
    65.     {
    66.         ::new(__node) _Rb_tree_node<_Val>;
    67.         _Alloc_traits::construct(_M_get_Node_allocator(),
    68.                      __node->_M_valptr(),
    69.                      std::forward<_Args>(__args)...);
    70.     }
    71.     // 构造节点对象，调用_M_construct_node
    72.     template<typename... _Args>
    73.     _Link_type _M_create_node(_Args&&... __args)
    74.     {
    75.         _Link_type __tmp = _M_get_node();
    76.         _M_construct_node(__tmp, std::forward<_Args>(__args)...);
    77.         return __tmp;
    78.     }
    79.     // 节点对象的析构函数
    80.     void _M_destroy_node(_Link_type __p)
    81.     {
    82.         // 释放内容
    83.         _Alloc_traits::destroy(_M_get_Node_allocator(), __p->_M_valptr());
    84.         // 释放内存
    85.         __p->~_Rb_tree_node<_Val>();
    86.     }
    87.     // 红黑树的构造函数
    88.     _Rb_tree() = default;
    89.     _Rb_tree(const _Compare& __comp
    90.             , const allocator_type& __a = allocator_type())
    91.     : _M_impl(__comp, _Node_allocator(__a)) { }
    92.     // 红黑树的析构函数
    93.     ~_Rb_tree()
    94.     { _M_erase(_M_begin()); }
    95. };

    还有如下操作函数：

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

    3. STL红黑树迭代器

    STL红黑树也自定义了一个迭代器_Rb_tree_iterator。

    1. template<typename _Tp>
    2. struct _Rb_tree_iterator
    3. {
    4.     typedef _Tp  value_type;
    5.     typedef _Tp& reference;
    6.     typedef _Tp* pointer;
    7.     typedef bidirectional_iterator_tag iterator_category;
    8.     typedef ptrdiff_t                  difference_type;
    9.  
    10.     typedef _Rb_tree_iterator<_Tp>        _Self;
    11.     typedef _Rb_tree_node_base::_Base_ptr _Base_ptr;
    12.     typedef _Rb_tree_node<_Tp>*           _Link_type;
    13.     // 迭代器是一个指向红黑树节点的指针
    14.     _Base_ptr _M_node;
    15. };

    重载了*操作符和->操作符来获取节点中存储的数据

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

    迭代器类重载的++操作符，自增（自底而上）的时候调用。本质是调用函数_Rb_tree_increment

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

    同理，也重载了--操作符，调用_Rb_tree_decrement函数

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

    同理，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.   /* 左节点不为空,返回左子树中最大的节点 */
    12.   else if ( __x->_M_left != 0 )
    13.   {
    14.     _Rb_tree_node_base *__y = __x->_M_left;
    15.     while ( __y->_M_right != 0 )
    16.       __y = __y->_M_right;
    17.     __x = __y;
    18.   }else  {
    19. /* 自底向上找到当前节点为其父节点的右孩子,那么父节点就是前驱节点 */
    20.     _Rb_tree_node_base *__y = __x->_M_parent;
    21.     while ( __x == __y->_M_left )
    22.     {
    23.       __x  = __y;
    24.       __y  = __y->_M_parent;
    25.     }
    26.     __x = __y;
    27.   }
    28.   return
    29.     (__x);
    30. }

    也重载了==与!=操作符，用来判断节点指针是否相等。

    1. bool
    2. operator==(const _Self& __x) const _GLIBCXX_NOEXCEPT
    3. { return _M_node == __x._M_node; }
    4.  
    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.STL红黑树的自平衡

    我们在一开始就说明了STL红黑树也要满足普通红黑树的规则，这些规则才保证了红黑树的自平衡。红黑树从根到叶子的最长路径不会超过最短路径的2倍。

    当插入节点或者删除节点的时候，红黑树的规则可能会被打破，这时候就需要做出一些调整，调整的方法有变色和旋转两种。旋转又包含左旋转和右旋转两种形式。

    变色

    为了重新符合红黑树的规则，尝试把红色节点变为黑色，或者把黑色节点变为红色。

    如下所示为变色的场景：

     

     

     STL的源代码如下所示：

    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. }

     

     

    代码如下：

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

    左旋转

    逆时针旋转红黑树的两个节点，使得父节点被自己的右孩子取代，而自己成为自己的左孩子。

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

    右旋转

    顺时针旋转红黑树的两个节点，使得父节点被自己的左孩子取代，而自己成为自己的右孩子。

    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;
    14.  
    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;
    23.  
    24.     // step3 处理_x与_y关系
    25.     _y->right = _x;     // _y的右孩子为_x
    26.     _x->parent = _y;    // _x的父亲是_y
    27. }

    STL红黑树会在插入和删除节点的时候进行自平衡操作，底层调用的是
    _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;
    7.  
    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;
    13.  
    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
    21.  
    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;
    29.  
    30.         if (__p == __header._M_right)
    31.             __header._M_right = __x; // maintain rightmost pointing to max node
    32.     }
    33.  
    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;        // 祖父节点
    39.  
    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. }

    map和set其实都是对rb-tree的包装，操作函数最终都是调用rb-tree提供的操作。map和set的增删改查，其实就是rb-tree的增删改查，所以掌握rb-tree的底层原理即可。这篇文章的内容已经足够多了，下一篇我会仔细分析一下rb-tree的增删改查，如果不理解这其中的细节，会导致我们在使用map和set时踩到很多陷阱。

  • 相关阅读:
    C2. k-LCM (hard version)-Codeforces Round #708 (Div. 2)
    破解WPA2-PSK加密
    java项目-第128期ssm+oracle的宿舍管理平台-java毕业设计_计算机毕业设计
    “低代码技术：数字化工厂的加速器与智能制造的桥梁“
    华为机试 - 城市聚集度
    基础组件-流量回放(全链路流量回放预研)
    Android安装过程二 系统进程中PackageInstallerSession对象的创建
    「全球数字经济大会」登陆 N 世界，融云提供通信云服务支持
    【c++】信号处理--signal、raise、sigaction的介绍
    【JVM--StringTable字符串常量池】
  • 原文地址：https://blog.csdn.net/qq_40989769/article/details/126526948