AVL树中的插入的执行方式与在二叉搜索树中执行的方式相同。 新节点作为叶节点添加到AVL树中。 但是，它可能会导致违反AVL树属性，因此树可能需要平衡。
可以通过应用旋转来平衡树。 仅当插入新节点时任何节点的平衡因子受到干扰时才需要旋转，否则不需要旋转。
根据插入的类型，旋转分为四类。
| 编号 | 旋转 | 描述 |
|---|---|---|
| 1 | LL旋转 | 新节点被插入到关键节点的左子树的左子树中。 |
| 2 | RR旋转 | 新节点被插入到关键节点的右子树的右子树中。 |
| 3 | LR旋转 | 新节点被插入到关键节点的左子树的右子树中。 |
| 4 | RL旋转 | 新节点被插入到关键节点的右子树的左子树中。 |
示例： 通过以给定顺序插入以下元素来构造AVL树。
63, 9, 19, 27, 18, 108, 99, 81
从给定元素集构造AVL树的过程如下图所示。
在每一步，必须计算每个节点的平衡因子，如果发现它大于2或小于-2，那么需要一个旋转来重新平衡树。 旋转类型将通过插入元素相对于关键节点的位置来估计。
插入所有元素以维持二叉搜索树的顺序。
上一篇：
平衡搜索树(AVL树)
下一篇：
B树