sgi_stl源码学习，解析set、map背后的_Rb_tree源码(未完待续)

参考资料：
chatGPT先推荐的《算法导论》第13章，不过我手头没有这本书。
https://www.cnblogs.com/skywang12345/p/3245399.html （chatGPT推荐的）
外加sgi stl源码。个人觉得通过源码理解算法接地气一些。
https://blog.csdn.net/v_JULY_v/article/details/6105630
https://sedgewick.io/wp-content/themes/sedgewick/papers/2008LLRB.pdf
https://github.com/julycoding/The-Art-Of-Programming-By-July-2nd/blob/master/ebook/zh/03.01.md

首先红黑树节点的属性红黑，不仅仅是概念上的，源码中用bool去存储了

typedef bool _Rb_tree_Color_type;
const _Rb_tree_Color_type _S_rb_tree_red = false;
const _Rb_tree_Color_type _S_rb_tree_black = true;

基础node的定义如下，实际就是将数据和树分离，base定义的只是树结构，实际要存储的值在_Rb_tree_node 中的_M_value_field中

struct _Rb_tree_node_base{
  typedef _Rb_tree_Color_type _Color_type;
  typedef _Rb_tree_node_base* _Base_ptr;
  _Color_type _M_color; 
  _Base_ptr _M_parent; //父节点
  _Base_ptr _M_left; //左节点
  _Base_ptr _M_right; //右节点
  static _Base_ptr _S_minimum(_Base_ptr __x)  {
    while (__x->_M_left != 0) __x = __x->_M_left;//找到子树的最小节点，实际就是递归左节点
    return __x;
  }
  static _Base_ptr _S_maximum(_Base_ptr __x)  {
    while (__x->_M_right != 0) __x = __x->_M_right;//找到子树的最大节点
    return __x;
  }
};

template <class _Value>
struct _Rb_tree_node : public _Rb_tree_node_base{
  typedef _Rb_tree_node<_Value>* _Link_type;
  _Value _M_value_field;//加上数据组成实际的tree node
};

以上继承没有虚函数，所以也没有虚函数表的开销。模板的继承成本待调查。

红黑树的迭代器定义，_M_increment右移一个节点，_M_decrement左移一个节点。父节点大于左节点，小于右节点。

struct _Rb_tree_base_iterator{
  typedef _Rb_tree_node_base::_Base_ptr _Base_ptr;
  typedef bidirectional_iterator_tag iterator_category;
  typedef ptrdiff_t difference_type;
  _Base_ptr _M_node;
  void _M_increment()  {
    if (_M_node->_M_right != 0) {
      _M_node = _M_node->_M_right;
      while (_M_node->_M_left != 0)
        _M_node = _M_node->_M_left;
    }
    else {
      _Base_ptr __y = _M_node->_M_parent;
      while (_M_node == __y->_M_right) {//当前节点是其父节点的右子节点，那么就继续向上查找
        _M_node = __y;
        __y = __y->_M_parent;
      }//如果当前节点是其父节点的左子节点，则说明父节点就是当前节点的后继节点。
      if (_M_node->_M_right != __y)
        _M_node = __y;
    }
  }
  void _M_decrement()  {
    if (_M_node->_M_color == _S_rb_tree_red &&
        _M_node->_M_parent->_M_parent == _M_node)//只有根节点满足此条件
      _M_node = _M_node->_M_right;
    else if (_M_node->_M_left != 0) {//左子树非空时，左子树的最右节点就是减一的节点
      _Base_ptr __y = _M_node->_M_left;
      while (__y->_M_right != 0)
        __y = __y->_M_right;
      _M_node = __y;
    }
    else {
      _Base_ptr __y = _M_node->_M_parent;
      while (_M_node == __y->_M_left) {
        _M_node = __y;
        __y = __y->_M_parent;
      }
      _M_node = __y;
    }
  }
};

上图描述应该改下：对Y进行右旋，意味着"将Y变成一个右节点"。

对x进行左旋，意味着，将“x的右孩子”设为“x的父亲节点”；即，将 x变成了一个左节点(x成了为z的左孩子)！。 因此，左旋中的“左”，意味着“被旋转的节点将变成一个左节点”。
对x进行右旋，意味着，将“x的左孩子”设为“x的父亲节点”；即，将 x变成了一个右节点(x成了为y的右孩子)！ 因此，右旋中的“右”，意味着“被旋转的节点将变成一个右节点”。

inline void 
_Rb_tree_rotate_left(_Rb_tree_node_base* __x, _Rb_tree_node_base*& __root)
{
  _Rb_tree_node_base* __y = __x->_M_right;
  __x->_M_right = __y->_M_left;
  if (__y->_M_left !=0)
    __y->_M_left->_M_parent = __x;
  __y->_M_parent = __x->_M_parent;

  if (__x == __root)
    __root = __y;
  else if (__x == __x->_M_parent->_M_left)
    __x->_M_parent->_M_left = __y;
  else
    __x->_M_parent->_M_right = __y;
  __y->_M_left = __x;
  __x->_M_parent = __y;
}

