很多人被平衡二叉树的插入后的调整过程弄的晕头转向的 私以为 不妥！
整理了一套 小学生都能理解的思路解释这一过程
前半部分的定义给没看过的同学们补充前景知识 可用目录跳到精彩部分
平衡二叉树是一种特殊的二叉树，它保证了树中任意两个叶子节点到根节点的距离差不超过1，从而确保了树的平衡性。这种结构可以使得树的查找、插入和删除操作的时间复杂度保持在O(log n)，其中n是树中节点的数量。
平衡二叉树的定义
平衡二叉树的定义通常基于树的高度差。一个平衡二叉树满足以下条件：
- 每个节点的左子树和右子树的高度差（深度差）不超过1。
- 每个子树也是一棵平衡二叉树。
结点平衡因子等于左子树高-右子树高
相信概念理解起来都不难 平衡二叉树难就难在他令人“闻风丧胆”的插入操作 但真的如此吗？
插入
插入新的节点意味着可能会打破原有的平衡 所以 关键的矛盾就在寻找平衡身上
欲平衡 先找不平衡
我们都知道 是因为插入 导致的不平衡 所以我们要在最小的范围内找到不平衡的子树
传统的讲义都是分这四种情况讨论 但我最后还会再补充一个“四合一”的方法 来简化记忆
LL
这还是一颗平衡树 因为平衡因子为1 这时候在左下角插入
这个时候 a结点的左子树高度是H 2 右子树高度是H所以 平衡因子是2 此时不平衡！
由B、A、AR这三个结点组成的子树就是最小不平衡子树！
所以我们要调整这个最小不平衡子树
肉眼可见 左高右低 所以进行右旋 ---思想：想象这是一个移长补短的过程
这个过程我记作“父夺子权，反被骑头”
首先 “父夺子权”
父亲结点想要夺取子结点手里的“权”（这里的“权”就是该子节点的子节点）
然后 “父亲被反骑”
被夺权的逆子很生气 要骑在父亲的头上 于是 原先的 父节点变成了自己子节点的孩子
如图所示 原先B是A的孩子 现在B却成了A的父亲 其中的父子关系就如同男生宿舍里一般诡异多变
经过这样的一轮变换 树就平衡了
同理
RR
在右子树的右子树插入导致不平衡
找到最小不平衡子树 AL 、A、B 开始操作
父夺子权
随后 儿子喜当爹
操作完毕 恢复平衡
LR
在左子树的右子树插入
当然了 这里插入的子树 可以在CL或者CR插入 都是一样的 先假设插入在CR
在这种情况下 我们就可以把原本在B、A、AR之间的矛盾 转移到 BL、B、C之间 因为 BL、B、C才是最小不平衡子树
操作
我们发现这里的情况跟上一种RR类似
把刚才RR那种情况的操作重复一遍 让C这个逆子 骑在B头上
这里 又跟LL那种情况一样 重复操作 轮到A夺C的权
然后C又骑在了A的头上
到了RL 其实跟LR 是一个思想 无非就是 把LL或RR的操作 重复了两遍 不多赘述 感兴趣可以手写试着看看能不能成功演练出来
所以总结一下这里操作的口诀：“父夺子权，反被骑。方向不同（特指LR和RL），弄两次 ”
解释一下这么操作的本质是什么
平衡二叉树的本质 其实就是不等式
例如这里就是 BL<B<CL<C<CR<A<AR
具体拿A夺权 让CR成为孩子 这个操作 来进行解释
C<CR<A
二叉树的性质 子树里边 左小右大呗 所以A能够夺权 是基于C<CR<A这个不等式
C能当A的爹 同理 那保证了不等式守恒 来解释一下为什么这么做呢？
首先 A的右腿子（AR） 营养不良根本没 左子树C高啊 在不能无中生有的情况下 只能把AR“往下拉” 那咋子往下拉？ 拖家带口呗 把AR的父节点A也往下拉 那C这个高个儿的 往上挪一挪 左右不就平衡了
