中国科技大学算法导论-第二次实验报告.docx

第二次实验报告 红黑树

1.红黑树
1.1 需求分析
本实验要求实现红黑树各种操作如SEARCH ， PREDECESOR ， SUCCESSOR ，
MINIMUM，MAXIMUM，INSERT，DELETE 等。
红黑树是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途
是实现关联数组。它是在1972 年由Rudolf Bayer 发明的，他称之为"对称二叉B 树"，它现
代的名字是在Leo J. Guibas 和Robert Sedgewick 于1978 年写的一篇论文中获得的。它是
复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的: 它可以在O(log
n)时间内做查找，插入和删除，这里的n 是树中元素的数目。
红黑树是每个节点都带有颜色属性的二叉查找树，颜色或红色或黑色。在二叉查找树强
制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求:
1. 每个结点或红或黑。
2. 根结点为黑色。
3. 每个叶结点(实际上就是NULL 指针)都是黑色的。
4. 如果一个结点是红色的,那么它的周边3 个节点都是黑色的。
5. 对于每个结点,从该结点到其所有子孙叶结点的路径中所包含的黑色结点个数都一
样。这些约束强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能
路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最
坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都
是高效的，而不同于普通的二叉查找树。
要知道为什么这些特性确保了这个结果，注意到属性5 导致了路径不能有两个毗连的红
色节点就足够了。最短的可能路径都是黑色节点，最长的可能路径有交替的红色和黑色节点。
因为根据属性4 所有最长的路径都有相同数目的黑色节点，这就表明了没有路径能多于任何其他路径的两倍长。在很多树数据结构的表示中，一个节点有可能只有一个子节点，而叶子节点包含数据。用这种范例表示红黑树是可能的，但是这会改变一些属性并使算法复杂。为此，本文中我们使用"nil 叶子" 或"空(null)叶子"。
1.2 算法设计
操作SEARCH,，PREDECESOR，SUCCESSOR，MINIMUM，MAXIMUM 与二查检索
树的对应操作几乎相同。这里只介绍旋转、插入、删除。
1.2.1 旋转
由于插入、删除操作对树作了修改，结果可能违反红黑树的五个性质。为保持这些性质，
就要改变树中某些结点的颜色以及指针结构。指针结构的修改通过旋转来完成。

当在某个结点x 上做左旋时，假设它的有孩子y 不是nil[T]，左旋以x 与y 之间的链为
“支轴”进行。它使y 成为该子树新的根，x 成为y 的左孩子，而y 的左孩子成为x 的孩
子。右旋与左旋对称。左旋代码如下：
void RBLeftRotate(RBTree * T,RBTreeNode * x)
{
RBTreeNode * y = x->right;
x->right = y->left;
if(y->left != T->NIL)
y->left->parent = x;
y->parent = x->parent;
if(x->parent == T->NIL)
T->root = y;
else if(x->parent->left ==x)
x->parent->left = y;
else
x->parent->right =y;
y->left = x;
x->parent = y;
}

1.2.2 插入
向一颗含n 个结点的红黑树插入一个结点z 的操作可在O(lgn)时间完成。利用二叉查找
树的Tree_Insert 过程， 将z 插入树内， 并将其着红色。为保证红黑树的性质，调用
RB_INSERTT_FIXUP 来对结点重新着色并旋转。RB_INSERTT_FIXUP 代码如下：
void RBTreeInsertFixup(RBTree * T,RBTreeNode * z)
{

RBTreeNode * y;
if(z->parent == T->NIL)//z是根节点
{
z->color = BLACK;
return;
}
if(z->parent->color == BLACK)//这种情况下是平衡的
{
return;
}
//一直循环，直到z的父节点的颜色为黑色
while(z->parent->color == RED)
{
if(z->parent == z->parent->parent->left)//当z的父节点是z祖父节点的左孩子时
{
y = z->parent->parent->right;//y是z的叔叔
//case1:z的叔叔y 的颜色为红色
if(y->color == RED)
{
z->parent->color = BLACK;
y->color = BLACK;
z->parent->parent->color = RED;
z = z->parent->parent;
}
else
{
if(z == z->parent->right)//case2:z的叔叔y 的颜色为黑色并且z是它父节点的右孩子
{
z = z->parent;
RBLeftRotate(T,z);
}
//case3:z的叔叔y 的颜色为黑色并且z是它父节点的左孩子
z->parent->color =BLACK;
z->parent->parent->color = RED;
RBRightRotate(T,z->parent->parent);
}
}//当z的父节点是z祖父节点的右孩子时
else //如果z的父节点是其祖父节点的右孩子
{
y = z->parent->parent->left;//y是z的叔叔节点
if(y->color == RED)//case1：z的叔叔节点为红色，则z的父节点BLACK，祖父节点RED，叔叔节点BLACK均变色
{
z->parent->color = BLACK;
y->color = BLACK;
z->parent->parent->color = RED;
z = z->parent->parent;
}
else
{
if(z == z->parent->left)//case2:z的叔叔y的颜色为黑色并且z是它父节点的左孩子
{
z = z->parent;
RBRightRotate(T,z);
}
//case3:z的叔叔y的颜色为黑色并且z是它父节点的右孩子
z->parent->color = BLACK;
z->parent->parent->color = RED;
RBLeftRotate(T,z->parent->parent);
}
}
}
T->root->color = BLACK;
}

