平衡二叉树（AVL树）_请写出并证明在一个树高为 h 的 avl 平衡二叉树中完成一次移除结点操作的时间复杂

平衡二叉树：

• 二叉查找树的一种
• 查找的时间复杂度为O(log n)
• 插入和删除的时间复杂度也是O(log n)

什么是二叉排序树（二叉查找树）？

1. 左子树不为空的时候，所有结点的值均小于根结点值
2. 右子树不为空的时候，所有结点的值均大于根结点值
3. 左右子树均为二叉排序树

由于建树是通过递归进行的，所以左右子树一定满足上述情况

如何评估一棵树是否为平衡二叉树？

• 使用平衡因子

平衡因子：以某个结点为当前根结点，用当前根结点的左子树高度减去右子树高度的结果就是平衡因子

平衡的两种情况：

• 理想平衡： 包含n个结点的二叉树，若树高正好为log₂n，则是理想平衡
• 适度平衡： 在渐进意义（经过有限次调整后）下适当放宽标准，例如：树高渐进地不超过O(log n) 属于适度平衡

AVL树属于适度平衡，每个结点的平衡因子范围在（-1，0，1）三个数之中， 即：平衡因子的绝对值不超过1，最多为1

最小不平衡子树： 距离插入点最近的，而且平衡因子的而绝对值大于1的结点为根的子树

AVL树通过不断地旋转，平衡，来达到性能上的各种指标 ， 所以，核心操作就是旋转，而查找的时候根据左小右大的特点即可规划相应查找路径

平衡因子符号为正：右旋，顺时针
平衡因子符号为负：左旋，逆时针

旋转操作操作方法记忆口诀：

1. 平衡因子超范围 ， 符号决定向哪旋。
2. 因子为正向右旋 ， 因子为负向左旋。
3. 插入删除新结点 ， 子树因子重新算。
4. 算完符号若不同 ， 应将符号先统一。
5. 为正为负自己定 ， 统一之后再旋转。
6. 旋转调整二叉树 ， 调整过后又平衡。
7. 调整需找基准根 ， 任意结点均可作。
8. 右旋有右则接左 ， 左旋有左则接右。
9. 平衡因子计算多 ， 特殊需求换结构。

注释：

1. AVL树每次操作之后都会计算相关结点的平衡因子，发现绝对值大于1的时候会进行旋转调整
2. AVL树根据平衡因子符号的正负进行相应方向的旋转调整
3. 当一棵子树的平衡因子符号不同时，而且需要进行旋转调整的时候，应当先统一他们的符号，（具体情况具体分析）再进行旋转调整
4. 被选取作为根结点的某个结点，没有限制，因为递归遍历的时候每个点都可作为根结点，只不过左右孩子的数量不同而已
5. 删除某个结点之后，重新平衡的过程，最少进行（log n）次旋转（即：复杂度为 Ω (log n) 而不是 O(log n) ），从而频繁地使树的结构发生变化 ，若特殊场合对某些指标有特殊要求，则要考虑使用其他数据结构