1. AVL树
(1) 定义
平衡因子（Balance Factor）：某节点的 左右子树 的高度差
AVL树的特点：
- 每个节点的 平衡因子 只可能是1、0、-1（绝对值<=1，否则失衡）
- 每个节点的 左右子树 高度差不超过1
- 搜索、添加、删除的时间复杂度是
)
平衡
失衡
(2) 解决失衡方法
1> LL - 右旋转（单旋）
LL
2> RR - 左旋转（单旋）
RR
3> LR - RR左旋转，LL右旋转（双旋）
LR
4> RL - LL右旋转，RR左旋转（双旋）
RL
(3) 添加导致的失衡
示例：往下面这棵子树添加 13
- 最坏情况：可能会导致 所有祖先节点 都失衡
- 父节点、非祖先节点，都不可能失衡
添加导致的失衡
(4) 删除导致的失衡
示例：删除子树中的 16
- 可能会导致 父节点或祖先节点 失衡
- 只有一个节点会失衡，其他节点 都不可能失衡
删除导致的失衡
删除导致的失衡
(5) 总结
添加
- 可能会导致 所有祖先节点 都失衡
- 只要让 高度最低的失衡节点 恢复平衡，整棵树就恢复平衡【仅需
次调整】
删除
- 可能会导致 父节点或祖先节点 失衡（只有1个节点会失衡）
- 恢复平衡后，可能会导致 更高层的祖父节点 失衡【最多需要
平均时间复杂度
- 搜索：
- 添加：
- 删除：