当调用RB_INSERTT_FIXUP(T，z)时，while 有三种情况：
Case 1)：z 的叔叔y 是红色

只有在p[z]和y 都是红色的时候才会执行case 1。既然p[p[z]]是黑色的，可以将p[z]和
y 都着黑色，再将p[p[z]]着红色保持性质5，然后z=p[p[z]]来重复while 循环。
Case 2）：z 的叔叔y 是黑色，且z 的为p[z]的右孩子
Case 3）：z 的叔叔y 是黑色，且z 的为p[z]的左孩子

Case 2 与case 3 如上图。Case 2 中z 是p[z]的右孩子，利用左旋把case 2 转化为case 3，
因为z 与p[z]都是红色的，左旋对结点黑高度和性质5 每影响。在case 3 下可以通过改颜
色和旋转的方式到达平衡， 并且不再出现红色警戒，因为无需往上遍历。首先我们将红父
变成黑色，祖父变成红色，然后对祖父进行右旋转。这样我们可以看到，整颗树的黑高
- 4 -
不变，并且这颗树的左右子树也达到平衡。新的树根为黑色。

1.3 结果分析
根据每次从文件中读的数据，调用RB_Insert()。理论上红黑树结构应为下图，

由实验运行结果知，程序是正确的。

/*
* copyright@nciaebupt 转载请保留此标记
* 所有代码已经在linux g++ 下编译通过，直接拷贝运行即可 如有问题欢迎指正
* 红黑树（red-black tree）是许多“平衡的”查找树中的一种。
* 红黑树的性质:
* １、每个结点或是红的，或是黑的。
* ２、根结点是黑的。
* ３、每个叶结点（NIL）是黑的。
* ４、如果一个结点是红的，则它的两个儿子都是黑的。
* ５、对每个结点，从该结点到其子孙的所有路径上包含相同数目的黑结点。
* 红黑树的结点比普通的二叉查找树的结点多了一个颜色属性。
*/
#include <iostream>
#include <vector>
using namespace std;

//将RED,BLACK颜色值定义成枚举类型
enum RBCOLOR {RED,BLACK};

//定义红黑树节点的数据结构
struct RBTreeNode
{
int key;
RBCOLOR color;
RBTreeNode * left;
RBTreeNode * right;
RBTreeNode * parent;
};
//定义红黑树的数据结构
struct RBTree
{
RBTreeNode * root;

RBTreeNode * NIL;
};

void RBTreeInsertFixup(RBTree * T,RBTreeNode * z);

//实现红黑树的左旋操作
void RBLeftRotate(RBTree * T,RBTreeNode * x)
{
RBTreeNode * y = x->right;
x->right = y->left;
if(y->left != T->NIL)
y->left->parent = x;
y->parent = x->parent;
if(x->parent == T->NIL)
T->root = y;
else if(x->parent->left ==x)
x->parent->left = y;
else
x->parent->right =y;
y->left = x;
x->parent = y;
}

//实现红黑树的右旋操作
void RBRightRotate(RBTree * T,RBTreeNode * x)
{
RBTreeNode * y = x->left;
if(x->left == T->NIL)
return;
x->left = y->right;
if(y->right != T->NIL)
{
y->right->parent = x;
}

y->parent = x->parent;
if(x->parent == T->NIL)
T->root = y;
else
{
if(x->parent->left == x)
x->parent->left = y;
else
x->parent->right = y;
}

y->right = x;
x->parent = y;
}

