红黑树看着有点费劲,分两次写,这次先写旋转和插入,下一篇写删除~~~
其实最早的时候,之所以买侯捷的这本《stl源码剖析》主要是因为想搞懂这篇文章的主题——rb-tree,因为当时自己作死,买的《算法导论》,但是这一章翻来覆去的,看不明白,哎,还是太菜鸡了,然后就一直拖到现在,最近也是一直在看这一块,总算水磨工夫起了点作用(也可以说是他山之石,可以攻玉哈~),两本书联合着看,外加一点网络资料,看懂了一丢丢,在这里跟大家分享一下喽~
首先rb-tree严格意义上讲并不是一颗非常严格的“平衡”二叉查找树,没有avl-tree严格,但是在其限制条件下,其关于集合的操作,最坏的时间复杂度为O(lgN),所以rb-tree是好多stl的关联式容器均选择。
先来说一下rb-tree的相关性质:
1. 每一个节点多出一个关于颜色的性质:非黑即红
2. 根节点是黑色的
3. 每一个叶子节点(NULL)视为黑色
4. 如果一个节点为红色,那么它的两个孩子的颜色必须都为黑色
5. 对于任意节点来说,从其开始,至其任意子孙当中的叶子结点的每一条路径当中,所包含的黑色节点数目相同。
然后还要先来示例说明一下对应的rb-tree节点的代码,注意哈,这里是有父节点指针的~
-
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){}
-
};
然后说一下左旋转和右旋转,跟之前那一篇avl的差不多,就是多了父指针,
情形如下图:
代码如下:
-
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;
-
}
接下来,说一下红黑树的插入,第一点要说明的是,插入节点的颜色默认都是红色的;这样以来呢,它就不会影响到性质3,5,如果是根节点,直接变黑就行了;但是,如果影响了性质4,就需要用到之前的旋转以及颜色调换了~
违背性质4的插入的话,用《stl源码剖析》的话说,只有两种情况:内插和外插,如下图所示,其中插入的节点可以自带子树,也可以是新插入节点,但是都保证知味饭性质4,这样做是为了将来在递归回溯时方便理解:
(为了方便,这里没有画出其他子树,并假设在插入之前该树满足红黑树性质)
我们通过观察可以发现,内插的话,通过一次之前的左旋或者右旋操作,会变成了外插,这样的话,以后的文章就可以归结为外插入一种情况了。
现在来分析一下,外插入红色节点的父节点为红色的情况,这种情况就要看其叔父节点的颜色了,因为两个红色节点肯定不能相邻,肯定会进行改变颜色或者进行旋转,影响的只有其祖父节点下的性质4和5,这样的话,看叔父节点就好了:
1) 叔父节点为黑,进行如下变换:
简单解释一下,首先,调整后的树满足性质4;之后查看性质5,原来对于G,a,b,c,d,四颗子树的黑高是相同的,调整完之后,依旧是相同的,跟p的兄弟节点的黑高只差p这一个黑色节点~嗯,很满足条件5了,其他的条件就更加满足了。
1) 叔父节点为红,进行如下变换:
这样变换的话,节点G(包含)的性质5得以保存,但是,其变为红色,若其父节点为红色,可能违反性质4,这时,我们就要把当前节设置为祖父节点,进行新一轮的迭代。最终,不要忘了设置根节点的颜色为黑色哦,因为如果一直回溯的话,是有可能将根节点回溯为红色,而违反性质2的哈~
代码如下:
-
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);
-
}
之后就可以写个数组,插入进去试一试了哈~
不足之处,还望大家不吝赐教~~~
阅读(2277) | 评论(0) | 转发(0) |