最佳二叉排序樹

具有最小平均比較次數

平衡二叉排序樹

平衡二叉樹（AVL樹）：二叉樹中每個節(jié)點的左右子樹高度都差不多；平衡二叉樹或者是空樹，或者其左右子樹都是平衡二叉樹，且左右子樹的深度差的絕對值不超過1；
平衡因子BF：右子樹與左子樹的高度差，取值只有-1,0,1；

調整平衡的模式

若失去平衡，首先調整最小不平衡子樹，即離插入節(jié)點最近，且根節(jié)點的平衡因子大于1的子樹；若調整后最小不平衡子樹恢復平衡，且恢復到插入前的高度，那么整棵樹也就恢復平衡；

最小不平衡子樹的根為A，調整動作分為4種：

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

LL型調整:

在A的左子節(jié)點(L)的左子樹(L)中插入新節(jié)點，使A的平衡因子由-1變成-2，打破了平衡；
調整規(guī)則：將A的左子節(jié)點B提升為新的二叉樹的根，原來的根A連同其右子樹Y向右下方旋轉成B的右子樹；B的右子樹調整為A的左子樹；

RR型調整：

在A的右子節(jié)點(R)的右子樹(R)中插入新節(jié)點，使A的平衡因子由1變成2，打破平衡；
調整規(guī)則：將A的右子節(jié)點B提升為新二叉樹的根，原來的根A連同其左子樹向左下旋轉成B的左子樹；B的原左子樹\beta作為A的右子樹;

LR型調整 ：

在A的左子節(jié)點（L）的右子樹（R）中插入新節(jié)點，使A的平衡因子由-1變成-2，打破平衡；

調整規(guī)則:設C是A的左子節(jié)點的右子節(jié)點；

• 將A的孫子節(jié)點C提升為新的二叉樹的根；
• 將C的父節(jié)點連同其左子樹向左下旋轉成為新根C的左子樹；
• 將C的左子樹稱為B的右子樹
• 原來根A連同其左子樹向右下旋轉成為C的右子樹；
• 將C的右子樹變?yōu)锳的左子樹

RL型調整：

在A的右子樹（R）的左子樹(L)中插入新節(jié)點，使A的平衡因子由1變成2，打破平衡；
調整規(guī)則：設C是A的右子樹的左子樹

• 將A的右子節(jié)點C提升為新二叉樹的根
• 原來C的父節(jié)點B連同其右子樹向右下旋轉稱為新根C的右子樹；
• 原來C的右子樹變成B的左子樹
• 原根A連同其左子樹向左下旋轉成為C的左子樹；
• C的左子樹成為A的右子樹