最佳二叉排序树

具有最小平均比较次数

平衡二叉排序树

平衡二叉树（AVL树）：二叉树中每个节点的左右子树高度都差不多；平衡二叉树或者是空树，或者其左右子树都是平衡二叉树，且左右子树的深度差的绝对值不超过1；
平衡因子BF：右子树与左子树的高度差，取值只有-1,0,1；

调整平衡的模式

若失去平衡，首先调整最小不平衡子树，即离插入节点最近，且根节点的平衡因子大于1的子树；若调整后最小不平衡子树恢复平衡，且恢复到插入前的高度，那么整棵树也就恢复平衡；

最小不平衡子树的根为A，调整动作分为4种：

1. LL型调整 2.RR型调整
   3.LR型调整 4.RL型调整

LL型调整:

在A的左子节点(L)的左子树(L)中插入新节点，使A的平衡因子由-1变成-2，打破了平衡；
调整规则：将A的左子节点B提升为新的二叉树的根，原来的根A连同其右子树Y向右下方旋转成B的右子树；B的右子树调整为A的左子树；

RR型调整：

在A的右子节点(R)的右子树(R)中插入新节点，使A的平衡因子由1变成2，打破平衡；
调整规则：将A的右子节点B提升为新二叉树的根，原来的根A连同其左子树向左下旋转成B的左子树；B的原左子树\beta作为A的右子树;

LR型调整 ：

在A的左子节点（L）的右子树（R）中插入新节点，使A的平衡因子由-1变成-2，打破平衡；

调整规则:设C是A的左子节点的右子节点；

• 将A的孙子节点C提升为新的二叉树的根；
• 将C的父节点连同其左子树向左下旋转成为新根C的左子树；
• 将C的左子树称为B的右子树
• 原来根A连同其左子树向右下旋转成为C的右子树；
• 将C的右子树变为A的左子树

RL型调整：

在A的右子树（R）的左子树(L)中插入新节点，使A的平衡因子由1变成2，打破平衡；
调整规则：设C是A的右子树的左子树

• 将A的右子节点C提升为新二叉树的根
• 原来C的父节点B连同其右子树向右下旋转称为新根C的右子树；
• 原来C的右子树变成B的左子树
• 原根A连同其左子树向左下旋转成为C的左子树；
• C的左子树成为A的右子树