inline void 
_Rb_tree_rotate_right(_Rb_tree_node_base* __x, _Rb_tree_node_base*& __root)
{
  _Rb_tree_node_base* __y = __x->_M_left;
  __x->_M_left = __y->_M_right;
  if (__y->_M_right != 0)
    __y->_M_right->_M_parent = __x;
  __y->_M_parent = __x->_M_parent;

  if (__x == __root)
    __root = __y;
  else if (__x == __x->_M_parent->_M_right)
    __x->_M_parent->_M_right = __y;
  else
    __x->_M_parent->_M_left = __y;
  __y->_M_right = __x;
  __x->_M_parent = __y;
}
inline void 
_Rb_tree_rebalance(_Rb_tree_node_base* __x, _Rb_tree_node_base*& __root);//_M_insert之后调用
inline _Rb_tree_node_base*
_Rb_tree_rebalance_for_erase(_Rb_tree_node_base* __z,
                             _Rb_tree_node_base*& __root,
                             _Rb_tree_node_base*& __leftmost,
                             _Rb_tree_node_base*& __rightmost);

RB-INSERT(T, z)  
01  y ← nil[T]                        // 新建节点“y”，将y设为空节点。
02  x ← root[T]                       // 设“红黑树T”的根节点为“x”
03  while x ≠ nil[T]                  // 找出要插入的节点“z”在二叉树T中的位置“y”
04      do y ← x                      
05         if key[z] < key[x]  
06            then x ← left[x]  
07            else x ← right[x]  
08  p[z] ← y                          // 设置 “z的父亲” 为 “y”
09  if y = nil[T]                     
10     then root[T] ← z               // 情况1：若y是空节点，则将z设为根
11     else if key[z] < key[y]        
12             then left[y] ← z       // 情况2：若“z所包含的值” < “y所包含的值”，则将z设为“y的左孩子”
13             else right[y] ← z      // 情况3：(“z所包含的值” >= “y所包含的值”)将z设为“y的右孩子” 
14  left[z] ← nil[T]                  // z的左孩子设为空
15  right[z] ← nil[T]                 // z的右孩子设为空。至此，已经完成将“节点z插入到二叉树”中了。
16  color[z] ← RED                    // 将z着色为“红色”
17  RB-INSERT-FIXUP(T, z)             // 通过RB-INSERT-FIXUP对红黑树的节点进行颜色修改以及旋转，让树T仍然是一颗红黑树

RB-INSERT-FIXUP(T, z)
01 while color[p[z]] = RED                                                  // 若“当前节点(z)的父节点是红色”，则进行以下处理。
02     do if p[z] = left[p[p[z]]]                                           // 若“z的父节点”是“z的祖父节点的左孩子”，则进行以下处理。
03           then y ← right[p[p[z]]]                                        // 将y设置为“z的叔叔节点(z的祖父节点的右孩子)”
04                if color[y] = RED                                         // Case 1条件：叔叔是红色
05                   then color[p[z]] ← BLACK                    ▹ Case 1   //  (01) 将“父节点”设为黑色。
06                        color[y] ← BLACK                       ▹ Case 1   //  (02) 将“叔叔节点”设为黑色。
07                        color[p[p[z]]] ← RED                   ▹ Case 1   //  (03) 将“祖父节点”设为“红色”。
08                        z ← p[p[z]]                            ▹ Case 1   //  (04) 将“祖父节点”设为“当前节点”(红色节点)
09                   else if z = right[p[z]]                                // Case 2条件：叔叔是黑色，且当前节点是右孩子
10                           then z ← p[z]                       ▹ Case 2   //  (01) 将“父节点”作为“新的当前节点”。
11                                LEFT-ROTATE(T, z)              ▹ Case 2   //  (02) 以“新的当前节点”为支点进行左旋。
12                           color[p[z]] ← BLACK                 ▹ Case 3   // Case 3条件：叔叔是黑色，且当前节点是左孩子。(01) 将“父节点”设为“黑色”。
13                           color[p[p[z]]] ← RED                ▹ Case 3   //  (02) 将“祖父节点”设为“红色”。
14                           RIGHT-ROTATE(T, p[p[z]])            ▹ Case 3   //  (03) 以“祖父节点”为支点进行右旋。
15        else (same as then clause with "right" and "left" exchanged)      // 若“z的父节点”是“z的祖父节点的右孩子”，将上面的操作中“right”和“left”交换位置，然后依次执行。
16 color[root[T]] ← BLACK

未完，待续