数据结构-平衡二叉树
1.定义
平衡二叉树又称为AVL树，或者为空树，或者具有以下性质的二叉树：
- 它的左子树和右子树都是平衡二叉树，且左子树和右子树的高度之差的绝对值不超过1。
- 若将二叉树结点的平衡因子定义为该结点左子树的高度减去其右子树的高度，则平衡二叉树上所有结点的平衡因子只可能是-1、0、1。
- 只要树上有一个结点的平衡因子的绝对值大于1，则该二叉树就不平衡。
最小不平衡树：是指离插入结点最近且以平衡因子的绝对值大于1的结点作为根的子树。
2.插入
1）LL型向右旋转平衡处理
在A结点的左子树的左子树上插入结点C
2） RR型向左旋转平衡处理
在A结点的右子树的右子树上插入结点C
3）LR型先左后右双向旋转平衡处理
在A结点的左子树的右子树上插入结点C
4）RL型 先右后左双向旋转平衡处理
在A结点的右子树的左子树上插入结点C