平衡二叉树的调整

要保证始终是平衡二叉树，就必然要在 插入 与删除操作后对树进行调整，让其的|BF(T) |≤ 1
所以平衡二叉树的重要操作是调整树

• RR旋转（右单旋）

• LL旋转（左单旋）

• LR旋转（左-右双旋）

• RL旋转 （右-左双旋）

以月份按月份缩写的字母顺序为比较标准，构建平衡二叉树的调整

1、RR旋转（右单旋）

---

依次 输入 Mar , May , Nov (3月，5月，11月）
当在插入 11月时，树的根节点的平衡因子为 -2 ，不满足 构成 平衡二叉树条件|BF(T)| <=1,所以需要进行调整

针对上述插入引起的不平衡采取RR旋转（右单旋）

RR旋转（右单旋）：不平衡的“发现者”是Mar，“麻烦结点”Nov在发现者右子树的右边， 因而叫 RR 插入，需要RR 旋转（右单旋)

2、LL旋转（左单旋）

---

再向调整后的月份树插入 Aug , Apr (8月，4月)
两个月份都以 A 字母 开头，则 比较 第二位 的字母 在字母表中的顺序，从而得出大小关系，所以 Apr < Aug；Aug 又小于 Mar ,所以 插入结果如下,同时需要对树进行调整

针对上述插入引起的不平衡采取LL旋转（左单旋）

LL旋转（左单旋）:“发现者”是Mar，“麻烦结点”Apr在发现者左子树的左边， 因而叫LL 插入，需要LL 旋转（左单旋）

3、LR旋转（左-右双旋）

再次加入 Jan (1月)
插入后，如下图所示，导致 May 的BF = 2 ，需要对树进行调整

针对上述插入引起的不平衡采取LR旋转（左-右双旋）

LR旋转（左-右双旋）: “发现者”是May，“麻烦结点”Jan在在发现者左子树的右边， 因而叫 LR 插入，需要LR 旋转

4、RL旋转 （右-左双旋）

再次顺序插入 Dec , July , Feb (12月，7月，2月)
导致 Aug 节点的BF = -2 ，需要对树进行调整

RL旋转（右-左双旋）: “发现者”是Aug，“麻烦结点”Dec在发现者右子树的左边， 因而叫 RL 插入，需要RL 旋转

重新计算 一些平衡因子

最后插入 June , Oct , Sept (6月,10月,9月)

注意：有时候插入元素即便 不需要调整结构，也可能需要重新计算 一些平衡因子。

C语言代码实现：

平衡二叉树数据结构:

插入调整:

辅助函数：