AVL树概述 | AI生成和翻译
什么是AVL树？
AVL树是一种自平衡二叉搜索树（BST），由Georgy Adelson-Velsky和Evgenii Landis于1962年发明（因此得名）。与任何二叉搜索树一样，它以排序方式存储数据：左子树中的所有节点都小于父节点，右子树中的所有节点都大于父节点。其关键特性在于，在插入或删除操作后会自动调整结构以保持平衡。
工作原理
- 平衡因子：对于每个节点，树会计算一个“平衡因子”，即左子树高度减去右子树高度。该值必须始终为-1、0或+1（即子树高度最多相差一级）。
- 平衡旋转：如果插入或删除操作破坏了平衡因子：
- 单旋转（左旋或右旋）用于修复较近子节点的不平衡。
- 双旋转（左右旋或右左旋）用于处理较远子节点的不平衡。
- 这些旋转操作在保持二叉搜索树性质的同时恢复平衡，且每次操作的时间复杂度为O(1)。
示例：若将节点按排序顺序插入普通二叉搜索树，会形成链表（不平衡）。而在AVL树中，旋转操作能保持大致的高度平衡，如下简化的前后对比：
不平衡状态（插入1,2,3后）：
2
/
1
/
3 （实际向右倾斜：1→2→3）
旋转后：
2
/ \
1 3
独特之处
- 性能保证：与普通二叉搜索树最坏情况下可能退化为O(n)（如倾斜成链表）不同，AVL树确保搜索、插入和删除操作的平均和最坏情况时间复杂度均为O(log n)。这使其非常适合需要稳定性能的应用场景，如数据库或符号表。
- 权衡考量：相比其他平衡树（如红黑树允许稍多的不平衡以换取更快的插入/删除），AVL树更严格。它优先考虑搜索速度而非修改速度。
- 空间开销：每个节点需要额外字段记录高度/平衡信息，但影响较小。
简而言之，AVL树的“特殊”之处在于其严格的自平衡特性，能将可能混乱的二叉搜索树转变为稳定可靠的对数级性能数据结构。
更多细节请参阅：维基百科AVL树词条