AVL树时带有平衡条件的二叉查找树. 这个平衡条件是每个结点的左子树和右子数的高度最多差1的二叉查找树(假设空树的高度为-1).
高度为h的AVL树中, 最少结点数S(h) = S(h-1) + S(h-2) + 1, 即最少结点左子树+最少结点右子树+根节点.
除了插入/删除操作, 绝大部分操作都可以以时间O(logN)来执行
插入/删除操作有可能会破坏树的平衡, 需要通过旋转来重新平衡
旋转针对的时被破坏了平衡部分的树, 通过旋转将破坏平衡的子树提升1层来重新达到平衡
树出现不平衡的情况:
- 对左子树的左子树进行插入, 单旋转
- 对左子树的右子树进行插入, 双旋转
- 对右子树的左子树进行插入, 双旋转
- 对右子树的右子树进行插入, 单旋转
AVL树的高度 = max(左子树的高度, 右子树的高度) + 1
删除
- 立即删除结点
- 懒惰删除