AVL树

AVL树是根据它的发明者G. M. Adelson-Velskii和E. M. Landis命名的。它是一种特殊的二叉搜索树。

AVL树要求: 任一节点的左子树深度和右子树深度相差不超过1，AVL树的搜索算法复杂度是log(n)的量级。

AVL树的不平衡

有4种情况会导致AVL树失去平衡

• LL：插入一个新节点到根节点的左子树（Left）的左子树（Left），导致根节点的平衡因子由1变为2
• RR：插入一个新节点到根节点的右子树（Right）的右子树（Right），导致根节点的平衡因子由-1变为-2
• LR：插入一个新节点到根节点的左子树（Left）的右子树（Right），导致根节点的平衡因子由1变为2
• RL：插入一个新节点到根节点的右子树（Right）的左子树（Left），导致根节点的平衡因子由-1变为-2

旋转

针对AVL树出现的不平衡，AVL树通过旋转的策略实现自平衡。

• 左旋转：将根节点旋转到（根节点的）右孩子的左孩子位置
• 右旋转：将根节点旋转到（根节点的）左孩子的右孩子位置

旋转的目的就是减少高度，通过降低整棵树的高度来平衡。哪边的树高，就把那边的树向上旋转。

进一步可细分为：

• 左旋转
• 右旋转
• 左右旋转（先左后右）
• 右左旋转（先右后左）