红黑树的使用详解
(学习的参考资料主要是《算法导论》)
首先是红黑树的性质。一棵二叉查找树满足以下的红黑性质,则为一棵红黑树。
1)每个结点或是红的,或是黑的。
2)根结点是黑的。
3)每个叶结点(NIL)是黑的。
4)红结点的两个孩子都是黑的。
5)对任意结点,从它到其子孙结点所有路径上包含相同数目的黑结点。
初学时并不在意,但是仔细研究相关算法就会知道,算法都是围绕保持这些性质来进行的。性质5)保证了红黑树使用时的高效。定理证明了n个内结点的红黑树高度至多为2lg(n+1)。
不同于一般二叉查找树,红黑树一般采用一个哨兵结点代表NIL,这对算法的使用提供了很多方便,具体编写时可以体会的到。哨兵设置为黑色,它是根的父结点,也是所有的叶子结点。而它的其他域可以设置为任意值。我用关键字把它和普通的结点进行区分。
旋转是红黑树的特有操作。以前搞不清左旋和右旋究竟是如何进行的,现在比较明白,可以这样概括:以x结点左旋即为,使x从一棵子树的根变成这个子树的左孩子;对称的,同理。旋转是红黑树插入和删除时为了维持红黑性质而可能进行的操作。
插入的原理:
除了空指针的处理,插入的过程和二叉查找树相同,但是插入后需要进行独有的调整算法以保证红黑性质。下面的描述是我的个人概括,看上去比较混乱,和算法以及实例相对照着可能容易理解一些。
新插入的点z直接染成红色,再根据其父结点是否为红(与性质4冲突)和插入的结点是否为根(与性质2冲突)进行调整。后者直接把根染黑即可。
对于前者,找到z的叔叔y(找叔叔y虽然需要分情况处理,但比较简单,不详写),根据y是红还是黑进一步分清况。z的父亲为左孩子时,前者只需要把z的父亲和叔叔同时变黑、z的父结点的父结点变红、令z指向z的父结点的父结点迭代处理即可;后者进一步分z是左孩子还是右孩子处理。z是左孩子时直接以z的父结点进行旋转让z的父亲左旋并成为新z即成为后一种情况。在后一种情况中,将z的父亲染黑,祖父染红,以z的祖父右旋就能获得。
删除的原理:
算法导论上的删除算法把两种情况同时进行处理,确实很有技巧。红黑树的删除除了最后需要根据对于删除结点的颜色来判断是否需要进行调整外,和普通的二叉查找树没有区别,这里稍微做一下分析。
RB-DELETE(T,z) // 情况1 || 情况2
ifleft[z]=nil[T]orright[z]=nil[T] // z最多一个孩子时 || z有两个孩子时
theny←z // 令y=z || 令y是z后继(此时y必然不是z的右孩子)
elsey←TREE-SUCCESSOR(z) //===============================================================================
ifleft[y]≠nil[T] // 令x为y的孩子或哨兵 || 令x是y的右孩子(x必然不为左孩子,否则y不可能是z的后继)
thenx←left[y] // || 将来x会代替y的位置
elsex←right[y] //================================================================================
p[x]←p[y] //
ifp[y]=nil[T] //
thenroot[T]←x // x与x的新父亲之间建立关系
elseify=left[p[y]] //
thenleft[p[y]]←x //
elseright[p[y]]←x //=================================================================================
ify!≠z // ||
thenkey[z]←key[y] // 删完后整体上移 || 替代,用于替代的原结点删除
copyy"ssatellitedataintoz // ||
ifcolor[y]=BLACK // ||
thenRB-DELETE-FIXUP(T,x) // ||
returny
删除后,如果删除的结点是黑色,可能会造成性质2、4、5的违反。调整算法思想是使得代替y的x多染一层黑色而成为红黑或二重黑色结点。这个处理只是用指针x标示,并不用改变结点color域的内容。调整算法按8种情况,其中两两对称,只描述4种。
用w表示x的兄弟。
情况1为w红。此时调整w为黑,p[x]为红,以p[x]左旋,w指向x的新兄弟,此时则成为情况2或3或4。
情况2为w黑,且w的两个孩子均黑。此时把w染红,令p[x]成为新的x。这相当于把x剥离了一层黑色,使这层黑色上移。
情况3为w黑,w的左孩子为红,右孩子为黑。这时交换w和左孩子颜色,并对w右旋,此时成为情况4。
情况4为w黑,w有孩子为红。这时使w成为p[x]的颜色,p[x]置为黑色,w的右孩子置为黑,对p[x]左旋。令x为根。这时相当于把原先x上的一重黑色传给了其父亲并于它一起下移,而w代替了其父亲原先的颜色和位置。这是不存在红黑结点或二重黑结点。
每次处理都判断x是否为根且x是否为黑。x不为根且为黑时才代表有红黑结点或二重黑结点,需要进行新一轮循环。循环结束后把根染黑就结束了。
最后附上一个我自己用C写的红黑树操作。插入操作验证无误,删除操作验证次数有限,可能有bug存在。
#include <stdlib.h>
#include <stdio.h>
#defineT_nil-1
//T_nilisakeyofnil[T]inthebook.
#defineRED 1
#defineBLACK 0//T_nilisBLACK
//T_nil"spisitself.needtoset.
structrb_tree{
intcolor;
intkey;//normallyapositivenumber.
structrb_tree*left;
structrb_tree*right;
structrb_tree*p;
};
intrb_walk(structrb_tree*node){
if(node->key!=T_nil){
rb_walk(node->left);
printf("%d,coloris%s\n",node->key,(node->color?"RED":"BLACK"));
rb_walk(node->right);
}
return1;
}
structrb_tree*rb_search(structrb_tree*node,intk){
if((node->key==T_nil)||(node->key==k))
returnnode;
if(k<node->key)
returnrb_search(node->left,k);
else
returnrb_search(node->right,k);
}
structrb_tree*tree_minimum(structrb_tree*node){
if(node->key==T_nil)
returnnode;
while(node->left->key!=T_nil)
node=node->left;
returnnode;
}
structrb_tree*tree_maximum(structrb_tree*node){
if(node->key==T_nil)
returnnode;
while(node->right->key!=T_nil)
node=node->right;
returnnode;
}
structrb_tree*tree_successor(structrb_tree*node){
structrb_tree*y;
if(node->right->key!=T_nil)
returntree_minimum(node->right);
y=node->p;
while((y->key!=T_nil)&&(node==y->right)){
node=y;
y=y->p;
}
returny;
}
//3functionofbelowiscopyfromtree.
structrb_tree*left_rotate(structrb_tree*rb,structrb_tree*x){
structrb_tree*y;
//if(x->right->key==T_nil){
// printf("havenorightchild,rotationcancel.\n");
// returnrb;
//}
y=x->right;
x->right=y->left;
if(y->left->key!=T_nil)
y->left->p=x;
y->p=x->p;
if (x->p->key==T_nil)
rb=y;
elseif(x==x->p->left)
x->p->left=y;
else
x->p->right=y;
y->left=x;
x->p=y;
returnrb;
}
structrb_tree*right_rotate(structrb_tree*rb,structrb_tree*x){
structrb_tree*y;
//if(x->left->key==T_nil){
// printf("havenoleftchild,rotationcancel.\n");
// returnrb;
//}
y=x->left;
x->left=y->right;
if(y->right->key!=T_nil)
y->right->p=x;
y->p=x->p;
if(x->p->key==T_nil)
rb=y;
elseif(x==x->p->left)
x->p->left=y;
else
x->p->right=y;
y->right=x;
x->p=y;
returnrb;
}
structrb_tree*rb_insert_fixup(structrb_tree*rb,structrb_tree*z){
structrb_tree*y;
while(z->p->color==RED){
if(z->p==z->p->p->left){
y=z->p->p->right;
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->right){
z=z->p;
rb=left_rotate(rb,z);
}
z->p->color=BLACK;
z->p->p->color=RED;
rb=right_rotate(rb,z->p->p);
}
}
else{//sameasrightandleftexchanged
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;
rb=right_rotate(rb,z);
}
z->p->color=BLACK;
z->p->p->color=RED;
rb=left_rotate(rb,z->p->p);
}
}
}
rb->color=BLACK;
returnrb;
}
structrb_tree*rb_insert(structrb_tree*rb,intk){
structrb_tree*y=rb->p;
structrb_tree*x=rb;
structrb_tree*z;
z=(structrb_tree*)malloc(sizeof(structrb_tree));
z->key=k;
while(x->key!=T_nil){
y=x;
if(k<x->key)
x=x->left;
else
x=x->right;
}
z->p=y;
if(y->key==T_nil)
rb=z;
elseif(z->key<y->key)
y->left=z;
else
y->right=z;
z->left=rb->p;
z->right=rb->p;
z->color=RED;
returnrb_insert_fixup(rb,z);
}
structrb_tree*rb_delete_fixup(structrb_tree*rb,structrb_tree*x){
structrb_tree*w;
while((x!=rb)&&(x->color==BLACK)){
if(x==x->p->left){
w=x->p->right;
if(w->color==RED){
w->color=BLACK;
x->p->color=RED;
left_rotate(rb,x->p);
w=x->p->right;
}
if((w->left->color==BLACK)&&(w->right->color==BLACK)){
w->color=RED;
x=x->p;
}
elseif(w->right->color==BLACK){
w->left->color=BLACK;
w->color=RED;
right_rotate(rb,w);
w=x->p->right;
}
w->color=x->p->color;
x->p->color=BLACK;
w->right->color=BLACK;
left_rotate(rb,x->p);
x=rb;
}
else{//sameasrightandleftexchanged
w=x->p->left;
if(w->color==RED){
w->color=BLACK;
x->p->color=RED;
right_rotate(rb,x->p);
w=x->p->right;
}
if((w->right->color==BLACK)&&(w->left->color==BLACK)){
w->color=RED;
x=x->p;
}
elseif(w->left->color==BLACK){
w->right->color=BLACK;
w->color=RED;
left_rotate(rb,w);
w=x->p->left;
}
w->color=x->p->color;
x->p->color=BLACK;
w->left->color=BLACK;
right_rotate(rb,x->p);
x=rb;
}
}
x->color=BLACK;
}
structrb_tree*rb_delete(structrb_tree*rb,structrb_tree*z){
structrb_tree*x,*y;
if((z->left->key==T_nil)||(z->right->key==T_nil))
y=z;
elsey=tree_successor(z);
if(y->left->key!=T_nil)
x=y->left;
else
x=y->right;
x->p=y->p;
if(y->p->key==T_nil)
rb=x;
elseif(y==x->p->left)
y->p->left=x;
else
y->p->right=x;
if(y!=x)//copyy"sdatatoz
z->key=y->key;
if(y->color==BLACK)
rb_delete_fixup(rb,x);
free(y);
returnrb;
}
intmain(){
structrb_tree*p,*root;
structrb_treetree_nil={BLACK,T_nil,&tree_nil,&tree_nil,&tree_nil};
root=&tree_nil;
root=rb_insert(root,15);
root=rb_insert(root,5);
root=rb_insert(root,16);
root=rb_insert(root,3);
root=rb_insert(root,12);
root=rb_insert(root,20);
root=rb_insert(root,10);
root=rb_insert(root,13);
root=rb_insert(root,6);
root=rb_insert(root,7);
root=rb_insert(root,18);
root=rb_insert(root,23);
rb_walk(root);
p=rb_search(root,18);
root=rb_delete(root,p);
rb_walk(root);
return1;
}
相关文章
- 一体箱型无线型振弦传感器采集采发仪常见的使用注意事项
- 解决VSCode快捷键注释无法使用的情况
- 【说站】Python布尔索引的使用
- java使用xquery_如何使用Java XQuery
- Oracle回滚段使用查询代码详解
- nginx同时使用(http)80和(https)443端口详解程序员
- SQL Server 使用触发器(trigger)发送电子邮件步骤详解
- JNI动态注册native方法及JNI数据使用详解手机开发
- V8不再使用基准测试引擎 Octane详解架构师
- 关于时间,日期,星期,月份的算法(Java中Calendar的使用方法)详解编程语言
- 使用jetty实现小型的Servlet服务器详解编程语言
- Node.js中使用数据库详解编程语言
- Drools6从HelloWorld开始使用和学习详解编程语言
- 使用jdk的keytool 生成CA证书的方法详解编程语言
- Linux更新:使用GCC提升性能(linux更新gcc)
- MySQL函数大全,从基础函数到高级函数,用法详解(mysql中使用的函数)
- 1 MySQL 容器化上云,数据存储全方位2 使用容器将 MySQL 数据库部署到云端 3 流行软件 MySQL 上容器技术的应用 4 容器技术在 MySQL 软件上的实现 5 如何在 MySQL 上使用容器技术实现云上部署
- 使用SQL查询DB29中的XML数据
- C#使用DllImport调用非托管的代码的方法
- javascript:void(0)使用探讨
- python创建和使用字典实例详解
- C#标识符的使用小结
- 使用c#开发公众平台自定义菜单功能
- 使用jqueryprev()方法找到同级的前一个元素