• 欢迎访问开心洋葱网站,在线教程,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站,欢迎加入开心洋葱 QQ群
  • 为方便开心洋葱网用户,开心洋葱官网已经开启复制功能!
  • 欢迎访问开心洋葱网站,手机也能访问哦~欢迎加入开心洋葱多维思维学习平台 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏开心洋葱吧~~~~~~~~~~~~~!
  • 由于近期流量激增,小站的ECS没能经的起亲们的访问,本站依然没有盈利,如果各位看如果觉着文字不错,还请看官给小站打个赏~~~~~~~~~~~~~!

C++红黑树的实现(int精简版)

OC/C/C++ 水墨上仙 2797次浏览

最近在阅读SGI STL源代码,其中红黑树的实现比较有技术含量,但标准库里面是捆绑了其中的allocator, iterator(Rb_tree专用的),使用很多模板变量,实现对多种数据类型的处理。这些情况对于有较扎实C++基础的人来说不成问题,但对于一般初学算法,而又没有太好的C++基础的人来说有点困难。并且SGI STL中的实现代码写得很精巧,节省代码,也高效运行,但会使得功能不够深厚的人读起来还是比较费劲。
这里使用简单的int类型节点,实现红黑树的创建、插入及相关内部操作的功能。目前代码中删除节点及其内部操作功能没有实现。
关于红黑树的五个条件(有的书上说四个,内容是等价的)以及插入节点后的调整,可以参考侯捷先生的《STL源码剖析》,里面有详细的原理介绍。也可以参考《算法导论》。下面代码可以直接使用运行,经测试正确,代码不追求在物理运行上的效率,尽量把算法步骤表现在代码里,不作过多合并优化,并且已经加上不少注释,方便阅读。

My_Rb_Tree.h

#pragma once
#define node_black true
#define node_red false
typedef bool node_color;
typedef int value_type;
struct node
{
	node_color color;
	node * left;
	node * right;
	node * parent;
	value_type val;
};
class My_Rb_Tree
{
public:
	My_Rb_Tree(void);
	~My_Rb_Tree(void);
	node * InsertUnique(value_type in_val);
	void Erase(node * in_cur);
	node * Find(value_type _val);
private:
	node * Root();
	void Init();
	node * CreateNode(value_type _val);
	void DestoryNode(node * &_n);
	void RotateLeft(node * _cur);
	void RotateRight(node * _cur);
	void Rebalance(node * _cur);
	void RebalanceForErase(node * _cur);
	node * Insert(node * in_parent, node * in_cur, value_type in_value);
private:
	int node_count;
	node * head;
};

My_Rb_Tree.cpp

