平衡二叉树的相关概念
定义
为了避免树的的高度增长过快，降低二叉排序树性能，规定在插入和删除结点时，保证任意节点的左、右子树高度差的绝对值不超过1，把这样的二叉树称为平衡二叉树，或AVL树。定义结点左子树与右子树的高度差为该结点的平衡因子，则平衡二叉树的平衡因子的值只可能是-1、0或1。
性质
1、左子树与右子树的高度之差绝对值小于等于1；
2、左子树与右子树也是平衡二叉树。引入平衡二叉树的目的是为了提高查找效率，其平均查找长度为O（log₂n），结点的平衡因子的定义是结点的左子树深度ui右子树深度之差，平衡二叉树的平衡因子的值只可能是-1、0或1。
插入操作
LL平衡旋转
在A的左孩子的左子树插入导致的不平衡
右单旋转
RR平衡旋转
在A的右孩子右子树插入导致的不平衡
左单旋转
LR平衡旋转
在A的左孩子的右子树中插入导致的不平衡
先左旋在右旋
RL平衡旋转
在A的右孩子的左子树中插入导致的不平衡
先左旋在右旋
例题
王道例题
严蔚敏
408例题&其他
题1
解析
题2
解析
所以选D
题3
解析
