Red-Balck Tree

By | 2013 年 1 月 5 日

红黑树
是一颗比较平衡的二叉搜索树,算法复杂,但是保证了各种操作最差情况下是O(logn)

定义
除了普通二叉搜索树的要求以外,还有几个其它的要求:
1·根节点是黑色的
2·不能有两个相邻的红色节点,(父子不同红色)
3·叶节点是黑色的(这里定义的叶节点是指空节点,不包含数字)
4·根节点到所有叶节点的各条路径上的黑色节点数目是相等的
5·所有节点,非红即黑

性质
最长和最短的根节点到叶节点的路径长度只差不超过2倍。
所有操作都可以在O(logn)时间内完成。

查找操作
查找操作和普通二叉搜索树是一样的

插入操作
按照普通二叉搜索树的方法,将要插入的节点插入到二叉树里面,所有的节点在插入的时候都涂成红色,然后分情况进行处理
1·如果插入的节点没有父节点(即刚插入的节点是根节点),直接涂成黑色就搞定。

void insert_case1(node n) {
     if (n->parent == NULL)
         n->color = BLACK;
     else
         insert_case2(n);
 }

2·设插入的节点的父节点为F,如果F是黑色的,就什么也不用做。

void insert_case2(node n) {
     if (n->parent->color == BLACK)
         return; /* 树仍旧有效 */
     else
         insert_case3(n);
 }

3·否则的话,F是红色,那么F不是根节点,所以F必然有父节点,设父节点的父节点是G(必然是黑色)。设父节点的兄弟节点是U。如果U存在并且F和U都是红色的,那么就将FU涂成黑色,G涂成红色。然后把G当做新加入的节点从第1步开始依次查看。

 void insert_case3(node n) {
     if (uncle(n) != NULL && uncle(n)->color == RED) {
         n->parent->color = BLACK;
         uncle(n)->color = BLACK;
         grandparent(n)->color = RED;
         insert_case1(grandparent(n));
     }
     else
         insert_case4(n);
 }

(45两步都假设F是G的左子结点,如果F是G的右子结点,那么下面的操作都反向)
4·否则,要么U不存在,要么U是黑色。如果新节点N是F的左子节点,转5;否则对F做一次左旋转,并且交换新节点N和F的角色,进行第5步处理
(这一步有点诡异,怎么会出现黑色的U呢?因为在加入N之前,G(黑)-F(红)-Leaf(黑) = 2黑,G(黑)-U(黑)-…-Leaf(黑) >=3 黑,不可能啊。后来想明白了,这种情况只可能是由于第3步中交换颜色之后导致的情况。)

void insert_case4(node n) {
     if (n == n->parent->right && n->parent == grandparent(n)->left) {
         rotate_left(n->parent);
         n = n->left;
     } else if (n == n->parent->left && n->parent == grandparent(n)->right) {
         rotate_right(n->parent);
         n = n->right;
     }
     insert_case5(n);
 }

5·这种情况下,N是F的左子结点,且NF都是红色,G是黑色,U是黑色。此时对G做一次右旋转,且交换G和U的颜色,搞定。

 void insert_case5(node n) {
     n->parent->color = BLACK;
     grandparent(n)->color = RED;
     if (n == n->parent->left && n->parent == grandparent(n)->left) {
         rotate_right(grandparent(n));
     } else {
         /* Here, n == n->parent->right && n->parent == grandparent(n)->right */
         rotate_left(grandparent(n));
     }
 }

删除操作
(未完待续…)



Reference
http://blog.csdn.net/longerzone/article/details/7817533
http://zh.wikipedia.org/wiki/红黑树

发表评论

电子邮件地址不会被公开。 必填项已用*标注