首页 > 代码库 > STL RB Tree(红黑树)分析

STL RB Tree(红黑树)分析

当我2014年上半年看内核代码的时候,进程调度用的就是RB  Tree,而现在分析STL源码的时候发现Set和Map也使用了这个数据结构,说明了RBTree的使用时如此的广泛,所以我花了两天时间看了这,分三部分来说明,首先我要说明下红黑树的基本概念,然后说明下STL中的RB Tree的迭代器,最后说下STL中RB Tree容器的实现。


一、红黑树的基本概念


红黑树是平衡二叉搜索树的一种(平衡二叉搜索树中又有AVL Tree),满足二叉搜索树的条件外,还应买足下面的4个条件

1) 每个节点不是红色就是黑色;

2) 根节点是黑色;

3)如果节点是红,那么子节点为黑色;(所以新增节点的父节点为黑色)

4)任一节点到NULL(树尾端)的任何路径,所含的黑节点数必须相同;(所以新增节点为红色)

那么如果按照二叉搜索树的规则插入节点,发现未能符合上面的要求,就得调整颜色并旋转树形。


下面分情况讨论才,插入节点后,发现未能符合要求的几种情况,以及我怎样去调整颜色和旋转树形。


在上图的红黑树种,我们插入四个节点3、8、35、75,插入后首先肯定是红色的,在上图的情况中,这四个插入操作都会违反条件三(红色节点的子节点为黑色),上面的四个点代表了四中情况,而这个图也是很具有代表性的,下面我们就来分情况分析下:

情况一:

插入节点3,如下图所示:


节点3的伯父节点是黑色节点(这里是NULL的话就算作黑色),节点3为外侧插入,这种情况下,需要做一次右旋:


这里的右旋是将爷爷节点下降一层,将父节点上升一层,因为父节点是红色,根据条件三,红色节点的子节点为黑色,所以讲父节点的颜色改为黑色,根据保证条件4,将下降的爷爷节点颜色改为红色,为了满足二叉搜索树的条件,即左子树的值小于/大于右字树的值,所以将父节点的左子树移动给爷爷节点的左子树。


情况二,插入节点8,8的伯父节点(也可以说是叔叔节点)是黑色的(空算作是黑色),插入为内侧插入:


所做的旋转和调色如上图所示,将8上调5下调之后,将8的颜色调为黑色,以满足条件3,将8的左子树移交给5的右子树以满足二叉搜索树的条件,然后再将爷爷节点调整为红色,调整后为上图第二个所示,然后再做一次右旋(是为了减少左右子树的高度差)。


情况三,插入节点75,那么该节点,伯父节点为红色,且插入为外侧插入:


此时爷爷节点85无右旋点,右旋一次以后OK,因为此时曾祖父节点为黑色,所以OK;


情况四,插入节点值为35的节点,和情况三的不同点是调整后,曾祖父节点为红色,那么就得继续往上做同样的旋转和颜色调整,直到不再有父子连续为红色的为止看,如下图所示:



OK,关于如何插入节点已经集中情况已经说完了,那么如何用代码实现则在下面继续说明。


二、红黑树迭代器的实现

这里我先直接将代码贴上来:

typedef bool __rb_tree_color_type;
typedef __rb_tree_color_type __rb_tree_red   = false;
typedef __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;
	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() {
		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->left;
		}
		else if (node->left != 0) {
			node = node->left;
			while ( node->right != 0) {
				node = node->right;
			}
		}
		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 	referece;
	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_offset = x ;}
	__rb_tree_iterator(const iterator &it) { node = it.node; }

	referece operator*()  const { return link_type(node)->value_field ;}
	referece operator->() const { return &(operator*());}

	self& operator++() {
		increment();
		return *this;
	}

	self operator++(int) {
		self tmp = *this;
		increment();
		return tmp;
	}

	self& operator--() {
		decrement();
		return *this;
	}

	self operator--() {
		self tmp = *this;
		decrement();
		return tmp;
	}

};

这里我要分析下函数increment(),decrement()和increment是类似的,所以这里我只说下increment

	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;
		}
	}

