这里先来说一下上篇文章没有说到的地方,在stl中,插入红黑树返回的是一个pair, 其中第二个元素表示成功与否,第一个元素表示插入成功的元素对应的迭代器或者插入失败(已经存在的键)的旧的迭代器~
好了,开始今天的主题——红黑树的删除操作~~~
首先,来回顾一下红黑树的性质,这东西是要时刻记在脑袋里面的:
1. 每一个节点多出一个关于颜色的性质:非黑即红
2. 根节点是黑色的
3. 每一个叶子节点(NULL)视为黑色
4. 如果一个节点为红色,那么它的两个孩子的颜色必须都为黑色
5. 对于任意节点来说,从其开始,至其任意子孙当中的叶子结点的每一条路径当中,所包含的黑色节点数目相同。
对于删除操作,对于二叉搜索树来讲,只需要考虑以下三种情况中的前两种,因为第三种可以将当前要删除节点的值与其后继节点的值相互调换,之后转变为情况1,或者情况2:
1) 叶子结点
2) 只有一个孩子不为空
3) 两个孩子都不为空
这样的话,如果要删除一个节点,就先按照正常的二叉搜索树来删除掉该节点,并且
记录注删除节点的颜色,以及递补上来节点的颜色(NULL视为黑色);如果我们只是如此的话,就可能会违背红黑树的性质2,4, 5。对于以上的情况,算法导论里面提出了一个“额外黑色”的概念,即如果被删除的节点的颜色为黑,需要将其原来的黑色额外的加入到递补上来的节点的颜色上,如果递补上来的颜色为红色,那么直接将其变为黑色即可,如果递补进来的节点为黑色,则黑色和额外的黑色无法累加,需要进行如下四张图的调整(调整的时候要看兄弟节点的颜色,且x为递补上来的节点,s为其兄弟节点):其中四张图的顺序依次为兄弟节点为红色、兄弟节点为黑色且两个侄子均为黑色、兄弟节点为黑色且近侄子为红色、兄弟节点为黑色且远侄子为红色,其中,只有情况4是可以肯定使得这个递归过程彻底结束的,所以,其他三种情况应该及可能的向其形式靠拢~
当递补上来的节点的兄弟节点为红色时,由于从根本上来讲,A的实际黑高比D(即C和E)低1,通过变换颜色以及旋转无法直接解决问题,,所以需要将x的兄弟变为黑色,以便后续求解,同时,需要保证B的parent的该子树下的黑高尽可能不变;
当x的兄弟节点为黑色,且两个侄子的颜色均为黑色的时候,最简单的做法就是将兄弟节点的颜色变为红色,x指向其父节点,递归向上,去除“额外的黑色”
由于下面一种情况是比较好解决的,所以这种情况就需要委屈一下,尽量变为下边一种情况喽~这里不要害怕E的颜色为红色,因为在下一步操作中,D的颜色会被变为黑色的~
这种情况是肯定会终止的,现在C,e, f 的黑高与A相同,B的parent的该方向的子树的黑高为:BH(A) + 1 + B->color==BLACK?1:0;即BH(D)
但是A所在的子树理应多出一个黑高才能使之结束,这样,就将B,D颜色对调,E的颜色置为黑色,对B再进行一次左旋就行了~
整个红黑树以及测试代码奉上:
-
#include <iostream>
-
-
using namespace std;
-
struct RB_tree_node{
-
int val;
-
bool color;// false: red; true: black
-
struct RB_tree_node *parent;
-
struct RB_tree_node *lchild;
-
struct RB_tree_node *rchild;
-
RB_tree_node(int value):val(value), color(false), parent(NULL), lchild(NULL), rchild(NULL){}
-
};
-
struct RB_tree_node *root = NULL;
-
struct RB_tree_node *Left_Rotate(struct RB_tree_node *x){
-
struct RB_tree_node *y = x->rchild;
-
bool flag = false;
-
if( root == x) flag = true;
-
x->rchild = y->lchild;
-
if( y->lchild != NULL) y->lchild->parent = x;
-
y->parent = x->parent;
-
if( !flag ){
-
if( x == x->parent->lchild)x->parent->lchild = y;
-
else x->parent->rchild= y;
-
}
-
y->lchild = x;
-
x->parent = y;
-
if(flag) root = y;
-
return y;
-
}
-
struct RB_tree_node *Right_Rotate(struct RB_tree_node *y){
-
struct RB_tree_node *x = y->lchild;
-
bool flag =false;
-
if( y == root) flag = true;
-
y->lchild = x->rchild;
-
if(x->rchild != NULL) x->rchild->parent = y;
-
x->parent = y->parent;
-
if(!flag){
-
if( y==y->parent->lchild) y->parent->lchild = x;
-
else y->parent->rchild = x;
-
}
-
x->rchild = y;
-
y->parent = x;
-
if(flag) root = x;
-
return x;
-
}
-
struct RB_tree_node *Get_Sibling(struct RB_tree_node *cur){
-
if( cur->parent == NULL) return NULL;
-
if( cur == cur->parent->lchild) return cur->parent->rchild;
-
else return cur->parent->lchild;
-
}
-
struct RB_tree_node *Get_Uncle(struct RB_tree_node *cur){
-
if(cur->parent == NULL) return NULL;
-
else return(Get_Sibling(cur->parent));
-
}
-
void insert_fix( struct RB_tree_node *cur){
-
while(cur->parent != NULL && cur->parent->color == false){
-
if(cur->parent == cur->parent->parent->lchild){
-
struct RB_tree_node *uncle = Get_Uncle(cur);
-
if(uncle != NULL && uncle->color == false){
-
cur->parent->color = true;
-
uncle->color = true;
-
cur->parent->parent->color = false;
-
cur = cur->parent->parent;
-
}
-
else{
-
if(cur == cur->parent->rchild){//内插,需要多一步旋转
-
Left_Rotate(cur->parent);
-
cur=cur->lchild;
-
}
-
//外插情况
-
cur->parent->color = true;
-
cur->parent->parent->color = false;
-
Right_Rotate(cur->parent->parent);
-
}
-
}else{//父节点是祖节点的右孩子
-
struct RB_tree_node *uncle = Get_Uncle(cur);
-
if(uncle != NULL && uncle->color == false){
-
cur->parent->color = true;
-
uncle->color = true;
-
cur->parent->parent->color = false;
-
cur = cur->parent->parent;
-
}
-
else{
-
if(cur == cur->parent->lchild){//内插,需要多一步旋转
-
Right_Rotate(cur->parent);
-
cur=cur->rchild;
-
}
-
//外插情况
-
cur->parent->color = true;
-
cur->parent->parent->color = false;
-
Left_Rotate(cur->parent->parent);
-
}
-
}
-
}
-
root->color = true;
-
}
-
void insert(int val){
-
struct RB_tree_node *cur = new RB_tree_node(val);
-
if( root == NULL){
-
cur->color = true; root = cur; return;
-
}
-
struct RB_tree_node *x = root, *y;
-
while(x != NULL){
-
y=x;
-
if (val < x->val) x = x->lchild;
-
else x = x->rchild;
-
}
-
if( val < y->val) y->lchild = cur;
-
else y->rchild = cur;
-
cur->parent = y;
-
if( y->color == false)insert_fix(cur);
-
}
-
struct RB_tree_node *Find(int val){
-
struct RB_tree_node *cur = root;
-
while( cur ){
-
if(cur->val == val) break;
-
else if(cur->val > val) cur = cur->lchild;
-
else cur = cur->rchild;
-
}
-
return cur;
-
}
-
void Transplant(struct RB_tree_node *u, struct RB_tree_node *v){
-
if( u->parent == NULL) root = v;
-
else if(u == u->parent->lchild) u->parent->lchild = v;
-
else u->parent->rchild = v;
-
if(v) v->parent = u->parent;
-
}
-
void Delete_fix(struct RB_tree_node *x){
-
while(x != root && x->color == true){
-
if(x == x->parent->lchild){
-
struct RB_tree_node *w = x->parent->rchild;
-
if( w->color == false){
-
w->color = true;
-
x->parent->color = false;
-
Left_Rotate(x->parent);
-
w = x->parent->rchild;
-
}
-
if( w->lchild->color==true && w->rchild->color == true){
-
w->color = false;x = x->parent;
-
}else{
-
if(w->rchild->color == true){
-
w->lchild->color = true;
-
w->color = false;
-
Right_Rotate(w);
-
w = x->parent->rchild;
-
}
-
w->color = x->parent->color;
-
x->parent->color = true;
-
w->rchild->color = true;
-
Left_Rotate(x->parent);
-
x = root;
-
}
-
}else{
-
struct RB_tree_node *w = x->parent->lchild;
-
if( w->color == false){
-
w->color = true;
-
x->parent->color = false;
-
Right_Rotate(x->parent);
-
w = x->parent->lchild;
-
}
-
if( w->lchild->color==true && w->rchild->color == true){
-
w->color = false;x = x->parent;
-
}else{
-
if(w->lchild->color == true){
-
w->rchild->color = true;
-
w->color = false;
-
Left_Rotate(w);
-
w = x->parent->lchild;
-
}
-
w->color = x->parent->color;
-
x->parent->color = true;
-
w->lchild->color = true;
-
Right_Rotate(x->parent);
-
x = root;
-
}
-
}
-
}
-
x->color = true;
-
}
-
struct RB_tree_node *Delet_Black_leaf(struct RB_tree_node *s){
-
if(s == s->parent->rchild){
-
if( s->color == false){
-
s->color = true;
-
s->parent->color = false;
-
Left_Rotate(s->parent);
-
s = s->lchild->rchild;
-
}
-
if( s->lchild==NULL && s->rchild== NULL ){
-
s->color = false;
-
return s->parent;
-
}else{
-
if(s->rchild == NULL){
-
s->lchild->color = true;
-
s->color = false;
-
Right_Rotate(s);
-
s = s->parent;
-
}
-
s->color = s->parent->color;
-
s->parent->color = true;
-
s->rchild->color = true;
-
Left_Rotate(s->parent);
-
return NULL;
-
}
-
}else{
-
if( s->color == false){
-
s->color = true;
-
s->parent->color = false;
-
Right_Rotate(s->parent);
-
s = s->rchild->lchild;
-
}
-
if( s->lchild==NULL && s->rchild== NULL ){
-
s->color = false;
-
return s->parent;
-
}else{
-
if(s->lchild == NULL){
-
s->rchild->color = true;
-
s->color = false;
-
Left_Rotate(s);
-
s = s->parent;
-
}
-
s->color = s->parent->color;
-
s->parent->color = true;
-
s->rchild->color = true;
-
Right_Rotate(s->parent);
-
return NULL;
-
}
-
}
-
}
-
void Delete(int val){
-
struct RB_tree_node *cur = Find(val);
-
if(!cur) return;
-
struct RB_tree_node *y = cur, *successor, *sibling;
-
bool original_color = y->color;
-
if( cur->lchild == NULL) {
-
successor = cur->rchild;
-
sibling = Get_Sibling(y);
-
Transplant(cur, cur->rchild);
-
}
-
else if( cur->rchild == NULL){
-
successor = cur->lchild;
-
sibling = Get_Sibling(y);
-
Transplant(cur, cur->lchild);
-
}
-
else{
-
y = cur->rchild;
-
while(y->lchild){
-
y = y->lchild;
-
}
-
original_color = y->color;
-
successor = y->rchild;
-
sibling = Get_Sibling(y);
-
cur->val = y->val;
-
Transplant(y, y->rchild);
-
}
-
if(original_color){
-
if(successor == NULL){
-
successor = Delet_Black_leaf(sibling);
-
}
-
if( successor)
-
Delete_fix(successor);
-
}
-
delete cur;
-
}
-
int main()
-
{
-
int arr[] = {10, 7, 8, 15,5, 6,11, 13, 12 };//9
-
for(int i = 0; i < 9; i++){
-
insert(arr[i]);
-
}
-
Delete(15);
-
Delete(12);
-
Delete(10);
-
Delete(6);
-
Delete(8);
-
return 0;
-
}
由于我没有采用算法导论当中的指定T.nil 来充当辅助节点,所以我在处理删除黑色叶子结点的时候,多谢了一个函数,其形式是照搬的Delete_fix函数~
阅读(2283) | 评论(0) | 转发(0) |