【STL源码剖析】|STL源码剖析 RB-tree STL|学习|STL源码剖析

文章目录

1. RB-tree概述
- 1.1 关于二叉搜索树
- - 1.1.1 二叉搜索树简介
  - 1.1.2 二叉搜索树的性质
  - 1.1.3 平衡二叉搜索树
- 1.2 RB-tree
- 1.3 RB-tree平衡性修正
2. 节点及迭代器设计
- 2.1 节点设计
- 2.2 迭代器设计
- - 2.2.1 header设计
  - 2.2.2 设计迭代器
3. RB-tree数据结构
4. RB-tree构造与内存管理
5. 元素操作
- 5.1 元素插入
- 5.2 搜寻元素
6. 总结

1. RB-tree概述

RB-tree，即红黑树，是一种平衡二叉搜索树，由二叉搜索树经过某种特定的操作使之能够达到平衡

1.1 关于二叉搜索树 1.1.1 二叉搜索树简介
二叉搜索树，顾名思义，是由一颗二叉树组织而成，这样的一颗树可以由链表数据结构来表示，每个节点除了key以外，还有left、right及parent，分别指向左子节点、右子节点及父节点，如果对应的节点不存在的话则指向NIL节点
1.1.2 二叉搜索树的性质
【【STL源码剖析】|STL源码剖析 RB-tree】二叉搜索树是一颗空树或者具有以下性质的二叉树：

1.任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值
2.任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值
3.任意节点的左、右子树也分别为二叉查找树
4.没有键值相等的节点

1.1.3 平衡二叉搜索树
我们知道，一颗由n个节点随机构造的二叉搜索树的高度为logn，但也许因为输入值不够随机，也许因为某些插入或删除操作，二叉搜索树可能会失去平衡，造成搜寻效率低落的情况。从而，引出了平衡二叉搜索树的概念，这里的平衡的意思是没有任何一个节点深度过大，如AVL tree要求左右子树高度相差最多1，AVL tree要求有点严苛，不过稍后所要解析的RB-tree并没有如此的严苛，只是要求最长路径不超过最短路径的两倍
1.2 RB-tree 经过刚刚的了解，我们知道RB-tree是一种平衡二叉搜索树，但RB-tree又不仅限于此，还必须满足以下规则：

1.每个节点不是红色就是黑色
2.根节点为黑色
3.每个叶子节点(NIL)为黑色[注意：这里所说的叶子节点是为空(NIL或NULL)的节点]
4.父节点与子节点不能同时为红色
5.从一个节点到其子孙节点的路径上所包含的黑节点数目相同

我们刚刚提到RB-tree要求其最长路径不超过其最短路径的两倍，那么通过上述的规则能否达到这个要求呢？通过每个节点的颜色限制是能够达到这种要求的，例如，根据上述规则一颗RB-tree其最短路径假设为n，即全为黑节点才能使得路径最短，那么根据规则5，我们就能得出满足条件的最长路径应该是黑红相间的，且长度为2n或2n-1，这样就满足了条件
1.3 RB-tree平衡性修正当我们在RB-tree中插入了一些数据时，就很容易导致RB-tree失衡，这个时候就需要某些特定操作来使得RB-tree重新恢复平衡，这些操作分为三种，分别为改变节点颜色、左旋和右旋，下面让我们来逐一了解它们吧：

改变节点颜色
首先，根据规则5，我们知道新增节点必须为红色，而当此时的父节点恰好为红色时，如果不进行更改，那么显然会违背规则4，这时就需要更改节点的颜色，如下图所示：

文章图片
将一个偏向右边的红色链接旋转为左链接，如下图：
文章图片

一个助于理解的动图：

文章图片
将一个偏向左边的红色链接改为右链接，如下图：

文章图片

一个有助于理解的动图：

文章图片

图片参考自eson_15的博客

现在我们认识到了RB-tree如何通过自我修正回到平衡，现在让我们深入解析RB-tree在STL中是如何设计的吧！
2. 节点及迭代器设计

