Red-black tree,该如何处理

2013-01-07

Red-black tree大家好，我有个关于红黑树的问题想请教下。在红黑树的插入算法（RB-INSERT(T,z)）的子程序RB-IN

Red-black tree
大家好，我有个关于红黑树的问题想请教下。
在红黑树的插入算法（RB-INSERT(T,z)）的子程序RB-INSERT-FIXUP(T,z)的伪代码中，为什么没有考虑
whilecolor[p[z]]<-RED//
     do if p[z]=left[p[p[z]]]
           then y<-right[p[p[z]]]
                if color[y]=RED
                  then color[p[z]]<-BLACK
                       color[y]<-BLACK
                       color[p[p[z]]]<-RED
                       z<-p[p[z]]
                else if z=right[p[p[z]]]
                        then z<-p[z]
                          LEFT-ROTATION(T,z)
                       color[p[z]]<-BLACK
                       color[p[p[z]]]<-RED
                       RIGHT-ROTATION(T,p[p[z]])
          else (same as then clause
                          with "right" and "left" exchanged)
color[root[T]]<-BLACK

在最初的时候，为什么没考虑color[p[z]]<-BLACK？在这种情况下，若color[left[p[z]]]=BLACK, color[z]=red,若不进行颜色调整，就违反了红黑树的性质5：For each node, all paths from the node to descendant leaves contain the same number of black nodes.

如果一个node颜色是RED,那是不是一定有两个真实的子节点，或者没有子节点？

[解决办法]
Red-black tree,该如何处理
到这里发帖子比较好http://bbs.csdn.net/forums/ST_Arithmetic
[解决办法]
>为什么没考虑color[p[z]]<-BLACK？
因为这种情况下rbtree的性质没有被破坏，可以直接返回。你加了一个红节点进去，从根到叶的黑节点数目没有发生变化，你说的违反其实根本没违反。

>如果一个node颜色是RED,那是不是一定有两个真实的子节点，或者没有子节点？
是。如果只有一边有实际节点的话，那个节点必须是黑色，然后就违反了黑节点数目的性质。
[解决办法]
在最初的时候，为什么没考虑color[p[z]]<-BLACK？在这种情况下，若color[left[p[z]]]=BLACK, color[z]=red,若不进行颜色调整，就违反了红黑树的性质

插入节点z之前，默认红黑树已经是满足条件的了，插入一个节点z，并将其设置为红色，这样不影响红黑树的黑高度，如果p[z]== back，那么就不需要调整了。。。即使color[left[p[z]]] = black，color[z] = red，也不会破坏红黑树性质。。。因为在插入之前红黑树已经是满足条件的了
------解决方案--------------------

http://blog.csdn.net/v_JULY_v/category/774945.aspx

热点排行

C++

Red-black tree,该如何处理