定义
- 平衡二叉树(AVL树)是特殊的二叉排序树，特殊的地方在于左右子树的高度之差绝对值不超过1，而且左右子树又是一棵平衡二叉树
- 定义结点左子树与右子树的高度差为该结点的平衡因子，则平衡二叉树结点的平衡因子的值只可能是−1、0或1。
建立和调整
平衡因子
某结点的左子树与右子树的高度(深度)差即为该结点的平衡因子（BF,Balance Factor）
- 平衡二叉树的建立过程和二叉排序树的建立过程是相似的，都是从一棵空树开始陆续插入结点。不同的地方在于对于平衡二叉树的建立过程中，由于插入结点可能会破坏结点的平衡性，所以需要进行平衡调整。
- 以距离插入结点最近的，平衡因子绝对值大于1的结点为根的子树称为最小不平衡子树*
LL调整
RR调整
RL&LR
解决办法：先将孩子结点的平衡因子转换成和根结点正负一致，再进行调整
o
京公网安备 11010502036488号