[text] ASSS

Viewer

  1. 4.红黑树的删除
  2.  
  3.  
  4. RB-DELET(T,y)
  5.     If left[z]=nil[T] or right[z]=nil[T]
  6.       Then y<-z                         
  7.       Else y<-Tree-successor   
  8.     If left[y]!=nil[T]                      
  9.       Then x<-left[y]
  10.       Else x<-right[y]   
  11.     //找到删除节点y的子树x,进行下一步操作。先找左子树,如果没有再找右子树.
  12.     //注意,这里的y有两种可能:
  13.     //有一棵空子树,则是删除节点z
  14.     //有两棵非空子树,则是删除节点z的后继节点。
  15.     P[x]<-p[y]                     
  16.     If p[y]=nil[T]                        
  17.       Then root[T]<-x       
  18.       Else if y = left[p[y]]       
  19.           Then left[p[y]]<-x
  20.       Else right[p[y]]<-x
  21.     If y!=z       
  22.     //如果删除的y和z指针不一样,说明y是z的后继。这在第三行代码tree-successor中赋值
  23.       Then key[z]<-key[y]
  24.          Copy_Ydata_to_z  
  25.     If color[y]=BLACK               
  26.       Then RB-DELET-FIXUP(T,x)  
  27.       //到这里,y已经被x取代,所以基于x去调整
  28.     Return Y
  29.     
  30.     
  31. RB-DELETE-FIX-UP(T,x)
  32. //x是被删除节点的子树,且已经更新为后继或子树的位置
  33.     While x!=root[T] and color[x]=BLACK   
  34.       Do if x=left[p[x]]     
  35.       {
  36.           Then w<-right[p[x]]    
  37.           //如果新x是左子树(则原来的y所在位置),则设置w为兄弟节点为右子树
  38.           If color[w]=RED  //如果兄弟节点是红色
  39.           //case1
  40.               Then
  41.               {color[w]<-BLAC色的)
  42.                Color[p[x]]<-RED                        //父节点设为红色
  43.                LEFT-ROTATE(T,p[x])
  44.                W<-right[p[x]
  45.               }
  46.       
  47.          If color[left[w]]=BLACK and color[right[w]]=BLACK 
  48.              //case2 
  49.              Then color[w]<-RED                        
  50.               X<-p[x]
  51.          //case3
  52.          Else if color[right[w]]=BLACK            
  53.              //如果是右黑侄,左红侄,则设置左红侄为黑节点,为了转向case4做准备。
  54.                  Then color[left[w]]<-BLACK
  55.                  color[w]<-RED     
  56.                  RIGHT-ROTATE(T,w)
  57.                  w<-right[p[x]]
  58.              //case 4 红色右侄子
  59.             else
  60.                  color[w]<-color[p[x]]   
  61.                  color[p[x]]<-BLACK
  62.                  color[right[w]]<-BLACK
  63.                  LEFT_ROTATE(T,p[x])
  64.                  x<-root[T]                 
  65.                  //x作为root。执行完case4后,整颗树已经平衡,设置x为root[T],则下一次while循环会跳出来。可见其作用是表示while结束。
  66.       }
  67.       Else(和上面逻辑对称)
  68.     Color[x]<-BLACK

Editor

You can edit this paste and save as new: