插入

AVL 树的插入方式与二叉搜索树相同。新节点被添加为 AVL 树的叶节点。然而，这可能导致 AVL 树属性的违反，因此可能需要对树进行平衡。

可以通过执行旋转来平衡树。仅当插入新节点后任何节点的平衡因子被扰动时才需要旋转，否则则不需要旋转。

根据插入的类型，旋转可分为四类。

问：按给定顺序插入以下元素，构建一个 AVL 树。

63, 9, 19, 27, 18, 108, 99, 81

从给定元素构建 AVL 树的过程如图所示。

每一步，我们都必须计算每个节点的平衡因子，如果发现其大于 2 或小于 -2，则需要进行旋转来重新平衡树。旋转的类型将根据插入的元素相对于关键节点的位置来估计。

所有元素都按顺序插入，以保持二叉搜索树的顺序。