1回答

liuyubobobo

2023-05-26

已采纳

这里的关键是，形成 LL 不平衡的节点是谁？

在右边的示例中，5 不是不平衡的节点。因为 5 的左子树高度为 2，右子树高度为 1，左右子树高度差为 1，满足平衡的条件。

但是，在往上看，8 不平衡了。因为 8 的左子树高度为 3，右子树高度为 1，左右子树高度差为 2，不满足平衡的条件。

==========

进一步分析，8 是哪种不平衡？

8的这种不平衡叫 LL。（后续你会看到 LR, RL 和 RR 一共 4 种不平衡的可能性。）

因为，首先，8 的左子树高于右子树，这是 LL 的第一个 L 的意思；

再看 8 的左子树，满足左子树高于右子树，这是 LL 的第二个 L 的意思；

那么造成 8 的这种 LL 不平衡的原因是什么？是因为我们在 4 的左侧插入了 2。此时，4 没有不平衡；5 也没有不平衡，但 8 不平衡了。

在这里说“左侧的左侧”确实不够严谨。（或者你理解成，左侧并不一定直接指左孩子。左孩子的左孩子也叫左侧。）但不管怎么样，核心在于：

- 要找到到底谁不平衡？（因为谁不平衡，才要调整谁？右侧示例中，5 没有不平衡，8 不平衡，所以我们的关注点是 8）

- 到底是怎么不平衡？（LL， LR，RL， RR）（因为知道怎么不平衡，才能根据不平衡的种类，做相应的调整。）

继续加油！：）

1