苏泽
“弃工从研”的路上很孤独，于是我记下了些许笔记相伴，渴望可以或许资助到大家
目次
许多人被平衡二叉树的插入后的调解过程弄的晕头转向的 私以为 不妥！
整理了一套 小学生都能明白的思路表明这一过程
平衡二叉树的定义
插入
欲平衡 先找不平衡
LL
这个过程我记作“父夺子权，反被骑头”
父夺子权
随后 儿子喜当爹
表明一下这么操纵的本质是什么
具体拿A夺权 让CR成为孩子 这个操纵 来进行表明
天道损有余而补不足
许多人被平衡二叉树的插入后的调解过程弄的晕头转向的 私以为 不妥！
整理了一套 小学生都能明白的思路表明这一过程
前半部分的定义给没看过的同学们增补远景知识 可用目次跳到精彩部分
平衡二叉树是一种特殊的二叉树，它包管了树中任意两个叶子节点到根节点的距离差不超过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这个高个儿的 往上挪一挪 左右不就平衡了
天道损有余而补不足
别的，使用了工作之余的一点点时间，整理了一套考研408的知识图谱，
我根据这一套知识图谱打造了这样一个408知识图谱问答体系
内里的每一个答复都是根据考研408的考点回复的
现在暂时只接入了微信，如果大家对这个问答体系感爱好的话可以在我的主页里找到我的微信号
找我拉进测试群免费体验哦
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。 | 
