红黑树
-
红黑树的删除类似于排序二叉树,排序二叉树主要分为三种情况:删除没有左孩子且没有右孩子的结点即:度为0。删除只有左(右)孩子的结点。即:度为1。删除有左孩子且有右孩子的结点。即:度为2。
由于红黑树还有颜色的区分,所以在上述三种情况的基础上加上颜色,就是六种情况。以 {15, 7, 45, 3, 10, 25, 55, 1, 5, 75} 为例:
红黑树有六种情况:第一种:删除度为 0 的黑色结点。比如:10、25。第二种:删除度为 0 的红色结点。比如:1、5、75。第三种:删除度为 1 的黑色结点。比如:55。第四种:删除度为 1 的红色结点。这种情况不存在。第五种:删除度为 2 的黑色结点。比如:3、15。第六种:删除度为 2 的红色结点。比如:7、45。- 第一种情况删除度为 0 的黑色结点:比较复杂,后面专门讨论。
- 第二种情况时候删除度为 0 的红色结点:直接删除即可。
- 第三种情况时候删除度为 1 的黑色结点:必然是"黑-红"的结构,则,删除当前结点(A),让孩子结点(B)代替A,并将B改为黑色。
- 第四种情况时候删除度为 1 的红色结点:这种情况不存在。到情况五的时候删除度为 2 的黑色结点:比如:删除 15,用其前驱10(后继也可以)的值代替15,再删除10(跳到情况1)即可。
比如:删除 15,用其前驱10(后继也可以)的值代替15,再删除10(跳到情况3)即可。
比如:删除 15,用其前驱12(后继也可以)的值代替15,再删除12(跳到情况2)即可。
西南地区IT社群(QQ)
- 云南
- 【昆明网页设计交流吧】243627302
- 【昆明nodejs交流吧】 243626749
- 【VUE】838405306
- 【云南程序员总群】343606807
- 【昆明UI设计】104031254
- 【云南软件外包】15547313
- 贵州
- 【PHP/java源码/站长交流群】55692114
- 四川
- 【成都Java/JavaWeb交流】86669225
- 【vaScript+PHP+MySql】116270060
- 【UI设计/设计交流学习群】135794928
- 重庆
- 【诺基亚 JAVA游戏博物馆】 559479780
- 【PHP,Java,Python,C++接单】 442103442
- 西藏