[text] SS

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                          //只要有一棵空子树,y则指向z，不找后继节点
  7.     　　Else y<-Tree-successor   //如果有两棵非空子树，则y指向后继节点
  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]                              //把y的父节点作为子树x的父节点，准备删除y。
  16.     If p[y]=nil[T]                         //如果y的父亲是nil，说明y是根位置。
  17.     　　Then root[T]<-x       //x放在根位置
  18.     　　Else if y = left[p[y]]        //用x取代y的位置
  19.     　　    Then left[p[y]]<-x
  20.     　　Else right[p[y]]<-x
  21.     //这一段操作主要就是用x取代y。Y的两种情况的操作都是一样的，都是把p[y]给p[x]，把x给left[p[y]]或者right[p[y]].
  22.     If y!=z       
  23.     //如果删除的y和z指针不一样，说明y是z的后继。这在第三行代码tree-successor中赋值
  24.     　　Then key[z]<-key[y]
  25.     　　   Copy_Ydata_to_z    //把后继的内容赋给z。
  26.     If color[y]=BLACK               //删除节点是黑色节点
  27.     　　Then RB-DELET-FIXUP(T,x)  //到这里，y已经被x取代，所以基于x去调整
  28.     Return Y
  29.     
  30.     
  31. RB-DELETE-FIX-UP(T,x)  ——  x是被删除节点的子树,且已经更新为后继或子树的位置
  32.     While x!=root[T] and color[x]=BLACK    //如果x是红色节点，则退出while，然后把x染黑，就可以增加一个黑色高度
  33.     　　Do if x=left[p[x]]     
  34.     　　{
  35.     　　    Then w<-right[p[x]]    
  36.     　　    //如果新x是左子树（则原来的y所在位置），则设置w为兄弟节点为右子树
  37.     　　    If color[w]=RED  //如果兄弟节点是红色
  38.     　　    //case1
  39.     　　        Then
  40.     　　        {color[w]<-BLACK  //兄弟节点设为黑色(x也是黑色的)
  41.     　　         Color[p[x]]<-RED                        //父节点设为红色
  42.     　　         LEFT-ROTATE(T,p[x])
  43.     　　         W<-right[p[x]]          //旋转后，兄弟已经变为旧兄弟的孩子，通过parent获得新兄弟
  44.     　        　}
  45.     　　
  46.     　   　If color[left[w]]=BLACK and color[right[w]]=BLACK 
  47.     　     　  //case2 
  48.     　    　   Then color[w]<-RED                        
  49.     　　        X<-p[x]
  50.     　   　//case3
  51.     　　   Else if color[right[w]]=BLACK            
  52.     　       　//如果是右黑侄，左红侄，则设置左红侄为黑节点，为了转向case4做准备。
  53.     　   　        Then color[left[w]]<-BLACK
  54.     　  　         color[w]<-RED     
  55.     　      　     RIGHT-ROTATE(T,w)
  56.     　　           w<-right[p[x]]
  57.     　　       //case 4 红色右侄子
  58.             else
  59.      　　          color[w]<-color[p[x]]     //父节点的颜色给兄弟
  60.     　　           color[p[x]]<-BLACK    //父节点设为黑色
  61.     　　           color[right[w]]<-BLACK  //兄弟的右子树设为黑色
  62.     　　           LEFT_ROTATE(T,p[x])
  63.     　　           x<-root[T]                          //x作为root。执行完case4后，整颗树已经平衡，设置x为root[T]，则下一次while循环会跳出来。可见其作用是表示while结束。
  64.     　　}
  65.     　　Else(和上面逻辑对称)
  66.     Color[x]<-BLACK

Editor

You can edit this paste and save as new:


File Description
  • SS
  • Paste Code
  • 22 Jun-2021
  • 3.47 Kb
You can Share it: