赞
踩
前面的提到了红黑树的结构定义还有旋转,其中包括左旋和右旋, 那么接下来就是插入并且做调整。
这里的处理逻辑就是不断遍历左右子树,然后找到最下面的nil节点为止,那么其上的父节点就是要考虑的插入位置,最后再考虑一下左右即可。
注意插入的节点默认都是红色,保证其他子树的黑色数量一致,也不违背根节点是黑色等条件,但是可能违背父子节点不能是红色,因此后续需要调整。
- void rbtree_insert(rbtree_t *T, rbtree_node_t *z) {
- //遍历的节点
- rbtree_node_t *x = T->root;
-
- //y用于保存要插入的位置的父节点
- rbtree_node_t *y = T->nil;
-
- while(x != T->nil) {
- y = x;
- if (x->key > z->key){
- x = x->left;
- }else if(x->key < z->key){
- x = x->right;
- }else{
- //Exist
- return;
- }
- }
-
- if (y== T->nil) {
- //空树
- T->root = z;
- } else {
- if (y->key > z->key) {
- y->left = z;
- } else {
- y->right = z;
- }
- }
-
- z->parent = y;
-
- //下面设置z属性
- z->left = T->nil;
- z->right = T->nil;
- //插入的颜色默认是红色,保证不会改变黑色节点的路径
- //但是可能不满足父子节点不能同时为红色的限制,因此后续需要考虑调整
- z->color = RED;
-
- rbtree_insert_fixup(T, z);
- }
对于节点的调整,因为插入节点是红色的,因此只有在其父节点也是红色的情况下才需要调整。同时其祖父节点(即父节点的父节点)一定是黑色的,但是祖父节点的另一个子节点,即叔父节点的颜色则是不确定的,因此可以从叔父节点的颜色入手考虑。
这里要调整就是祖父节点和其子节点颜色对换即可,方式如下所示:
那么这里的简易处理逻辑如下:
- // rbtree_node_t *z 是插入的节点
-
-
- //叔父节点
- rbtree_node_t *y = z->parent->parent->right;
-
- if (y->color == RED) {
- z->parent->color = BLACK;
- y->color = BLACK;
- z->parent->parent->color =RED;
-
- //回溯z,保证回溯到z都是红色的
- z = z->parent->parent;
- }
要注意这里最后 z = z->parent->parent 这段代码,这里是因为下面的子树解决了,但是上层可能又有冲突,例如祖父节点的父节点也是红色,因此这时候还要继续迭代考虑。
对于叔父节点是黑色的时候,这里还要分情况, 因为要分左右子树的情况,下面是左子树的情况:
这里迭代到z节点,然后和父节点都说红色并且在左子树。那么这里需要做两步:
下面是右子树的情况:
这里要做的事情有两件:
这时候得到的新的树,就是第一种情况,也就是父子节点都是红色的,并且在左子树。在下次递归的时候就可以进行处理了。
下面是调整函数的完整代码:
- void rbtree_insert_fixup(rbtree *T, rbtree_node_t *z)
- {
-
- // 父子节点都是红色的, 祖父节点必然是黑色的
- // 但是叔父节点(即祖父节点的另一个子节点)颜色未知
- if (z->color == RED)
- {
- while (z->parent->color == RED)
- {
- if (z->parent->parent->left == z->parent)
- {
- // 父节点在祖父节点的左子树下
-
- // 叔父节点
- rbtree_node_t *y = z->parent->parent->right;
-
- if (y->color == RED)
- {
- // 叔父节点也是红色的 --> 祖父节点和其子节点颜色对调
-
- z->parent->color = BLACK;
- y->color = BLACK;
- z->parent->parent->color = RED;
-
- // 回溯z,保证回溯到z都是红色的
- z = z->parent->parent;
- }
- else
- {
- // 叔父节点是黑色的 --> 区分z是在左还是右子树
-
- if (z == z->parent->left)
- {
- // z节点在左子树下
-
- // 1).对换父节点和祖父节点颜色
- z->parent->color = BLACK;
- z->parent->parent->color = RED;
-
- // 2). 以祖父节点进行右旋
- rbtree_right_roate(T, z->parent->parent);
- }
- else
- {
- // z节点在右子树下
-
- // 1). 把z改为其父节点
- z = z->parent;
- // 2). 进行左旋
- rbtree_left_roate(T, z);
- }
- }
- }
- else
- {
- // 叔父节点
- rbtree_node_t *y = z->parent->parent->left;
-
- if (y->color == RED)
- {
- // 叔父节点也是红色的 --> 祖父节点和其子节点颜色对调
-
- z->parent->color = BLACK;
- y->color = BLACK;
- z->parent->parent->color = RED;
-
- // 回溯z,保证回溯到z都是红色的
- z = z->parent->parent;
- }
- else
- {
- //和上面的情况对比,则是左右对调, 左右旋互换
- if (z == z->parent->right)
- {
-
- z->parent->color = BLACK;
- z->parent->parent->color = RED;
-
-
- rbtree_left_roate(T, z->parent->parent);
- }
- else
- {
- z = z->parent;
- rbtree_right_roate(T, z);
- }
- }
- }
- }
- }
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。