最佳二叉排序树
具有最小平均比较次数
平衡二叉排序树
平衡二叉树（AVL树）：二叉树中每个节点的左右子树高度都差不多；平衡二叉树或者是空树，或者其左右子树都是平衡二叉树，且左右子树的深度差的绝对值不超过1；
平衡因子BF：右子树与左子树的高度差，取值只有-1,0,1；
调整平衡的模式
若失去平衡，首先调整最小不平衡子树，即离插入节点最近，且根节点的平衡因子大于1的子树；若调整后最小不平衡子树恢复平衡，且恢复到插入前的高度，那么整棵树也就恢复平衡；
最小不平衡子树的根为A，调整动作分为4种：
- LL型调整 2.RR型调整
3.LR型调整 4.RL型调整
LL型调整:A(%5Cgamma)%20%3D%20(%5Calpha)B(%5Cbeta%20A%20%5Cgamma))
在A的左子节点(L)的左子树(L)中插入新节点，使A的平衡因子由-1变成-2，打破了平衡；
调整规则：将A的左子节点B提升为新的二叉树的根，原来的根A连同其右子树Y向右下方旋转成B的右子树；B的右子树调整为A的左子树；
RR型调整：A(%5Cbeta%20B%20%5Cgamma)%20%3D%20(%5Calpha%20A%20%5Cbeta)B(%5Cgamma))
在A的右子节点(R)的右子树(R)中插入新节点，使A的平衡因子由1变成2，打破平衡；
调整规则：将A的右子节点B提升为新二叉树的根，原来的根A连同其左子树向左下旋转成B的左子树；B的原左子树\beta作为A的右子树;
LR型调整 ：B(%5Cbeta%20C%20%5Cgamma))A(%5Cdelta)%20%3D%20(%5Calpha%20B%20%5Cbeta)C(%5Cgamma%20A%20%5Cdelta))
在A的左子节点（L）的右子树（R）中插入新节点，使A的平衡因子由-1变成-2，打破平衡；
调整规则:设C是A的左子节点的右子节点；
- 将A的孙子节点C提升为新的二叉树的根；
- 将C的父节点连同其左子树向左下旋转成为新根C的左子树；
- 将C的左子树
称为B的右子树
- 原来根A连同其左子树
向右下旋转成为C的右子树；
- 将C的右子树
RL型调整：A((%5Cbeta%20C%20%5Cgamma)B(%5Cdelta))%20%3D%20(%5Calpha%20A%20%5Cbeta)C(%5Cgamma%20B%20%5Cdelta))
在A的右子树（R）的左子树(L)中插入新节点，使A的平衡因子由1变成2，打破平衡；
调整规则：设C是A的右子树的左子树
- 将A的右子节点C提升为新二叉树的根
- 原来C的父节点B连同其右子树
- 原来C的右子树
变成B的左子树
- 原根A连同其左子树
向左下旋转成为C的左子树；
- C的左子树
