源码剖析：STL中红黑树（RB-tree）
本文深入解析红黑树(RB-tree)的实现原理与数据结构设计。首先介绍红黑树的五大规则：根黑、不红红、黑路同等特性，并分析了插入节点时的三种情况（根节点、红叔叔、黑叔叔）及对应的旋转操作。对删除操作也分情况讨论，包括单子节点和无子节点场景。详细阐述了红黑树的节点结构设计、迭代器实现（双向迭代器），以及底层数据结构成员定义。最后探讨了红黑树的构造方式（空树/复制）和关键操作：insert_unique（不重复插入）、insert_equal（允许重复）和find查找方法
前言
在文章《STL源码刨析：树的导览》中，曾简单的对树的结构，二叉搜索树和平衡二叉搜索树进行简单的讲解。而本章将重点对红黑树进行讲解，并为后续的set和map容器打下基础
RB-tree的简单介绍
红黑树也是一种平衡二叉搜索树，而在满足平衡二叉搜索树的基础上，红黑树还需要符合以下规则：
1.RB-tree的每一个节点不是黑色就是红色
2.RB-tree的根节点为黑色
3.如果在上一层节点中，其节点的颜色为红色，那该节点的子节点颜色必须为黑色（如果上一层节点颜色为黑色，则该节点的子节点颜色可以为黑色或者红色）
4.RB-tree满足从任意一个节点到叶子节点1的路径中，所含的黑色节点的数量相同
5.新插入的节点的父节点必须为黑色，而插入节点的颜色必须为红色
为了方便理解RB-tree的特点，可以参考下图：
图1.红黑树示例
为了方便辨别一棵平衡二叉搜索树是否是红黑树，基于图1还是不够准确的，应此我们还需要在图1的基础上把空节点画出来并标记为黑色，以确保符合红黑树的第四条规则，具体如下：
图2.红黑树完整示例
在针对图2的表示中，我们还可以发现以下规律：
1.RB-tree中最长路径不超过最短路径的两倍
2.RB-tree的最短路径中的节点必为全黑，最长路径的节点必为一黑一红
3.RB-tree的中的任意节点的左右子树高度相差不超过2，而平衡二叉搜索树为1（因为红黑树的平衡性比平衡二叉搜索树的平衡性弱，当搜寻节点的平均效率几乎相等）
PS：网传一个关于红黑树的口诀：左根右（代表红黑树为平衡二叉搜索树（左<根<右）），根叶黑（根节点和叶子节点为黑色），不红红（两个子节点的颜色不连续为红色），黑路同（从任意一个节点到叶子节点1的路径中，所含的黑色节点的数量相同）
RB-tree的插入节点操作
在了解了红黑树的规则以后，我们需要对红黑树的插入节点操作进行分析，即红黑树插入节点的情况为以下三种：
1.插入节点为根节点：
由于在对红黑树进行节点插入操作时，每一个插入节点的颜色视为红色，而对于红黑树来说其根节点必须为黑色，故在插入的节点为根节点时，将节点的颜色调整为黑色
图3.插入节点为根节点
2.插入节点的叔叔节点为红色：
若插入节点的叔叔节点（父亲节点的兄弟节点）为红色，则将父亲节点，叔叔节点和爷爷节点的颜色反转（红变黑，黑变红）
图4.插入节点时，叔叔节点为红色
3.插入节点时，叔叔节点为黑色
在插入节点时，叔叔节点为黑色则分为四种情况，分别是RR，RL，LL，LR（右旋，右左双旋，左旋，左右双旋），以下将对这四种情况进行讲解：
1.LL（左旋）情况：
图5.插入节点时，叔叔节点为黑色（LL）
2.RR（右旋）情况：
图6.插入节点时，叔叔节点为黑色（RR）
3.LR（左右双旋）情况：
图6.插入节点时，叔叔节点为黑色（LR）
4.RL（右左双旋）情况：
图7.插入节点时，叔叔节点为黑色（RL）
PS：更详细的操作可以参考下方视频链接
RB-tree的删除节点操作
在了解了红黑树的插入节点操作，接下来将对红黑树的删除节点操作进行讲解。而针对红黑树删除节点的情况主要分为以下两种：
1.删除的节点只存在左孩子或者右孩子的情况：
图8.删除节点时，只存在左孩子或右孩子
2.删除的节点，不存在孩子节点：
1.删除的节点为红节点：
图9.删除节点时，节点无孩子且为红节点
2.删除的节点为黑节点：
1.删除的节点的兄弟节点为黑色，其该兄弟节点存在一个孩子节点为红色：
图10.删除节点时，兄弟节点为黑色且其孩子节点为红节点
2.删除的节点的兄弟节点为黑色，其该兄弟节点存在孩子节点都为黑色：
图10.删除节点时，兄弟节点为黑色且其孩子节点为黑节点
3.删除的节点的兄弟节点为红色：
图11.删除节点的兄弟节点为红色
RB-tree的节点设计
在前几小节中，我们知道RB-tree中存在黑红两个颜色的节点定义，所以在设计红黑树的节点是，我们先需要对其两种颜色进行定义，源代码如下：
typedef bool _rb_tree_color_type;const _rb_tree_color_type _rb_tree_red = false; //红色为0const _rb_tree_color_type _rb_tree_black = true; //黑色为1在了解其节点颜色的定义后，我们需要对节点进行设计，如下：
struct _rb_tree_node_base{ typedef _rb_tree_color_type color_type; typedef _rb_tree_node_base* base_ptr; color_type color; //节点颜色 base_ptr parent; //红黑树的根节点指针 base_ptr left; //节点的左子树 base_ptr right; //节点的右子树}template<class Value>struct _rb_tree_node : public _rb_tree_node_base{ typedef _rb_tree_node<Value>* link_type; Value value_field; //节点值}红黑树的节点具体结构可参考下图：
图12.红黑树的节点结构
RB-tree的迭代器设计
针对RB-tree的迭代器设计，我们知道RB-tree是一种树的数据结构类型，故对元素不支持随机访问，而为了访问RB-tree中的各个元素，其设计的迭代器应支持遍历树的各个节点的操作，故把RB-tree的迭代器类型定为双向迭代器（可以访问子节点（后向），也可以访问父节点（前向））。在设计RB-tree迭代器之前，我们需要先为该迭代器设计一个基类迭代器，方便后续继承扩展其接口，且该基类迭代器应该支持所谓的前向访问和后向访问，具体源码如下：
//RB-tree的迭代器基类struct _rb_tree_base_iterator{ typedef _rb_tree_node_base::base_ptr base_ptr; //节点基类 typedef _bidirectional_iterator_tag iterator_category; //迭代器类别 typedef ptrdiff_t differrnce_type; //迭代器之间的距离 base_ptr node; //指向当前节点的指针 void increment(); //自增（访问右子树） void decrement(); //自减（访问左子树）}void increment(){ //自增 if(node->right != 0){ //存在右节点 node = node->right; while(node->left != 0){ //遍历该右子节点的左子树 node = node->left; } }else{ //不存在右节点 base_ptr y = node->parent; //找到父节点 while(node == y->right){ //寻找父节点的右子树 node = y; //父节点不存在右子树则继续访问祖宗节点，以此类推 y = y->parent; } } if(node->right != y){ node =y; }}void decrement(){ //自减 //该节点为红色，且祖宗节点的值与节点相同 if(node->color == _rb_tree_red && node->parent->parent == node){ node = node->right; }else if(node->left != 0){ //该节点存在左子节点 base_ptr y = node->left; //访问左子节点 while(y->right != 0){ //该左子节点存在右子树，则遍历到叶子节点 y = y->right; } node = y; }else{ //该节点无左子节点 base_ptr y = node->parent; //访问其父节点 while(node == y->left){ //访问父节点的左子节点 node = y; //其组织节点不存在左子节点则继续向上访问，以此类推 y = y->parent; } node = y; //最后访问到的节点 }}在RB-tree迭代器基类的基础上进行扩展，我们得到了RB-tree的完整的迭代器的数据结构，具体代码如下：
//RB-tree迭代器template<class Value, class Ref, class Ptr>struct _rb_tree_iterator : public _rb_tree_base_iterator{ typedef Value value_type; //迭代器值的类型 typedef Ref reference; //迭代器引用类型 //非const修饰的迭代器类型 typedef _rb_tree_iterator<Value, Value&, Value*> iterator; //const迭代器类型 typedef _rb_tree_iterator<Value, const Value&, const Value> const_iterator; //迭代器自身的类型 typedef _rb_tree_iterator<Value, Ref, Ptr> self; //节点的指针类型 typedef _rb_tree_node<Value>* link_type; _rb_tree_iterator(){} _rb_tree_iterator(link_type x){ node = x; } _rb_tree_iterator(const iterator& it){ node = it.node; } reference operator*() const { return link_type(node)->value_field; }#ifndef _SGI_STL_NO_ARROW_OPERATOR pointer operator->() const { return $$(operator*()); }#endif /* _SGI_STL_NO_ARROW_OPERATOR */ self& operator++(){ incerement(); return *this; } self& operator++(int){ self tmp = *this; increment(); return tmp; } self& operator--(){ decrement(); return *this; } self operator--(int){ self tmp = *this; decrement(); return tmp; }}RB-tree的数据结构
在了解了RB-tree的迭代器结构后，我们需要着手实现RB-tree的数据结构，以下是关于RB-tree的数据结构中相关的成员以及宏定义，源码如下：
//RB-tree中的成员以及宏定义template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>class rb_tree{protected: typedef void* void _pointer; typedef _rb_tree_node_base* base_ptr; typedef _rb_tree_node<Value> rb_tree_node; typedef simple_alloc<rb_tree_node, Alloc> rb_tree_node_allocator; typedef _rb_tree_color_type color_type;public: typedef Key key_type; typedef Value value_type; typedef value_type* pointer; typedef const value_type* const_pointer; typedef value_type& reference; typedef const value_type& const_reference; typedef rb_tree_node* link_type; typedef size_t size_type; typedef ptrdiff_t difference_type; typedef _rb_tree_iterator<value_type, reference, pointer> iterator;protected: size_type node_count; //追踪记录树的大小 link_type header; //根节点 Compare key_compare; //节点间的键值大小比较准则}在了解了RB-tree的成员以及宏定义后，要对RB-tree能做的具体操作进行实现，具体代码如下：
template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>class rb_tree{protected: //节点配置函数 link_type get_node(){ //分配节点 return rb_tree_node_allocator::allocate(); } link_type create_node(const value_type& x){ //初始化节点 link_type tnp = get_node(); //配置空间 _STK_TRY{ //异常处理 construct(&tmp->value_field, x); //构造内容 } _STL_UNWIND(put_node(tmp)); return tmp; } void destroy_node(link_type p){ //释放节点 destroy(&p->value_field); //析构内容 put_node(p); //释放内存 } //获取根节点相关的数据函数 link_type& root() const { //获取根节点 return (link_type&) header->parent; } link_type& leftmost() const { //获取根节点的左子节点 return (link_type&) header->left; } link_type& rightmost() const { //获取根节点的右子节点 return (link_type&) header->right; } //获取指定节点的数据函数 static link_type& left(link_type x){ return (link_type&)(x->left); } static link_type& right(link_type x){ return (link_type&)(x->right); } static link_type& parent(link_type x){ return (link_type&)(x->parent); } static reference value(link_type x){ return x->value_field; } static const Key& key(link_type x){ return KeyOfValue()(value(x)); } staicc color_type& color(link_type x){ return (color_type&)(x->color); } //求RB-tree中的最大值和最小值 static (link_type) minimum(link_type x){ return (link_type) _rb_tree_node_base::minimum(x); } static link_type maximum(link_type x){ return (link_type) _rb_tree_node_base::maximmum(x); }private: iterator _insert(base_ptr x, base_ptr y, const value_type& v); link_type _copy(link_type x, link_type p); void _erase(link_type x); void init(){ header = get_node(); //分配节点 color(header) = _rb_tree_red; root() = 0; leftmost() = header; rightmost() = header; }public: rb_tree(const Compare& comp = Compare()) : node_count(0), key_compare(comp){ init(); } ~rb_tree(){ clear(); put_node(header); } rb_tree<Key, Value, KeyOfValue, Compare, Alloc>& operator=(const rb_tree<Key, Value, KeyOfValue, Compare, Alloc>& x);public: Compare key_comp() const { return key_compare; } iterator begin() { return leftmost(); } iterator end() { return header; } bool empty() const { return node_count == 0; } size_type size() const { return node_count; } size_type max_size() const { return size_type(-1); }public: //将x插入到RB-tree中（保持节点值不重复） pair<iterator.bool> insert_uniue(const value_type& x); //将x插入到RB-tree中（允许节点值重复） iterator insert_equal(const value_type& x);}RB-tree的构造与内存管理
关于RB-tree的构造方式有两种，一种是以现有的RB-tree复制一个新的RB-tree，另一种是产生一个空空如也的树，代码如下：
//空树rb_tree<int, int, identity<int>, less<int>> itree;//复制rb_tree(const Compare& comp = Compare()) : node_count(0), key_compare(comp){ init();}RB-treed的元素操作
关于RB-tree的元素操作，主要在乎于节点的插入和搜寻操作。其中关于插入操作，RB-tree提供了两种插入操作：insert_unique() 和insert_equal()，前者表示插入的节点在红黑树中独一无二，后者表示插入的节点在整棵树中可以重复。具体可参考以下代码：
1.元素的插入操作insert_equal()：
//插入节点：节点值允许重复template<class Key, class Value, class KeyOfValue, class Compare, class Alloc>typedef rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::iteratorrb_tree<Key, Value, KeyOfValue, Compare, Alloc>::insert_equal(const Value& v){ link_type y = header; link_type x = root(); while(x != 0){ //遍历节点，找到插入的位置 y = x; x = key_compare(KeyOfValue()(v), key(x)) ? left(x) : right(x); //遇大则往左，遇小于或等于则往右 } return _insert(x,y,z);}2.元素的插入操作insert_unique()：
//插入节点：节点值不允许重复template<class Key, class Value, class KeyOfValue, class Compare, class Alloc>pari<typename rb_tree<Key, Value, KeyOfValue, Compare, Alloc>>::iterator, bool>rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::insert_unique(const Value& v){ link_type y = header; link_type x = root; //从根节点开始遍历 bool comp = true; while(x != 0){ y = x; comp = key_compare(KeyOfValue()(v), key(x)); x = comp ? left(x) : right(x); } iterator j = iterator(y); if(comp){ if(j == begin()){ eturn pair<iterator, bool>(_insert(x, y, v), true); }else{ --j; } } if(key_compare(key(j.node), KeyOfValue()(v))){ return pair<iterator, bool>(_insert(x, y, v), true); } return pair<iterator, bool>(j, false); //新节点和树中的节点值重复，不插入}3.元素的搜寻操作find()：
//搜寻节点template<class Key, class Value, class KeyOfValue, class Compare, class Alloc>typename rb_tree<Key, Value, KeyOfValue, Compare, Alloc>>::iteratorrb_tree<Key, Value, KeyOfValue, Compare, Alloc>::find(const Key& k){ link_type y = header; link_type = root(); while(x != 0){ if(!key_compare(key(x), k)){ y = x, x = left(x); }else{ x= right(x); } } iterator j= iterator(y); return (j ++ ned() || key_compare(k, key(j.node))) ? end() : j;}