//红黑树插入
void RBTreeInsert(RBTree * T,RBTreeNode * z)
{
RBTreeNode * y = T->NIL;
RBTreeNode * x = T->root;
while(x != T->NIL)
{
y = x;
if(z->key <= x->key)
x = x->left;
else
x = x->right;
}
z->parent = y;
if(y == T->NIL)
T->root = z;
else
{
if(z->key <= y->key)
{
y->left = z;
}
else
{
y->right = z;
}
}

RBTreeInsertFixup(T,z);

}

//红黑树插入对节点重新着色
void RBTreeInsertFixup(RBTree * T,RBTreeNode * z)
{

RBTreeNode * y;
if(z->parent == T->NIL)//z是根节点
{
z->color = BLACK;
return;
}
if(z->parent->color == BLACK)//这种情况下是平衡的
{
return;
}
//一直循环，直到z的父节点的颜色为黑色
while(z->parent->color == RED)
{
if(z->parent == z->parent->parent->left)//当z的父节点是z祖父节点的左孩子时
{
y = z->parent->parent->right;//y是z的叔叔
//case1:z的叔叔y 的颜色为红色
if(y->color == RED)
{
z->parent->color = BLACK;
y->color = BLACK;
z->parent->parent->color = RED;
z = z->parent->parent;
}
else
{
if(z == z->parent->right)//case2:z的叔叔y 的颜色为黑色并且z是它父节点的右孩子
{
z = z->parent;
RBLeftRotate(T,z);
}
//case3:z的叔叔y 的颜色为黑色并且z是它父节点的左孩子
z->parent->color =BLACK;
z->parent->parent->color = RED;
RBRightRotate(T,z->parent->parent);
}
}//当z的父节点是z祖父节点的右孩子时
else //如果z的父节点是其祖父节点的右孩子
{
y = z->parent->parent->left;//y是z的叔叔节点
if(y->color == RED)//case1：z的叔叔节点为红色，则z的父节点BLACK，祖父节点RED，叔叔节点BLACK均变色
{
z->parent->color = BLACK;
y->color = BLACK;
z->parent->parent->color = RED;
z = z->parent->parent;
}
else
{
if(z == z->parent->left)//case2:z的叔叔y的颜色为黑色并且z是它父节点的左孩子
{
z = z->parent;
RBRightRotate(T,z);
}
//case3:z的叔叔y的颜色为黑色并且z是它父节点的右孩子
z->parent->color = BLACK;
z->parent->parent->color = RED;
RBLeftRotate(T,z->parent->parent);
}
}
}
T->root->color = BLACK;
}

//中序遍历红黑树
void InorderRBTreeWalk(RBTree * T,RBTreeNode * x)
{
if(x != T->NIL)
{
InorderRBTreeWalk(T,x->left);
cout<<x->key;
cout<<" "<<x->color<<endl;
InorderRBTreeWalk(T,x->right);
}
}

void preorderRBTreeWalk(RBTree * T,RBTreeNode * x)
{
if(x != T->NIL)
{ cout<<x->key;
cout<<" "<<x->color<<endl;
preorderRBTreeWalk(T,x->left);

preorderRBTreeWalk(T,x->right);
}
}

int main(int argc, char **argv)
{
//15,5,3,12,10,13,6,7,16,20,18,23
RBTree * T = new RBTree;

T->NIL = new RBTreeNode;

T->NIL->color = BLACK;
T->NIL->key = 10000;
T->NIL->left = NULL;
T->NIL->parent = NULL;
T->NIL->right = NULL;
T->root = T->NIL;

vector<int> vi;

// vi.push_back(999);
vi.push_back(15);
vi.push_back(5);
vi.push_back(3);
// vi.push_back(1);
vi.push_back(13);
vi.push_back(6);
vi.push_back(7);
vi.push_back(70);
vi.push_back(16);
vi.push_back(20);
vi.push_back(18);
vi.push_back(23);

//建立红黑树
cout<<"\n\ncreate the red-black tree:"<<endl;
for(vector<int>::iterator it = vi.begin(); it != vi.end();++it)
{
RBTreeNode * p = new RBTreeNode;
p->color = RED;
p->key = *it;
p->left = T->NIL;
p->parent = T->NIL;
p->right = T->NIL;
cout<<"Insert key : "<<p->key<<endl;
RBTreeInsert(T,p);
}
cout<<"---------------------------------"<<endl;
//中序遍历红黑树
cout<<"the inOrder the red-black tree is :"<<endl;

InorderRBTreeWalk(T,T->root);
//先序遍历红黑树
cout<<"the preOrder the red-black tree is :"<<endl;
preorderRBTreeWalk(T,T->root);

cout<<"---------------------------------"<<endl;

return 0;
}