关联容器 — 红黑树
最后更新于：2022-04-01 19:54:15
set、map、multiset、multimap四种关联式容器的内部都是由红黑树实现的。在STL中红黑树是一个不给外界使用的独立容器。既然是容器，那么就会分配内存空间（节点），内部也会存在迭代器。关于红黑树的一些性质，可以参考“数据结构”中的笔记，这里只记录STL中的红黑树是如何实现的。
和slist一样，红黑树的节点和迭代器均采用了双层结构：
- 节点：__rb_tree_node继承自__rb_tree_node_base
- 迭代器：__rb_tree_iterator继承自__rb_tree_base_iterator
先看看颜色标识：
~~~
typedef bool __rb_tree_color_type; // 标识红黑树节点颜色的类型
const __rb_tree_color_type __rb_tree_red = false;
const __rb_tree_color_type __rb_tree_black = true;
~~~
基础节点：
~~~
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; // RB树的许多操作必须知道父节点
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; // 节点值
};
~~~
上层节点很简单，只包含一个指针类型和存放节点值的变量。
基础迭代器：
~~~
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() // 迭代器++时使用
{
....
}
void decrement() // 迭代器--时使用
{
....
}
};
~~~
基础迭代器中注意node成员，然后是两个专供operator++和operator--的内部方法，它们根据红黑树特性使node指向后一个或前一个节点，因为红黑树是一个二叉搜索树，找出键值相邻的节点是有规律可循的。所以，红黑树的迭代器属于双向迭代器。
上层迭代器：
~~~
template
struct __rb_tree_iterator : public __rb_tree_base_iterator
{
typedef Value value_type;
typedef Ref reference;
typedef Ptr pointer;
typedef __rb_tree_iterator iterator;
typedef __rb_tree_iterator const_iterator;
typedef __rb_tree_iterator self;
typedef __rb_tree_node* link_type; // 指向上层节点的指针
__rb_tree_iterator() {}
__rb_tree_iterator(link_type x) { node = x; } // 初始化node
__rb_tree_iterator(const iterator& it) { node = it.node; }
reference operator*() const { return link_type(node)->value_field; } // 解引用，注意link_type类型转换
pointer operator->() const { return &(operator*()); } // 箭头操作符
self& operator++() { increment(); return *this; }
self operator++(int) {
....
}
self& operator--() { decrement(); return *this; }
self operator--(int) {
....
}
};
~~~
上层迭代器就是红黑树类中的迭代器，对它的++或--操作最终都是调用了基础迭代器中的increment()或decrement()。
下面记录一下红黑树的数据结构框架：
~~~
template
class rb_tree {
....
typedef __rb_tree_node rb_tree_node;
typedef simple_alloc rb_tree_node_allocator; // 空间配置器，一次分配一个节点
typedef rb_tree_node* link_type;
link_type get_node() { return rb_tree_node_allocator::allocate(); } // 获得一个节点空间
void put_node(link_type p) { rb_tree_node_allocator::deallocate(p); } // 释放一个节点空间
link_type create_node(const value_type& x) { // 分配并构造一个节点
link_type tmp = get_node();
construct(&tmp->value_field, x);
return tmp;
}
....
void destroy_node(link_type p) { // 析构并释放一个节点
destroy(&p->value_field);
put_node(p);
}
protected:
size_type node_count; // 记录节点数量
link_type header; // 使用上的一个技巧
Compare key_compare; // 键值大小比较准则
....
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 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:
pair insert_unique(const value_type& x); // 节点键值独一无二
iterator insert_equal(const value_type& x); // 节点键值可重复性
void erase(iterator position); // 删除节点
....
public:
// 以下函数在multimap和multiset中使用
iterator find(const key_type& x);
size_type count(const key_type& x) const;
iterator lower_bound(const key_type& x);
iterator upper_bound(const key_type& x);
pair equal_range(const key_type& x);
}
~~~
注意上面代码的红色部分使用了一个技巧来处理节点为root时的边界情况，它使用了一个header指针。先看看初始化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; }
void init() { // 初始化header
header = get_node();
color(header) = __rb_tree_red; // used to distinguish header from
// root, in iterator.operator--
root() = 0; // header->parent = null
leftmost() = header;
rightmost() = header;
}
~~~
把header指向节点的颜色设置为红色（为了区别根节点的黑色），注意这不是根节点，只是类似一个哨兵节点。header的parent始终指向root（这里初始化为null）；left始终指向最小节点；right始终指向最大节点。header记录了这些信息之后，容器的begin()、end()就很好求了：
~~~
iterator begin() { return leftmost(); } // header->left
iterator end() { return header; } // 返回header，调用__rb_tree_iterator构造函数由指针转迭代器
~~~
和其它容器一样，end()同样是返回最后一个元素（最大节点）的下一个节点。
参考：
《STL源码剖析》 P213.
';