AVL 树

定义

AVL 树是最早被发明的自平衡二叉搜索树，由 Adelson-Velsky 和 Landis 提出。它要求任意节点的左右子树高度差（平衡因子）的绝对值不超过 1。

原理

每个节点记录子树高度。插入或删除后，沿路径回溯检查平衡因子，一旦失衡就通过旋转恢复平衡。失衡有四种情形：LL 型右旋、RR 型左旋、LR 型先左旋再右旋、RL 型先右旋再左旋。严格的平衡约束使 AVL 树的高度始终保持在 O(log n)，查询性能稳定，但插入删除时旋转较频繁。

复杂度

• 查找：O(log n)
• 插入：O(log n)
• 删除：O(log n)
• 空间复杂度：O(n)

应用场景

• 查询远多于增删、要求查找性能稳定的场景
• 内存数据库索引
• 需要严格平衡的有序集合