1. 最小失衡子树
插入结点为61后,结点31和结点20失衡。

最小子失衡子树
离插入位置最近的子树根(根)对应的子树为最小失衡子树。
为什么?
如果将最小的调整,深度减少一,那么这个局部减少最终会导致全局减少一。
调整最小子树达到整颗树平衡的过程,实际上就是局部平衡到全局平衡的过程。
2. 调整方法:中值法
关键技巧:
- 中值为根,然后将子树拆分挂到对应位置,
- 最后再根据二叉排序树的左小右大的规则拼凑起来。
最关键核心的操作就是让失衡根结点转换成中间值的孩子。拆的时候是根据做小右大的规则进行拆,挂的时候也是根左小右大的规则进行挂。
LR和RL进行转换,将其利用LL和RR将其转换成LL或者RR。
2.1 LL
插入位置是失衡根结点的左子树的左子树。
调整方法:最小子树A的左孩子右上旋转。


2.2 LR
插入位置是失衡结点的左子树的右子树。(关键是将R变成L,LL)
调整方法:最小子树A的左孩子的右孩子,先左上旋转再右上旋转。


2.3 RR
插入位置是失衡结点的右子树的右子树。
调整方法:最小子树A的右孩子左上旋转。


2.4 RL
插入位置是失衡结点的右子树的左子树。(关键是将L变成R,RR)
调整方法:最小子树A的右孩子的左孩子,先右上旋转再左上旋转。


3.Sample
Sample1:
最小失衡子树12的左子树的右子树中插入结点9导致失衡。
LR → LL → 平衡
结点12的做孩子的右孩子,先左上旋转至LL,再右上旋转即可

Sample2
最小失衡子树27的左子树的左子树插入结点25导致失衡。
LL → 平衡
27结点的左孩子26结点右上旋转即可。

Sample3
失衡结点20的右子树的左孩子的左孩子插入结点25导致失衡。
RL → RR → 平衡
注意中间值的选取结点26;
20结点的右子树的左孩子的左孩子26结点,先右上旋转值RR,再左上旋转至平衡

Sample4
失衡结点20的右孩子的右孩子的右孩子插入结点61导致失衡
RR → 平衡
20结点的右孩子31结点右上旋转即可。
