RB-tree的节点设计
SGI STL的实现源代码为了有更大的弹性，节点和迭代器都分为两层。
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
struct __rb_tree_node_base
{
typedef __rb_tree_color_type color_type; //bool
typedef __rb_tree_node_base* base_ptr;
color_type color; //定义节点颜色
base_ptr parent; //指向父节点
base_ptr left; //指向左孩子
base_ptr right; //指向右孩子
static base_ptr minimum(base_ptr x) //取以x为根节点的最小值
{
while(NULL != x->next) x = x->left;
return x;
}
static base_ptr maximum(base_ptr x) //取以x为根节点的最大值
{
while(NULL != x->next) 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; //节点值
};
RB-tree的迭代器
基层迭代器
struct __rb_tree_base_iterator
{
typedef __rb_tree_node_base::base_ptr base_ptr; //即__rb_tree_node_base*
typedef bidirectional_iterator_tag iterator_category; //双向迭代器类型
typedef ptrdiff_t difference_type; //表示迭代器之间的距离
base_ptr node; //与容器之间产生一个连结关系
void increment() //在顺序队列中找到node的下一位
{
if(node -> right != 0) //该节点有右子树，右子树的最小值
{
node = node->right;
while(node->left != 0)
{
node = node->left;
}
}
else //该节点没有右子树
{
base_ptr y = node->parent; //若该节点为父节点的左孩子，找该节点的父节点，就是我们要找的
while(node == y->right) //若该节点为父节点的右孩子，向上找，直至不为右孩子，有两种情况：(1)该节点为最大值，直到null(2).该节点的位于某个节点的左子树上，找到了这个节点
{
node = y;
y = y->parent;
}
if(node->right != y)
{
node = y;
}
}
}
void decrement() //在顺序队列中找到node的上一位
{
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;
}
}
};
正规迭代器
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, Ref, Ptr> self;
typedef __rb_tree_iterator<Value, Value&, Value*> iterator;
typedef __rb_tree_iterator<Value, const Value&, const Value*> const_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;
}
#ifndef __SGI_STL_NO_ARROW_OPERATOR
pointer operator->() const { return &(operator*());}
#endif
self& operator++()
{
increment();
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的三笔数据（其中有个仿函数，用来表现节点的大小比较方式）
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; //定义分配器，每个容器都有自己的空间分配器，详见allocator文件
typedef __rb_tree_color_type color_type;
public:
typedef Key key_type; //定义key类型
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:
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(); //配置空间
__STL_TRY { //内部的宏，处理异常
construct(&tmp->value_field, x); //构造该空间的内容
}
__STL_UNWIND(put_node(tmp)); //若发生错误，则释放该节点空间
return tmp;
}
void destory_node(link_type p)
{
destroy(&p->value_field); //析构函数
put_node(p); //释放内存
}
protected:
size_type node_count; //追踪记录树的大小（节点数量）
link_type header; //实现上的技巧
Compare key_compare; //节点间的键值大小比较准则
//以下三个函数用来方便取得header的成员
link_type& root() const { return (link_type&) header->parent; } //header->parent指向树的根节点
link_type& leftmost() const { return (link_type&) header->left; } //header->left指向树的最小值（第一个值）
link_type& rightmost() const { return (link_type&) header->right; } ）
//以下函数方便获得节点x的成员
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)); } //KeyofValue()：这是一个函数对象（也称为仿函数或者函数适配器），它的作用是从节点中存储的值中提取出键。value(x)：这是一个调用，它接受一个节点指针 x 并返回该节点中存储的值。这个值通常是一个包含键和值的对（如 std::pair），或者就是键本身，如果键和值是相同的。
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))); } //KeyofValue()：这是一个函数对象（也称为仿函数或者函数适配器），它的作用是从节点中存储的值中提取出键。value(x)：这是一个调用，它接受一个节点指针 x 并返回该节点中存储的值。这个值通常是一个包含键和值的对（如 std::pair），或者就是键本身，如果键和值是相同的。
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:
typedef __rb_tree_iterator<value_type, reference, pointer> iterator; //定义迭代器，外部可见
private:
iterator __insert(base_ptr x, base_ptr y, const value_type& v);
link_type __copy(link_ype x, link_type p);
void init() //实现上的技巧，初始化header
{
header = get_node(); //header指向一个空间，没有用create_node，证明没有初始化
color(header) = __rb_tree_red; //令header为红色，用来区分header
root() = 0;
leftmost() = header; //令header的左子节点为自己
rightmost() = header;
}
public:
rb_tree(const Compare& comp = Compare()) : node_count(0), key_compare(comp) { init(); } //构造函数，传入Compare仿函数
~rb_tree()
{
clear(); //清空树上的节点
put_node(header); //释放header
}
rbtree<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(); } //RB树的起头为最左（最小）节点处，iterator里面有构造函数接收link_type类型
iterator end() { return header; } //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:
pair<iterator, bool> insert_unique(const value_type& x); //保持节点值独一无二
iterator insert_equal(const value_type& x); //允许节点值重复
};
RB-tree的构建
元素插入操作
template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
typename rb_tree<Key, Value, KeyofValue, Compare, Alloc>::iterator rb_tree<Key, Value, KeyofValue, Compare, Alloc>::insert_equal(const value_type& 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为新值
}
template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
pair<typename rb_tree<Key, Value, KeyofValue, Compare, Alloc>::iterator, bool> rb_tree<Key, Value, KeyofValue, Compare, Alloc>::insert_equal(const value_type& 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); //令迭代器j指向插入点之父节点y
if(comp)
{
if(j == begin()) return pair<iterator, bool>(); //若父节点是最左边的值，那么一定没有左孩子，也就不会重复
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);
}
template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
typename rb_tree<Key, Value, KeyofValue, Compare, Alloc>::iterator rb_tree<Key, Value, KeyofValue, Compare, Alloc>::__insert(base_ptr x_, base_ptr y_, const value_type& v)
{ // x_为新值插入点(为了判断x是否不为空，也就是insert_equal需要)，参数y_为插入点之父节点，参数v为新值
link_type x = (link_type) x_;
link_type y = (link_type) y_;
link_type z = create_node(v);
if(y == header || x != 0 || key_compare(KeyofValue()(v), key(y)))
{
left(y) = z;
if(y == header)
{
root() = z;
rightmost() = z;
}
else if(y == leftmost()) leftmost() = z;
}
else
{
right(y) = z; //新节点成为y的右子节点
if(y == rightmost()) rightmost() = z; //维护rightmost()， 使它指向最右节点
}
parent(z) = y;
left(z) = 0;
right(z) = 0;
__rb_tree_rebalance(z, header->parent); //新增节点，root
++node_count;
return iterator(z);
}
调整RB-tree(旋转及改变颜色)
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;
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);
}
}
}
root->color = __rb_tree_black;
}
左旋
inline void __rb_tree_rotate_left(__rb_tree_node_base* x, __rb_tree_node_base*& root)
{
__rb_tree_node_base* y = x->right;
x->right = y->left;
if(y->left != 0) y->left->parent = x;
y->parent = x->parent;
if(x == root) root = y;
else if(x == x->parent->left) x->parent->left = y;
else 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)
{
__rb_tree_node_base* y = x->left;
x->left = y->right;
if(y->right != 0) y->right->parent = x;
y->parent = x->parent;
if(x == root) root = y;
else if(x == x->parent->left) x->parent->left = y;
else x->parent->right = y;
y->right = x;
x->parent = y;
}
元素的搜寻
template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
typename rb_tree<Key, Value, KeyofValue, Compare, Alloc>::iterator rb_tree<Key, Value, KeyofValue, Compare, Alloc>::find(const Key& k)
{
link_type y = header;
link_type x = root();
while(x != 0)
{
if(!key_compare(key(x), k)) //若小于x，则更新x，y
{
y = x, x = left(x);
}
else x = right(x);
}
iterator j = iterator(y);
return (j == end() || key_compare(k, key(j.node())) ? end() : j;
} //没有等号，但依然可以定位到指向该节点的迭代器，画个图一目了然