一、定义

• AVL tree是一个“加上了额外平衡条件”的二叉搜索树。其平衡条件的建立是为了确保整棵树的深度为
• AVL tree要求：任何节点的左右子树高度相差最多为1
• 例如：下面左图是一个AVL tree，但是插入了节点11之后就不是AVL tree了

二、非AVL tree的调整

• 如果是添加、删除节点导致一个AVL tree变为非AVL tree。只要调整“插入点至根节点”路径上、平衡状态被破坏之各节点中最深的那一个，便可使整棵树重新获得平衡

演示说明

• 假设该最深节点为X，由于节点最多拥有两个子节点，而所谓“平衡被破坏”意味着X的左右两棵子树的高度相差2，因此我们可以轻易将情况分为4种：
  • 1.插入点位于X的左子节点的左子树——左左
  • 2.插入点位于X的左子节点的右子树——左右
  • 3.插入点位于X的右子节点的左子树——右左
  • 4.插入点位于X的右子节点的右子树——右右
• 情况1,4彼此对称，称为外侧（outside）插入，可以采用单旋转操作调整解决
• 情况2,3彼此对称，称为内侧（inside）插入，可以采用双旋转操作调整解决

三、非AVL tree的调整之“单旋转”

• 为了调整平衡状态，我们希望将A子树提高一层，并将C子树下降一层，解析如下：
  • 把K1向上提起，使K2自然下滑，并将B子树挂到K2的左侧
  • 因为K2>k1，所以K2必须称为新树中K1的右子节点
  • 未旋转前B位于K1-K2之间，所以旋转之后，B必须位于K1右侧，K2的左侧
• 下图显示的是“左左”外侧插入，至于“右右”外侧插入也是如此

四、非AVL tree的调整之“双旋转”

• 下图左侧为内侧插入所造成的不平衡状态
• 单旋转不能解决这种情况：
  • 因为，我们不能再以K3为根节点
  • 其次，我们不能将K3和K1做一次单旋转，因为旋转之后还是不平衡
• 双旋转可以解决这种情况：
  • 以K2为新的根节点
  • 这使得K1必须成为K2的左子节点，K3必须成为K2的右子节点

• 为什么称为双旋转哪，因为它利用两次单旋转，如下图所示

• 上图显示的是“左右”外侧插入，至于“右左”外侧插入也是如此