首先，在解析slist提到过RB-tree采用与slist相同的设计方式，即双层设计，那么现在我们就来一探究竟RB-tree的双层设计的内部结构

2.1 节点设计

//RB-tree特有的颜色定义 typedef bool __rb_tree_color_type; const __rb_tree_color_type __rb_tree_red = false; //红色被定义为0 const __rb_tree_color_type __rb_tree_black = true; //黑色被定义为1 //RB-tree节点基本结构 struct __rb_tree_node_base { typedef __rb_tree_color_typecolor_type; typedef __rb_tree_node_base* base_ptr; color_type color; // 节点颜色,非黑即红 base_ptr parent; // 指向父节点,由于RB-tree时常要上溯其父节点 base_ptr left; // 指向左子节点 base_ptr right; // 指向右子节点// 一直往左走，就能找到红黑树的最小值节点 // 二叉搜索树的性质 static base_ptr minimum(base_ptr x) { while (x->left != 0) x = x->left; return x; } // 一直往右走，就能找到红黑树的最大值节点 // 二叉搜索树的性质 static base_ptr maximum(base_ptr x) { while (x->right != 0) x = x->right; return x; } }; // 真正的节点定义，采用双层节点结构 // 基类中不包含模板参数 template struct __rb_tree_node : public __rb_tree_node_base { typedef __rb_tree_node* link_type; Value value_field; // 即节点值 };

2.2 迭代器设计 2.2.1 header设计

在了解RB-tree迭代器设计之前，首先了解header这一特殊设计：

树状结构的各种操作，最需注意的就是边界情况的发生，也就是走到根节点时要有特殊的处理，为了简化这种处理，SGI STL为根节点再设计了一个父节点，名为header

文章图片
当插入一个节点时，不但要按照RB-tree的规则来调整，并且维护header的正确性，使其父节点指向根节点，左子节点指向最小节点，右子节点指向最大节点

2.2.2 设计迭代器

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 node; // 用来连接红黑树的节点// 寻找该节点的后继节点上 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; // 此时的父节点即为要找的后继节点 // 否则此时的node即为要找的后继节点，此为特殊情况，如下 // 我们要寻找根节点的下一个节点，而根节点没有右子节点 // 此种情况需要配合rbtree的header节点的特殊设计，后面会讲到 } }// 寻找该节点你的前置节点 void decrement() { if (node->color == __rb_tree_red && // 如果此节点是红节点 node->parent->parent == node)// 且父节点的父节点等于自己 node = node->right; // 则其右子节点即为其前置节点 // 以上情况发生在node为header时，即node为end()时 // 注意：header的右子节点为mostright，指向整棵树的max节点，后面会有解释 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; // 此时他的父节点即为要找的前驱节点 } } }; template struct __rb_tree_iterator : public __rb_tree_base_iterator { //...型别声明 // 迭代器的构造函数 __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; } pointer operator->() const { return &(operator*()); } // 前置++和后置++ self& operator++() { increment(); return *this; } self operator++(int) { self tmp = *this; increment(); // 直接调用increment函数 return tmp; } // 前置--和后置-- self& operator--() { decrement(); return *this; } self operator--(int) { self tmp = *this; decrement(); // 直接调用decrement函数 return tmp; } };

以下是对于这两个函数的个人理解（忽略图画的不好orz）：

文章图片

3. RB-tree数据结构

RB-tree定义如下，我们可以观察到一些型别的定义，用来维护RB-tree的三笔数据（其中包含一个仿函数，用来比较节点之间的大小），以及一些member function的定义或声明：

