AVL平衡树
特征：
- AVL
树既是
二叉搜索树，也是平衡二叉树，同时满足这两类二叉树的所有性质 - AVL 树是一种平衡二叉搜索树
属性：
- 节点高度
- 节点平衡因子：节点左子树的高度减去右子树的高度，空节点的平衡因子为0
AVL 树旋转：
- 作用：
- AVL 树的特点在于“旋转”操作，它能够在不影响二叉树的中序遍历序列的前提下，使失衡节点重新恢复平衡
- 旋转操作既能保持“二叉搜索树”的性质，也能使树重新变为“平衡二叉树”
- 旋转：
- 左旋
- 右旋
- 先左旋再右旋
- 先右旋再左旋
四种旋转情况的选择条件
| 失衡节点的平衡因子 | 子节点的平衡因子 | 应采用的旋转方法 |
|---|---|---|
| > 1 （左偏树） | ≥ 0 | 右旋 |
| > 1 （左偏树） | < 0 | 先左旋后右旋 |
| < −1 （右偏树） | ≤ 0 | 左旋 |
| < −1 （右偏树） | > 0 | 先右旋后左旋 |
AVL树的应用：
- 组织和存储大型数据，适用于高频查找、低频增删的场景。
- 数据库中的索引
- 红黑树也是一种常见的平衡二叉搜索树。
- 相较于 AVL 树，红黑树的平衡条件更宽松，插入与删除节点所需的旋转操作更少，节点增删操作的平均效率更高。