/************************************************************************/
/*  @brief Red-Black tree implement.
/*  @author sail2010@163.com
/*  @date 2012.10.12
/*  @time 16:56:37                                        
/************************************************************************/
#include "StdAfx.h"
#include "My_Rb_Tree.h"
#include "assert.h"
My_Rb_Tree::My_Rb_Tree(void)
:node_count(0),
head(0)
{
	Init();
}
My_Rb_Tree::~My_Rb_Tree(void)
{
}
node * My_Rb_Tree::Root()
{
	assert(head);
	if (!head)
	{
		return 0;
	}
	return head->parent;
}
void My_Rb_Tree::Init()
{	
	head = CreateNode(0);
	if (!head)
	{
		return;
	}
	head->color = node_red;
	head->left = head;
	head->right = head;
	head->parent = 0;
}
node * My_Rb_Tree::CreateNode(value_type _val)
{
	node * n = new node;
	n->parent = 0;
	n->left = 0;
	n->right = 0;
	n->color = node_red;
	n->val = _val;
	return n;
}
void My_Rb_Tree::DestoryNode(node * &_n)
{
	delete _n;
	_n = 0;
}
void My_Rb_Tree::RotateLeft(node * _cur)
{
	node * _root = Root();
	node * r = _cur->right;
	if (!r)
	{
		return;
	}
	if ( _cur ==_root )
	{
		_root = r;
		r->parent = _cur->parent;
		_cur->parent->parent = r;
	}
	else
	{
	}
	r->parent = _cur->parent;
	if (_cur->parent->left == _cur)
	{
		r->parent->left = r;
	}
	else
	{
		r->parent->right = r;
	}
	_cur->right = r->left;
	if (r->left)
	{	
		_cur->right->parent = _cur;
	}
	r->left = _cur;
	_cur->parent = r;
}
void My_Rb_Tree::RotateRight(node * _cur)
{
	node * _root = Root();
	node * l = _cur->left;
	if (!l)
	{
		return;
	}
	if ( _cur == _root )
	{
		_root = l;
		l->parent = _cur->parent;//head
		l->parent->parent = l;// head->parent
	}
	else
	{
		l->parent = _cur->parent;
		if (l->parent->left == _cur)
		{
			l->parent->left = l;
		}
		else
		{
			l->parent->right = l;
		}
	}
	_cur->left = l->right;
	if (l->right)
	{
		_cur->left->parent = _cur;
	}
	l->right = _cur;
	_cur->parent = l;
}
void My_Rb_Tree::Rebalance(node * _cur)
{
	node * _root = Root();
	_cur->color = node_red;
	if (_cur->parent == head) // _cur is root node
	{
		_cur->color = node_black;
		return;
	}
	if ( _cur->parent->color == node_black ) // now is balance state.
	{
		return ;
	}
	// 根据原来的树是符合红黑规则,祖父节点必定为黑色
	while( (_cur != Root()) && (_cur->parent->color == node_red)) // 当前节点的父节点为红色,违反规则
	{
		if (_cur->parent->parent->left == _cur->parent)  // 父节点为左子节点
		{
			if(_cur->parent->parent->right
				&& _cur->parent->parent->right->color == node_red)  // 伯父节点为红
			{
				// 把父节点和伯父节点变成黑色,祖父节点变成红色
				_cur->parent->parent->right->color=node_black;
				_cur->parent->color = node_black;
				_cur->parent->parent->color = node_red;
				// 因为祖父节点为红色,需要继续向上测试是否满足规则
				_cur = _cur->parent->parent;
				continue;
			}
			else // 伯父节点为黑或不存在
			{
				if ( _cur == _cur->parent->right )
				{
					// 以父节点为轴,左旋转后变成两个左外节点连续为红。
					_cur = _cur->parent;
					RotateLeft(_cur/*,_root*/);
				}
				// 改变颜色,以祖父节点为轴,右旋转。
				_cur->parent->parent->color = node_red;
				_cur->parent->color = node_black;
				RotateRight(_cur->parent->parent/*,_root*/);
				// 此时进入下一次while判断跳出循环
			}
		}
		else // 父节点为右子节点,依照左子节点的同样方法解决。
		{
			if(_cur->parent->parent->left
				&& _cur->parent->parent->left->color == node_red)  // 伯父节点为红
			{
				// 把父节点和伯父节点变成黑色,祖父节点变成红色
				_cur->parent->parent->left->color=node_black;
				_cur->parent->color = node_black;
				_cur->parent->parent->color = node_red;
				// 因为祖父节点为红色,需要继续向上测试是否满足规则
				_cur = _cur->parent->parent;
				continue;
			}
			else // 伯父节点为黑或不存在
			{
				if ( _cur == _cur->parent->left )
				{
					// 以父节点为轴,右旋转后变成两个右外节点连续为红。
					_cur = _cur->parent;
					RotateRight(_cur/*,_root*/);
				}
				// 改变颜色,以祖父节点为轴,左旋转。
				_cur->parent->parent->color = node_red;
				_cur->parent->color = node_black;
				RotateLeft(_cur->parent->parent/*,_root*/);
				// 此时进入下一次while判断跳出循环
			}
		}
	}//end while
	_root->color = node_black;
}
node * My_Rb_Tree::InsertUnique(value_type in_val)
{
	node * y = head;
	node * x = Root();
	bool comp = true;
	while( x )//一层一层深入找到合适的插入点
	{
		y = x;
		comp = ( in_val < x->val );
		if (in_val == x->val)
		{
			return 0;
		}
		x = comp ? x->left : x->right;
	}
	return Insert(y,x,in_val);
}
node * My_Rb_Tree::Insert(node * in_parent, node * in_cur, value_type in_value)
{
	node * new_node = CreateNode(in_value);
	if (in_parent == head) // 插入的是根节点
	{
		head->parent = new_node;
		head->left = new_node;
		head->right = new_node;
		new_node->parent = head;
		new_node->color = node_black;
	}
	else // 插入的是非根节点
	{
		if ( new_node->val < in_parent->val )
		{
			in_parent->left = new_node;
			if (in_parent == head->left) // 若插入点的父节点是最小节点,更新最小值节点指针
			{
				head->left = new_node;
			}
		}
		else
		{
			in_parent->right = new_node;
			if (in_parent == head->right)// 若插入点的父节点是最大节点,更新最大值节点指针
			{
				head->right = new_node;
			}
		}
		new_node->parent = in_parent;
		if (in_parent == head)
		{
			head->parent = new_node;
			in_parent->parent = Root();
		}
	}
	Rebalance(new_node/*,head->parent*/);
	node_count++;
	return new_node;
}
// 未实现,这个函数比较复杂
void My_Rb_Tree::RebalanceForErase(node * _cur)
{
	return;
}
// 依赖RebalanceForErase的实现
void My_Rb_Tree::Erase(node * in_cur)
{
	return;
}
node * My_Rb_Tree::Find(value_type _val)
{
	node * _t = Root();
	while(_t)
	{
		if (_t->val == _val)
		{
			return _t;
		}
		else if (_t->val > _val)
		{
			_t = _t->right;
		}
		else
		{
			_t = _t->left;
		}
	}
	return 0;
}


开心洋葱 , 版权所有丨如未注明 , 均为原创丨未经授权请勿修改 , 转载请注明C++红黑树的实现(int精简版)
喜欢 (0)
加载中……