参考资料：
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
未完，待续