这里increment是为了将node指向下一个大于它的node,node的右子树节点的值是都大于node的,而右子树中最小的节点是右子树最左下的节点;

右子树为空的话,那么只能上溯,如果node是node->parent的右孩子的话,那么node是大于node->parent的值的,相反,是node->parent的左孩子的话,是小于parent的,那么下一个大于node的是node所处的左子树的父节点。

(最后一个判断是为了处理RB-Tree根节点和header之间的特殊关系)


三、红黑树的实现

实现代码比较长,代码逻辑并不难,对照上面的例子分析代码,并不难,这里我只说下函数insert_unique,虽然逻辑也不难;

数据成员header的parent是root,left是leftmost,right是rightmost,这是实现上的技巧

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 const value_type* 	const_iterator;
	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;

public:
	link_type get_node() {
		return rb_tree_node::allocate();
	}

	void put_node(link_type p) {
		rb_tree_node::deallocate();
	}

	link_type create_node(const value_type& x) {
		link_type tmp = get_node();
		construct(&tmp->value_field , x)
		return tmp;
	}

	link_type clone_node(link_type x) {
		link_type tmp = create_node(x->value_field);
		tmp->color = x->color;
		tmp->left 	= 0;
		tmp->right 	= 0;
		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;

	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	x->value_field;			}
	static	const Key&	key(base_ptr x)			{	return	KeyOfValue() (value(x));	}
	static	color_type& color(base_ptr x)		{	return	(color_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_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);

	Compare 	key_comp() const 	{	return 	key_compare; }
	iterator 	begin()			 	{	return 	leftmost();  }
	iterator 	end()			 	{	return	header; }
	bool 		empty()			 	{	return	node_count == 0; }
	size_type	size()	const 	 	{	return 	node_count;	}
	size_type	max_size()	const 	{	return	size_type(-1);	}

public:
	pair<iterator , bool> inset_unique(const value_type& x);
	iterator insert_equal(const value_type& x);
};



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& x)
{
	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);
}

template <class Key , class Value , class KeyOfValue , class Compare , class Alloc = alloc>


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& v)
{
	link_type	x = (link_type) x_;
	link_type	y = (link_type)	y_;
	link_type	z;

	if ( y == header || x != 0 || key_compare(KeyOfValue()(v) , key(v))) {
		z = create_node(v);
		left(y) = z;
		if ( y == header) {
			root() = z;
			rightmost() = z;
		}
		else if (y == leftmost())
			leftmost = z;
	}
	else {
		z = create_node(v);
		right(y) = z;
		if ( y == rightmost() )
			rightmost() = z;
	}
	parent(z) 	= y;
	left(z)		= 0;
	right(z)	= 0;

	__rb_tree_rebalance(z , header->parent);
	++node_count;
	return iterator(z);
}

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;
			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->right;
			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;
			}
			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;

	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_rigth(__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;

	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;
}

至于函数insert_unique,是保证插入的键值不允许重复

typename rb_tree<Key , Value , KeyOfValue , Compare , Alloc>::iterator
rb_tree<Key , Value , KeyOfValue , Compare , Alloc>::insert_unique(const Value& x)
{
	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); //遇大则往左,小于等于则往右
	}       //离开之后, y即为插入点之父节点,此时它必为叶节点        iterator j = iterator(y);
	if (comp) { //如果离开while循环的时候,comp是真,说明是插入点是y的左孩子		if (j == begin()) { //插入点父节点是最左节点,此时,不会有重复键值
			return 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> , false);
}
插入点父节点不是最左边的节点的话,--j,是将j指向比父节点小的上一个节点,和v的键值比较,不相等说明是没有重复,因为插入点是左孩子,必然是小于父节点的,那么和比父节点小点的节点比较(v肯定是大于等于该值的),如果不是等于,则插入;

另外如果插入点是父节点y的右孩子的话,右孩子是大于等于y的,那么和y比较大小,如果不等于则插入。


这里呢,我只备注了下我看代码的时候让我迷惑的那些代码,如果哪有说的不对的地方,欢迎指正,谢谢 O(∩_∩)O哈哈~




STL RB Tree(红黑树)分析