算法导论 - 实验四 常见平衡树的实现与比较

情况5：当前节点颜色是黑色，兄弟节点是黑色，兄弟的左子是红色，右子是黑色。 解法：把兄弟结点染红，兄弟左子节点染黑，之后再在兄弟节点为支点解右旋， 之后重新进入算法。此是把当前的情况转化为情况6，而性质5得以保持。 5.变化前：

5.变化后：

情况6：当前节点颜色是黑色，它的兄弟节点是黑色，但是兄弟节点的右子是红色，兄弟节点左子的颜色任意。

解法：把兄弟节点染成当前节点父节点的颜色，把当前节点父节点染成黑色，兄弟节点右子染成黑色，

之后以当前节点的父节点为支点进行左旋，此时算法结束，红黑树所有性质调整正确。 6.变化前：

6.变化后：

c) 平衡二叉树插入、删除操作的具体实现

i.

插入操作各种可能的情况 1. LL的情况：

由于在A的左孩子B的左子树上插入结点F，使A的平衡因子由1增至2而失去平衡。故需进行一次顺时针旋转操作。 即将A的左孩子B向右上旋转代替A作为根结点，A向右下旋转成为B的右子树的根结点。而原来B的右子树则变成A的左子树。

2. LR情况：

由于在A的左孩子B的右子数上插入结点F，使A的平衡因子由1增至2而失去平衡。故需进行两次旋转操作（先逆时针，后顺时针）。即先将A结点的左孩子B的右子树的根结点D向左上旋转提升到B结点的位置，然后再把该D结点向右上旋转提升到A结点的位置。即先使之成为LL型，再按LL型处理。