- 4.红黑树的删除
- RB-DELET(T,y)
- If left[z]=nil[T] or right[z]=nil[T]
- Then y<-z
- Else y<-Tree-successor
- If left[y]!=nil[T]
- Then x<-left[y]
- Else x<-right[y]
- //找到删除节点y的子树x,进行下一步操作。先找左子树,如果没有再找右子树.
- //注意,这里的y有两种可能:
- //有一棵空子树,则是删除节点z
- //有两棵非空子树,则是删除节点z的后继节点。
- P[x]<-p[y]
- If p[y]=nil[T]
- Then root[T]<-x
- Else if y = left[p[y]]
- Then left[p[y]]<-x
- Else right[p[y]]<-x
- If y!=z
- //如果删除的y和z指针不一样,说明y是z的后继。这在第三行代码tree-successor中赋值
- Then key[z]<-key[y]
- Copy_Ydata_to_z
- If color[y]=BLACK
- Then RB-DELET-FIXUP(T,x)
- //到这里,y已经被x取代,所以基于x去调整
- Return Y
- RB-DELETE-FIX-UP(T,x)
- //x是被删除节点的子树,且已经更新为后继或子树的位置
- While x!=root[T] and color[x]=BLACK
- Do if x=left[p[x]]
- {
- Then w<-right[p[x]]
- //如果新x是左子树(则原来的y所在位置),则设置w为兄弟节点为右子树
- If color[w]=RED //如果兄弟节点是红色
- //case1
- Then
- {color[w]<-BLAC色的)
- Color[p[x]]<-RED //父节点设为红色
- LEFT-ROTATE(T,p[x])
- W<-right[p[x]
- }
- If color[left[w]]=BLACK and color[right[w]]=BLACK
- //case2
- Then color[w]<-RED
- X<-p[x]
- //case3
- Else if color[right[w]]=BLACK
- //如果是右黑侄,左红侄,则设置左红侄为黑节点,为了转向case4做准备。
- Then color[left[w]]<-BLACK
- color[w]<-RED
- RIGHT-ROTATE(T,w)
- w<-right[p[x]]
- //case 4 红色右侄子
- else
- color[w]<-color[p[x]]
- color[p[x]]<-BLACK
- color[right[w]]<-BLACK
- LEFT_ROTATE(T,p[x])
- x<-root[T]
- //x作为root。执行完case4后,整颗树已经平衡,设置x为root[T],则下一次while循环会跳出来。可见其作用是表示while结束。
- }
- Else(和上面逻辑对称)
- Color[x]<-BLACK
[text] ASSS
Viewer
Editor
You can edit this paste and save as new:
File Description
- ASSS
- Paste Code
- 22 Jun-2021
- 2.69 Kb
You can Share it: