如何根据序列构建平衡二叉搜索树？
什么是平衡二叉搜索树（AVL）？
1、AVL树的定义
AVL树又称平衡二叉搜索树，它能保证二叉树高度相对平衡，尽量降低二叉树的高度，提高搜索效率
2、AVL树的特点
（1）AVL的左右子树高度之差的绝对值不超过1
（2）树中的每个左子树和右子树都是AVL树
（3）每个节点都有一个平衡因子,任一节点的平衡因子只能是
（-1、0、1）
(每个节点的平衡因子等于右子树的高度减去左子 树的高度 )
（4）平衡二叉树的高度和结点数量之间的关系也是O(logn)的
什么是右单旋转？
什么是左单旋转？
什么是双旋转？
RR RL LR什么意思？
R：right缩写
L：left缩写
看自己旋转的情况判断
不需要死记硬背
只要能旋转满足平衡就行
实例题目
关键字序列（16，3，7，11，9，26，18，14，15）给出构造AVL树的构造过程
过程
第一步
插入16，计算结点16的平衡因子
平衡因子为0不需要调整、
第二步
插入3，3小于16插入右子树
计算平衡因子为1
不需要调整
第三个结点7，比16小比3大
插入3的右子树
失衡进行调整
LR型调整。
将7上升3作为7右子树16作为左子树
在计算平衡因子
都是0；
第三步
继续插入下一个结点
插入11平衡
继续
第四步
插入9时失衡并且7失衡，16失衡
找最小的失衡子树LL型
将中间结点上升。
第五步
插入26时
计算平衡因子
RR型失衡
插入18RL型失衡
第六步
平衡调整
第七步
插入14平衡
插入15
最后
RL型调整
差最后一步自己变换一下
我就不写了！加油