LL 旋转

下图所示的树是 AVL 树，但是，我们需要在 A 的左子树的左侧插入一个元素。由于关键节点 A 的存在，该树可能会失去平衡。

平衡因子不在 -1 和 1 之间的节点称为关键节点。

为了重新平衡树，将执行 LL 旋转，如下图所示。

节点 B 成为根节点，A 和 T3 分别作为其左子节点和右子节点。T1 和 T2 作为 A 的左子树和右子树。

示例

将值为 12 的节点插入下图所示的树中。

解决方案

12 将被插入到 25 的左侧，因此，这会破坏 AVL 树的 AVL 性。需要通过 LL 旋转来重新平衡树。

此时，关键节点 100 将向右移动，其左子树的根节点（B）将成为树的新根节点。

B 的右子树，即 T2（根节点为 75），将被放置在节点 A（值为 100）的左侧。

按照此过程，树将重新平衡，因此，插入 12 后生成的树将是 AVL 树。