平衡二叉树 AVL树

Amos Xia, 2018-06-09 08:57:11

AVL树时带有平衡条件的二叉查找树. 这个平衡条件是每个结点的左子树和右子数的高度最多差1的二叉查找树(假设空树的高度为-1).

高度为h的AVL树中, 最少结点数S(h) = S(h-1) + S(h-2) + 1, 即最少结点左子树+最少结点右子树+根节点.

除了插入/删除操作, 绝大部分操作都可以以时间O(logN)来执行

插入/删除操作有可能会破坏树的平衡, 需要通过旋转来重新平衡

旋转针对的时被破坏了平衡部分的树, 通过旋转将破坏平衡的子树提升1层来重新达到平衡

树出现不平衡的情况:

  • 对左子树的左子树进行插入, 单旋转
  • 对左子树的右子树进行插入, 双旋转
  • 对右子树的左子树进行插入, 双旋转
  • 对右子树的右子树进行插入, 单旋转

AVL树的高度 = max(左子树的高度, 右子树的高度) + 1

删除

  • 立即删除结点
  • 懒惰删除

知识共享许可协议
本作品采用知识共享署名 4.0 国际许可协议进行许可。


Copyright© 2018 s2u2m