AVL 树AVL tree

严格限制左右子树的高度差。

核心约束: 任意节点两侧子树高度差不超过 1。
适用问题: 需要严格控制搜索路径长度的有序集合。
边界与取舍: 更新时需要维护高度并可能多次旋转。

一棵平衡的二叉搜索树示例；普通二叉树不必满足键序。

常见操作#

n 为节点数，k 为范围查询输出数；键比较按常数成本计算。

操作	时间复杂度	条件与说明
查找 / 插入 / 删除	$O(\log n)$	最坏界；更新需维护每个节点左右子树高度差不超过 1。
最小 / 最大 / 前驱 / 后继	$O(\log n)$	从根定位；有缓存或迭代器时特定操作可更快。
有序遍历	$O(n)$	递归遍历的辅助栈为 $O(\log n)$ 。
范围枚举	$O(\log n+k)$	输出成本不可省略。

时间与空间#

时间复杂度: 查找 / 更新最坏 $O(\log n)$
存储空间: $O(n)$

每个节点保存高度或平衡信息；旋转与高度回传包含在更新时间内。

基础原理参考资料

Princeton · AVLTreeSTAVL 平衡条件、操作及最坏复杂度。