AVL_3">平衡二叉树（AVL树）
- 前提：二叉搜索树
- 所有结点的 (左子树高度 - 右子树高度）的绝对值 <= 1
左子树高度 - 右子树高度 —— 平衡因子 - 插入、查找、构建、删除过程与二叉搜索树一致，但是失衡的时候需要调整。
平衡二叉树的调整？
1. 左旋
- 将失衡结点左旋（逆时针旋转），发生冲突时 —— 冲突的左孩变成右孩
2. 右旋
- 将失衡结点右旋（顺时针旋转），发生冲突时 ——冲突的右孩变左孩
四种失衡情况
1. LL型
- 失衡结点平衡因子 = 2，失衡结点的左孩子的平衡因子 = 1
- 失衡结点右旋。
2. LR型
- 失衡结点平衡因子 = 2，失衡结点的左孩子的平衡因子 = -1
- 失衡节点左孩子先左旋，然后失衡结点再右旋。
3. RR型
- 失衡结点平衡因子= -2，失衡结点的右孩子的平衡因子 = -1
- 失衡节点左旋。
4. RL型
- 失衡结点平衡因子= -2，失衡结点的右孩子的平衡因子 = 1
- 失衡结点的右孩子先右旋，失衡结点再左旋。
插入节点后，若多个祖先结点失衡？
- 只需要调整距离插入结点最近的失衡结点，其他失衡结点会自然平衡。
删除节点后，调整？
- 需要依次对每个祖先进行检查并调整
