首页 > 代码库 > 算法导论-------------红黑树
算法导论-------------红黑树
红黑树是一种二叉查找树，但在每个结点上增加了一个存储位表示结点的颜色，可以是RED或者BLACK。通过对任何一条从根到叶子的路径上各个着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，因而是接近平衡的。本章主要介绍了红黑树的性质、左右旋转、插入和删除。重点分析了在红黑树中插入和删除元素的过程，分情况进行详细讨论。一棵高度为h的二叉查找树可以实现任何一种基本的动态集合操作，如SEARCH、PREDECESSOR、SUCCESSOR、MIMMUM、MAXMUM、INSERT、DELETE等。当二叉查找树的高度较低时，这些操作执行的比较快，但是当树的高度较高时，这些操作的性能可能没有链表好。红黑树（red-black tree）是一种平衡的二叉查找树，它能保证在最坏情况下，基本的动态操作集合运行时间为O(lgn)。本章内容有些复杂，看了两天，才大概清楚其插入和删除过程，日后需要经常回顾，争取完全消化掉。红黑树的用途非常广泛，例如STL中的map就是采用红黑树实现的，效率非常之高，有机会可以研究一下STL的源代码。
不说了，看了两天的算法导论，终于把红黑树实现了，为了下半辈子过的好点，我也是蛮拼的
。
红黑树的5个重要的性质：
（1）每个结点或是红色，或是黑色。
（2）根结点是黑色。
（3）每个叶子结点（NIL）是黑色。
（4）如果有一个结点是红色，则它的两个儿子都是黑色。
（5）对每个结点，从该结点到其孙子结点的所有路径上包含相同数目的黑色结点。
引理：一棵有n个内结点的红黑树的高度之多为2lg(n+1)。
还有一条重要性质：红黑树会确保没有一条路径会比其它路径长出两倍。
红黑树的一些操作在算法导论上都有详细的讲解，还有推理过程，讲的非常仔细，需要花一定的时间去理解，俺奋斗了2天，周末放假都呆在家里面没出去，这就是做一个码农的生活.
写了一个晚上好几个小时都在的调试代码，因为自己的粗心，在代码中对称操作的时候，有一个地方左右没有改过来导致我改了几个小时，NND，。
//*********************************************************************/
//time:2014.12.8 0:22
//author：ugly_chen(stallman)
//csdn: http://blog.csdn.net/chenxun_2010
//*********************************************************************/
#include<iostream>
#include<stack>
using namespace std;
static const int RED = 0;
static const int BLACK = 1;
template <class T>
class Red_Black_Tree_Node
{
public:
Red_Black_Tree_Node(T k) :key(k), color(BLACK), p(NULL), left(NULL), right(NULL) {}
T key;
int color;
Red_Black_Tree_Node<T>* p;
Red_Black_Tree_Node<T>* left;
Red_Black_Tree_Node<T>* right;
};
template <class T>
class Red_Black_Tree
{
public:
Red_Black_Tree();
Red_Black_Tree_Node<T>* get_root() const;//获取根节点
Red_Black_Tree_Node<T>* search_tree_node(const T& k)const;//查找关键字为k的节点
Red_Black_Tree_Node<T>* tree_maxmum(Red_Black_Tree_Node<T> *root) const;//查找最大关键字的节点
Red_Black_Tree_Node<T>* tree_minmum(Red_Black_Tree_Node<T> *root) const;//查找最小关键字的节点
Red_Black_Tree_Node<T>* tree_successor(Red_Black_Tree_Node<T> *pnode) const;//查找后继节点
Red_Black_Tree_Node<T>* tree_predecessor(Red_Black_Tree_Node<T> *pnode) const;//查找钱继节点
void left_rotate(Red_Black_Tree_Node<T> *pnode);//左旋转操作
void right_rotate(Red_Black_Tree_Node<T> *pnode);//右旋转操作
void rb_insert_fixup(Red_Black_Tree_Node<T> *pnode);//修正插入操作引起的违反红黑树性质的行为
void rb_delete_fixup(Red_Black_Tree_Node<T> *pnode);//修正删除操作引起的违反红黑树性质的行为
void rb_insert(Red_Black_Tree_Node<T>* z);//插入节点
void rb_delete(Red_Black_Tree_Node<T>* z);//删除节点
void inorder_tree_walk()const;//中序遍历红黑树：这样就是从小到大的顺序输出红黑树
void make_empty(Red_Black_Tree_Node<T>* root);
//~Red_Black_Tree();
public:
static Red_Black_Tree_Node<T> *NIL;
private:
Red_Black_Tree_Node<T>* root;
};
//初始化nil
template <class T>
Red_Black_Tree_Node<T>* Red_Black_Tree<T>::NIL = new Red_Black_Tree_Node<T>(-1);
//初始化root节点 利用默认构造函数
template <class T>
Red_Black_Tree<T>::Red_Black_Tree()
{
root = NIL;
};
//---------------------------------------------------------------------------------------
template<class T>
Red_Black_Tree_Node<T>* Red_Black_Tree<T>::get_root() const//获取根节点
{
return root;
}
//------------------------------------------------------------------------------------------
//查找树中关键字key的节点
template <class T>
Red_Black_Tree_Node<T>* Red_Black_Tree<T>::search_tree_node(const T& key) const
{
Red_Black_Tree_Node<T>* p = root;
while (p != NIL)
{
if (p->key == key)
break;
else if (p -> key > key)
p = p->left;
else
p = p->right;
}
return p;
}
//----------------------------------------------------------------------------------------
//查找最大关键字的节点
template <class T>
Red_Black_Tree_Node<T>* Red_Black_Tree<T>::tree_maxmum(Red_Black_Tree_Node<T> *root) const
{
Red_Black_Tree_Node<T>* p = root;
while (p->right != NIL)
{
p = p->right;
}
return p;
}
//------------------------------------------------------------------------------------------
//查找数中最小关键字的节点
template<class T>
Red_Black_Tree_Node<T>* Red_Black_Tree<T>::tree_minmum(Red_Black_Tree_Node<T>* root) const
{
Red_Black_Tree_Node<T>* p = root;
while (p->left != NIL)
{
p = p->left;
}
return p;
}
//----------------------------------------------------------------------------------------------
//查找后继节点:大于x的最小点
template<class T>
Red_Black_Tree_Node<T>* Red_Black_Tree<T>::tree_successor(Red_Black_Tree_Node<T>* x) const
{
if (x->right != NIL)
return tree_minmum(x->right);
Red_Black_Tree_Node<T>* y = x->p;
while (y != NIL &&x == y->right)
{
x = y;
y = y->p;
}
return y;
}
//--------------------------------------------------------------------------------------------------
//查找前驱节点://查找中序遍历下x的前驱，即小于x的最大值
template<class T>
Red_Black_Tree_Node<T>* Red_Black_Tree<T>::tree_predecessor(Red_Black_Tree_Node<T> *x) const
{
if (x->left != NIL)
return tree_maxmum(x->left);
Red_Black_Tree_Node<T>* y = x->p;
while (y != NIL&&x == y->left)
{
x = y;
y = y->p;
}
return y;
}
//----------------------------------------------------------------------------------------------------
//左旋转
template<class T>
void Red_Black_Tree<T>::left_rotate(Red_Black_Tree_Node<T> *x)
{
Red_Black_Tree_Node<T> *y = x->right;
x->right = y->left;
if (y->left != NIL)
y->left->p = x;
y->p = x->p;
if (x->p == NIL)
root = y;
else if (x == x->p->left)
x->p->left = y;
else
x->p->right = y;
y->left = x;
x->p = y;
}
//右旋转
//------------------------------------------------------------------------------------------------------
template<class T>
void Red_Black_Tree<T>::right_rotate(Red_Black_Tree_Node<T> *x)
{
Red_Black_Tree_Node<T> *y = x->left;
x->left = y->right;
if (y->right != NIL)
y->right->p = x;
y->p = x->p;
if (x->p == NIL)
root = y;
else if (x == x->p->left)
x->p->left = y;
else
x->p->right = y;
y->right = x;
x->p = y;
}
//--------------------------------------------------------------------------------
//插入的子过程：修正插入过后可能违反红黑树的节点
template<class T>
void Red_Black_Tree<T>::rb_insert_fixup(Red_Black_Tree_Node<T>* z)
{
Red_Black_Tree_Node<T> *y;
while (z->p->color == RED)
{
if (z->p == z->p->p->left)//z.p是z祖父的左孩子
{
y = z->p->p->right;
if (y->color == RED)//case1 z的叔节点为红色
{
z->p->color = BLACK;
y->color = BLACK;
z->p->p->color = RED;
z = z->p->p;
}
else //case 2 or case 3：叔节点是黑色
{
if (z == z->p->right)//z是右孩子
{
z = z->p;
left_rotate(z);
}
//case3 z为左孩子
z->p->color = BLACK;
z->p->p->color = RED;
right_rotate(z->p->p);
}
}
else if (z->p == z->p->p->right)//z.p是z祖父的右孩子，和上边情况相同也有三种情形
{
y = z->p->p->left;
if (y->color == RED)
{
z->p->color = BLACK;
y->color = BLACK;
z->p->p->color = RED;
z = z->p->p;
}
else
{
if (z == z->p->left)
{
z = z->p;
right_rotate(z);
}
z->p->color = BLACK;
z->p->p->color = RED;
left_rotate(z->p->p);
}
}
}
root->color = BLACK;
}
//-------------------------------------------------------------------------------------------
//修正删除rb_tree某个节点带来的可能违反红黑树性质的行为
template<class T>
void Red_Black_Tree<T>::rb_delete_fixup(Red_Black_Tree_Node<T> *x)
{
Red_Black_Tree_Node<T> *w;
//如果这个额外的黑色在一个根结点或一个红结点上，结点会吸收额外的黑色，成为一个黑色的结点
while (x != root&&x->color == BLACK)
{
//若x是其父的左结点（右结点的情况相对应）
if (x == x->p->left)
{
//令w为x的兄弟，根据w的不同，分为三种情况来处理
//执行删除操作前x肯定是没有兄弟的，执行删除操作后x肯定是有兄弟的
w = x->p->right;
if (w->color == RED)// case 1 w为红色
{
w->color = BLACK;
x->p->color = RED;
left_rotate(x->p);
w = x->p->right;//由这种情形可以进入2 3 4任何一种情形
}
if (w->left->color == BLACK && w->right->color == BLACK)//case 2：w为黑色，w的两个孩子也都是黑色
{
w->color = RED;
x = x->p;
}
else //case 3 w是黑色的,w->left是红色的,w->right是黑色的
{
if (w->right->color == BLACK)
{
w->left->color = BLACK;
w->color = RED;
right_rotate(w);
w = x->p->right;
}
//case 4：w是黑色的,w->left可以是红色也是可以是黑色,w->right 是红色
//修改 w 和 x.p的颜色
w->color = x->p->color;
x->p->color = BLACK;
w->right->color = BLACK;
left_rotate(x->p);
x = root;
}
}
else if (x == x->p->right)//x为其父节点的右孩子
{
w = x->p->left;
if (w->color == RED)//case1,w.color为红色
{
w->color = BLACK;
x->p->color = RED;
right_rotate(x->p);
w = x->p->left;//令w为x的兄弟，转为2.3.4三种情况之一
}
if (w->right->color == BLACK && w->left->color == BLACK)//case2：w为黑色，w的两个孩子也都是黑色
{
w->color = RED;
x = x->p;
}
else //case3：w是黑色的,w->left黑色,w->right是红色（与上面的相反：w->left是红色的,w->right是黑色的）
{
if (w->left->color == BLACK)
{
w->right->color = BLACK;
w->color = RED;
left_rotate(w);
w = x->p->left;////令w为x的新兄弟，进入case4
}
//case4：w是黑色的, w->left是红色 , w->right是可以是红色也可以是黑色.
//修改w和p[x]的颜色
w->color = x->p->color;
x->p->color = BLACK;
w->left->color = BLACK;
right_rotate(x->p);
//此时调整已经结束，将x置为根结点是为了结束循环
x = root;
}
}
}
x->color = BLACK;//while循环结束的时候x的的颜色为红色，用来吸收黑色.
}
//---------------------------------------------------------------------------------------------
//插入操作：rb_insert
template<class T>
void Red_Black_Tree<T>::rb_insert(Red_Black_Tree_Node<T>* z)
{
Red_Black_Tree_Node<T>* y = NIL;
Red_Black_Tree_Node<T>* x = root;
while (x != NIL)//找到插入的位置
{
y = x;
if (z->key < x->key)
x = x->left;
else
x = x->right;
}
z->p = y;
if (y == NIL)
root = z;
else if (z->key < y->key)
y->left = z;
else
y->right = z;
z->left = NIL;
z->right = NIL;
z->color = RED;
rb_insert_fixup(z);
}
//-------------------------------------------------------------------------------
//节点删除操作：rb_delete
template<class T>
void Red_Black_Tree<T>::rb_delete(Red_Black_Tree_Node<T>* z)
{
Red_Black_Tree_Node<T>* y;
Red_Black_Tree_Node<T>* x;
if (z->left == NIL || z->right == NIL)
y = z;
else y = tree_successor(z);
if (y->left != NIL)
x = y->left;
else x = y->right;
x->p = y->p;
if (y->p == NIL)
root = x;
else if (y == y->p->left)
y->p->left = x;
else
y->p->right = x;
if (y != z)
z->key = y->key;
//如果被删除的结点是黑色的，则需要调整
if (y->color == BLACK)
rb_delete_fixup(x);
}
//-----------------------------------------------------------------------------------------
//中序遍历红黑树，利用stack的功能从小到大输出红黑树
template <class T>
void Red_Black_Tree<T>::inorder_tree_walk() const
{
if (NULL != root)
{
stack<Red_Black_Tree_Node<T>* > s;
Red_Black_Tree_Node<T> *p;
p = root;
while (NIL != p || !s.empty())
{
if (NIL != p)
{
s.push(p);
p = p->left;
}
else
{
p = s.top();
s.pop();
cout << p->key << ":";
if (p->color == BLACK)
cout << "Black" << endl;
else
cout << "Red" << endl;
p = p->right;
}
}
}
}
int main()
{
Red_Black_Tree<int> tree ;
int s[6] = { 41, 38, 31, 12, 19, 8 };
int i;
for (i = 0; i< 6; i++)
{
Red_Black_Tree_Node<int> *z = new Red_Black_Tree_Node<int>(s[i]);
tree.rb_insert(z);
}
cout << "根节点是：" << tree.get_root()->key << endl;
tree.inorder_tree_walk();
int s2[10] = { 8, 12, 20, 38, 39, 48,666,999,1,100 };
for (i = 0; i< 6; i++)
{
Red_Black_Tree_Node<int> *z = tree.search_tree_node(s2[i]);
if (z != tree.NIL )
tree.rb_delete(z);
}
cout << "删除操作后的红黑树根节点是："<<tree.get_root()->key << endl;
tree.inorder_tree_walk();
return 0;
}
最后要感谢两位大牛：
http://www.cnblogs.com/Anker/archive/2013/01/30/2882773.html
http://blog.csdn.net/mishifangxiangdefeng/article/details/7718917
算法导论-------------红黑树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。