下面对红黑树删除某节点后，旋转三次的例子做出详解：
先利用代码建立树如下：
![红黑树删除某节点后旋转3次举例及详解]( "红黑树删除某节点后旋转3次举例及详解")
修改颜色分布为下列树：
![红黑树删除某节点后旋转3次举例及详解]( "红黑树删除某节点后旋转3次举例及详解")
先利用代码建立树如下：
修改颜色分布为下列树：
新浪博客
修改颜色分布后，利用
tree->insert(1);
tree->remove(1);
来判断是否是红黑树
如果不是红黑树，在插入删除的过程中，会进入各个case，并有相关语句会输出到cmd上。显然，上述语句执行后，没有任何信息，说明修改颜色分布后依然为一棵标准的红黑树树。
然后删除黑节点10；
由于删除的节点是叶子节点（黑），所以左右子节点都是NULL；
下面开始对删除过程中四种修正case进行分析
首先进入case 2
对被删除节点10的兄弟节点27染色，改为红
执行后效果如下：
由于node不为红色节点，所以继续进行下轮的while循环，此时进入case 1
染色后（橙黄色代表将要进行旋转的部分，下同）
左旋后
之后进入case 3
染色后
准备右旋转，旋转后并且调整other后如下：
最后进入case 4
染色前
让other的颜色等于parent的颜色，parent变黑，other->right变黑，处理后如下：
开始左旋，左旋后结果如下：
最终删除节点10，结果如下：
测试代码如下：
| 1 2 3 4 5 6 7 8 9 |
#include'RBTree.h' #include #include #include using namespace std; int main() { //int a[] = {40,20,60,50,80,70,90 }; int a[] = { 35,20,10,27,400,105,600,70,150,500,700,50,85 }; int check_insert = 0; int check_remove = 0; int i; int ilen = (sizeof(a)) / (sizeof(a[0])); RBTree* tree = new RBTree(); cout << '== 原始数据: '; for (i = 0; i cout << a[i] << ' '; cout << endl; for (i = 0; i { tree->insert(a[i]); // 设置check_insert=1,测试'添加函数' if (check_insert) { cout << '== 添加节点: ' << a[i] << endl; cout << '== 树的详细信息: ' << endl; tree->print(); |