Avl

AVL

  • 二叉搜索树,在插入和删除时可能失衡
  • 如在插入和删除时旋转,始终令其保持平衡,则成为自平衡点二叉搜索树
  • AVL是自平衡二叉搜索树的实现之一

Unbalance Situation

  • LL 一次右旋
    • 失衡节点左边高
    • 失衡节点左孩子左边高
  • LR 失衡节点左子树左旋,再右旋
    • 失衡节点左边高
    • 失衡节点左孩子右边高
  • RL 失衡节点右子树右旋,再左旋
    • 失衡节点右边高
    • 失衡节点右孩子左边高
  • RR 一次左旋
    • 失衡节点右边高
    • 失衡节点右孩子右边高

BackLink