首页 > 代码库 > 关联容器(底层机制) — 红黑树
关联容器(底层机制) — 红黑树
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
<
class
Value>
struct
__rb_tree_node :
public
__rb_tree_node_base
{
typedef
__rb_tree_node<Value>* 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
<
class
Value,
class
Ref,
class
Ptr>
struct
__rb_tree_iterator :
public
__rb_tree_base_iterator
{
typedef
Value value_type;
typedef
Ref reference;
typedef
Ptr pointer;
typedef
__rb_tree_iterator<Value, Value&, Value*> iterator;
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; }
// 初始化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
Key,
class
Value,
class
KeyOfValue,
class
Compare,
class
Alloc = alloc>
class
rb_tree {
....
typedef
__rb_tree_node<Value> rb_tree_node;
typedef
simple_alloc<rb_tree_node, 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<iterator,
bool
> 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<iterator,iterator> 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.
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。