跳转至

AVL 树

AVL 树,是一种平衡的二叉搜索树

性质

  1. 空二叉树是一个 AVL 树
  2. 如果 T 是一棵 AVL 树,那么其左右子树也是 AVL 树,并且 |h(ls) - h(rs) \leq 1| ,h 是其左右子树的高度
  3. 树高为 O(\log n)

平衡因子:右子树高度 - 左子树高度

插入结点

与 BST(二叉搜索树)中类似,先进行一次失败的查找来确定插入的位置,插入节点后根据平衡因子来决定是否需要调整。

删除结点

删除和 BST 类似,将结点与后继交换后再删除。

删除会导致树高以及平衡因子变化,这时需要沿着被删除结点到根的路径来调整这种变化。


评论