template class rb_tree { protected: typedef void* void_pointer; typedef __rb_tree_node_base* base_ptr; typedef __rb_tree_node rb_tree_node; typedef simple_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; protected: // RB-tree的数据结构 size_type node_count; // 记录树的节点个数 link_type header; // header节点设计 Compare key_compare; // 节点间的键值大小比较准则// 以下三个函数用来取得header的成员 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)); } static color_type& color(link_type x) { return (color_type&)(x->color); }// 以下六个函数用来取得节点的成员，由于双层设计，导致这里需要两个定义 static link_type& left(base_ptr x) { return (link_type&)(x->left); } static link_type& right(base_ptr x) { return (link_type&)(x->right); } static link_type& parent(base_ptr x) { return (link_type&)(x->parent); } static reference value(base_ptr x) { return ((link_type)x)->value_field; } static const Key& key(base_ptr x) { return KeyOfValue()(value(link_type(x))); } static color_type& color(base_ptr x) { return (color_type&)(link_type(x)->color); }// 求取极大值和极小值，这里直接调用节点结构的函数极可 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::maximum(x); }public: // RBTree的迭代器定义 typedef __rb_tree_iterator iterator; typedef __rb_tree_iterator const_iterator; private: //... void init() {//构造一个空tree header = get_node(); //产生一个节点空间，令header指向它 color(header) = __rb_tree_red; //令header为红色，用来将 //root与header区分开 root() = 0; leftmost() = header; //header的左子节点为自己 rightmost() = header; //header的右子节点为自己 } public: Compare key_comp() const { return key_compare; }// 由于红黑树自带排序功能，所以必须传入一个比较器函数 iterator begin() { return leftmost(); }// RBTree的起始节点为左边最小值节点 const_iterator begin() const { return leftmost(); } iterator end() { return header; }// RBTree的终止节点为右边最大值节点 const_iterator end() const { 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); }// 获取红黑树的最大节点个数， // 没有容量的概念，故为sizetype最大值 };

我们可以观察到，相较于其他的数据结构，其实RB-tree并无多少复杂，而对于header我们在上面已经解析了，稍后仍然会提及，所以这里还是没有什么难点的,接下来让我们来了解一些关于RB-tree的构造
4. RB-tree构造与内存管理以下是RB-tree关于构造的一些实例：

1.在上述RB-tree数据结构定义中我们看到了RB-tree定义了一个专属的空间配置器rb_tree_node_allocator为其配置节点
2.在上述数据结构中我们未列上去的关于节点的函数get_node(),put_node(),create_node(),clone_node,destroy_node()
3.RB-tree构造方式：以现有的RB-tree复制一个新的RB-tree；产生一颗空空的树：

//例：产生一颗空空如也的树 rb_tree, less > itree; //定义了节点的键值、实值及大小比较准则 //调用默认构造函数 rb_tree(const Compare& comp = Compare()) : node_count(0), key_compare(comp){init(); } //调用init初始化 void init() {//构造一个空tree header = get_node(); //产生一个节点空间，令header指向它 color(header) = __rb_tree_red; //令header为红色，用来将 //root与header区分开 root() = 0; leftmost() = header; //header的左子节点为自己 rightmost() = header; //header的右子节点为自己 }

4.关于header设计，主要是简化到边界特殊情况的处理，在上述已经详细解析了，这里就不再重提了

5. 元素操作 5.1 元素插入在前面我们已经知道了RB-tree对于平衡性修正有三种方式，分别是改变节点颜色、左旋和右旋，我们也知道在插入新元素时会导致RB-tree失去平衡，那么我们应该怎样合适的应用这三种方式来使RB-tree恢复平衡呢？现在就让我们来一起解析吧！

先来了解一下RB-tree提供的两种插入操作：insert_unique()、insert_equal()
insert_unique():表示被插入的键值在整棵树中必须独一无二
insert_equal():表示被插入节点的键值在整棵树中可以重复

insert_unique():

// 此插入函数不允许重复 // 返回的是一个pair，第一个元素为红黑树的迭代器，指向新增节点 // 第二个元素表示插入操作是否成功的 template pair::iterator , bool> rb_tree::insert_unique(const Value &v) { rb_tree_node* y = header; // 根节点root的父节点 rb_tree_node* x = root(); // 从根节点开始 bool comp = true; while(x != 0) { y = x; comp = key_compare(KeyOfValue()(v) , key(x)); // v键值小于目前节点之键值？ x = comp ? left(x) : right(x); // 遇“大”则往左，遇“小于或等于”则往右 } // 离开while循环之后，y所指即插入点之父节点（此时的它必为叶节点） iterator j = iterator(y); // 令迭代器j指向插入点之父节点y if(comp)// 如果离开while循环时comp为真（表示遇“大”，将插入于左侧） { if(j == begin())// 如果插入点之父节点为最左节点 return pair(_insert(x , y , z) , true); // 调用_insert函数 else// 否则（插入点之父节点不为最左节点） --j; // 调整j，回头准备测试 } if(key_compare(key(j.node) , KeyOfValue()(v) )) // 新键值不与既有节点之键值重复，于是以下执行安插操作 return pair(_insert(x , y , z) , true); // 以上，x为新值插入点，y为插入点之父节点，v为新值// 进行至此，表示新值一定与树中键值重复，那么就不应该插入新值 return pair(j , false); }

insert_equal():

//插入新值：节点键值允许重复 //返回值是一个RB-tree迭代器，指向新增节点 template pair::iterator , bool> rb_tree::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, v); // 以上，x为新值插入点，y为插入点之父节点，v为新值 }

观察上述，无论是哪一种插入方式，最终都需要调用__insert()函数,这个函数才是真正的插入函数：

// 真正地插入执行程序 _insert() // 返回新插入节点的迭代器 template typename::_insert(base_ptr x_ , base_ptr y_ , const Value &v) { // 参数x_ 为新值插入点，参数y_为插入点之父节点，参数v为新值 link_type x = (link_type) x_; link_type y = (link_type) y_; link_type z; // key_compare 是键值大小比较准则。应该会是个function object if(y == header || x != 0 || key_compare(KeyOfValue()(v) , key(y) )) { z = create_node(v); // 产生一个新节点 left(y) = z; // 这使得当y即为header时，leftmost() = z if(y == header) { root() = z; rightmost() = z; } else if(y == leftmost())// 如果y为最左节点 leftmost() = z; // 维护leftmost()，使它永远指向最左节点 } else { z = create_node(v); // 产生一个新节点 right(y) = z; // 令新节点成为插入点之父节点y的右子节点 if(y == rightmost()) rightmost() = z; // 维护rightmost()，使它永远指向最右节点 } parent(z) = y; // 设定新节点的父节点 left(z) = 0; // 设定新节点的左子节点 right(z) = 0; // 设定新节点的右子节点 // 新节点的颜色将在_rb_tree_rebalance()设定（并调整） _rb_tree_rebalance(z , header->parent); // 参数一为新增节点，参数二为根节点root ++node_count; // 节点数累加 return iterator(z); // 返回一个迭代器，指向新增节点 }

在将节点插入到RB-tree中后，需要调整RB-tree使之恢复平衡，调用_rb_tree_rebalance()函数：

// 全局函数 // 重新令树形平衡（改变颜色及旋转树形） // 参数一为新增节点，参数二为根节点root inline void _rb_tree_rebalance(_rb_tree_node_base* x , _rb_tree_node_base*& root) { x->color = _rb_tree_red; //新节点必为红 while(x != root && x->parent->color == _rb_tree_red)// 父节点为红 { if(x->parent == x->parent->parent->left)// 父节点为祖父节点之左子节点 { _rb_tree_node_base* y = x->parent->parent->right; // 令y为伯父节点 if(y && y->color == _rb_tree_red)// 伯父节点存在，且为红 { x->parent->color = _rb_tree_black; // 更改父节点为黑色 y->color = _rb_tree_black; // 更改伯父节点为黑色 x->parent->parent->color = _rb_tree_red; // 更改祖父节点为红色 x = x->parent->parent; } else// 无伯父节点，或伯父节点为黑色 { if(x == x->parent->right)// 如果新节点为父节点之右子节点 { x = x->parent; _rb_tree_rotate_left(x , root); // 第一个参数为左旋点 } x->parent->color = _rb_tree_black; // 改变颜色 x->parent->parent->color = _rb_tree_red; _rb_tree_rotate_right(x->parent->parent , root); // 第一个参数为右旋点 } } else// 父节点为祖父节点之右子节点 { _rb_tree_node_base* y = x->parent->parent->left; // 令y为伯父节点 if(y && y->color == _rb_tree_red)// 有伯父节点，且为红 { x->parent->color = _rb_tree_black; // 更改父节点为黑色 y->color = _rb_tree_black; // 更改伯父节点为黑色 x->parent->parent->color = _rb_tree_red; // 更改祖父节点为红色 x = x->parent->parent; // 准备继续往上层检查 } else// 无伯父节点，或伯父节点为黑色 { if(x == x->parent->left)// 如果新节点为父节点之左子节点 { x = x->parent; _rb_tree_rotate_right(x , root); // 第一个参数为右旋点 } x->parent->color = _rb_tree_black; // 改变颜色 x->parent->parent->color = _rb_tree_red; _rb_tree_rotate_left(x->parent->parent , root); // 第一个参数为左旋点 } } }//while root->color = _rb_tree_black; // 根节点永远为黑色 } // 左旋函数 inline void _rb_tree_rotate_left(_rb_tree_node_base* x , _rb_tree_node_base*& root) { // x 为旋转点 _rb_tree_node_base* y = x->right; // 令y为旋转点的右子节点 x->right = y->left; if(y->left != 0) y->left->parent = x; // 别忘了回马枪设定父节点 y->parent = x->parent; // 令y完全顶替x的地位（必须将x对其父节点的关系完全接收过来） if(x == root)// x为根节点 root = y; else if(x == x->parent->left)// x为其父节点的左子节点 x->parent->left = y; else// x为其父节点的右子节点 x->parent->right = y; y->left = x; x->parent = y; } // 右旋函数 inline void _rb_tree_rotate_right(_rb_tree_node_base* x , _rb_tree_node_base*& root) { // x 为旋转点 _rb_tree_node_base* y = x->left; // 令y为旋转点的左子节点 x->left = y->right; if(y->right != 0) y->right->parent = x; // 别忘了回马枪设定父节点 y->parent = x->parent; // 令y完全顶替x的地位（必须将x对其父节点的关系完全接收过来） if(x == root) root = y; else if(x == x->parent->right)// x为其父节点的右子节点 x->parent->right = y; else// x为其父节点的左子节点 x->parent->left = y; y->right = x; x->parent = y; }

在上述我们看到了在何种情况下应该只改变节点颜色，而在何种情况下应该通过左旋、右旋来使RB-tree修正，保持平衡
5.2 搜寻元素

对于一个二叉搜索树而言，搜寻元素对于其而言可以称之简单，下面是寻找RB-tree中是否有键值为k的节点：

// 寻找RBTree中是否存在键值为k的节点 template typename rb_tree::iterator rb_tree::find(const Key& k) { link_type y = header; // Last node which is not less than k. link_type x = root(); // Current node. while (x != 0) // key_compare是节点键值大小比较函数 if (!key_compare(key(x), k)) // 如果节点x的键值大于k，则继续往左子树查找 y = x, x = left(x); // else // 如果节点x的键值小于k，则继续往右子树查找 x = right(x); iterator j = iterator(y); // y的键值不小于k，返回的时候需要判断与k是相等还是小于 return (j == end() || key_compare(k, key(j.node))) ? end() : j; }

6. 总结关于RB-tree，就解析到这里了，RB-tree作为一种基础的数据结构，我们应该将其掌握，这个掌握不是你今天掌握了而明天又忘了，而是当你回想起RB-tree时你的大脑要像条件反射一样回顾起关于RB-tree的种种，要做到这一点有难度，所以就要求我们时常温故；作为map及set的底层数据结构，RB-tree的重要性不言而喻，而且面试时几乎是必考题，所以掌握RB-tree会受益匪浅
本文解析RB-tree可能略有粗糙，想要了解更多可以参考以下两位大佬的博客：