《数据结构》—— 平衡二叉树的定义、插入及最小不平衡子树处理

一、平衡二叉树的定义

为避免树的高度增长过快，降低二叉排序树的性能，规定在插入和删除二叉树结点时，要保证任意结点的左、右子树高度差的绝对值不超过1，将这样的二叉树称为平衡二叉树(Balanced Binary Tree)，简称平衡树。

结点的平衡因子 = 左子树高-右子树高。

定义结点左子树与右子树的高度差为该结点的平衡因子，则平衡二叉树结点的平衡因子的值只可能是一-1、0或1。

二、平衡二叉树的插入

我们要思考在二叉排序树中插入新结点后，如何保持平衡？
插入新结点后，查找路径上的所有结点都有可能受到影响，使得平衡因子的值会超过1。那我们怎么办呢？

如上图，首先从插入点67往回找到第一个不平衡结点70，调整该结点作为根的子树，这个子树我们称为是 “最小不平衡子树” 。

接下来我们只需将最小不平衡子树调整为平衡即可，中序为67->68->70。

---

三、平衡二叉树的平衡处理

导致不平衡的插入总结有4种情况。

3.1 调整最小不平衡子树（LL）

在结点A的左孩子(L)的左子树(L)上插入了新结点，导致不平衡。如上图，插入之后 B的左子树BL高为H+1，其他子树高是H，根节点A的平衡因子为2，出现不平衡情况。这时候我们就要进行一次向右的旋转操作：

• 将A的左孩子B向右上旋转代替A成为根结点；
• 将A结点向右下旋转成为B的右子树的根结点；
• 而B的原右子树则作为A结点的左子树。

设指针f指向根结点A，指针p指向A的左子树B结点，gf指针指向A的父结点；

实现f向右下旋转，p向右上旋转;
其中f是爹，p为左孩子，gf为f他爹;
f->lchild = p->rchild;
p->rchild = f;
gf->lchild/rchild = p;

由于BL<B<BR<A<AR，左旋、右旋操作后可以保持二叉排序树的特性。
1
2
3
4
5
6
7

---

为什么要假定所有子树的高度都是H？

• 假如A的右子树AR高为H+1，那当BL插入结点，使得高为H+1时，A的平衡因子=(BL+1)-AR=(H+2) - (H+1) =1，满足平衡条件！！！
• 假如A的右子树AR高为H-1，BL本身高为H，A的平衡因子=(BL+1)-AR=(H+1) - (H-1) =2，在还没插入结点时，根节点A本身就不满足平衡条件！！
• 综上，所有子树的高度必须都是同高H才行。

---

3.2 调整最小不平衡子树（RR）

在结点A的右孩子®的右子树® 上插入了新结点，导致不平衡。如上图，插入之后 B的右子树BR高为H+1，其他子树高是H，根节点A的平衡因子=AL-(BR+1)=H-(H+1+1)=-2，出现不平衡情况。这时候我们就要进行一次向左的旋转操作：

• 将A的右孩子B向左上旋转代替A成为根结点；
• 将A结点向左下旋转成为B的左子树的根结点；
• 而B的原左子树则作为A结点的右子树。

设指针f指向根结点A，指针p指向A的左子树B结点，gf指针指向A的父结点；

实现f向左下旋转， p向左上旋转;
其中f是爹，p为右孩子，gf为f他爹;
f->rchild = p->lchild;
p->lchild = f;
gf->lchild/rchild = p;

由于AL<A<BL<B<BR，左旋、右旋操作后可以保持二叉排序树的特性。
1
2
3
4
5
6
7

---

3.3 调整最小不平衡子树（LR）

如上图，在A的左孩子B的右子树(BR)上插入新结点，A的平衡因
子=BR+1-AR=2，导致以A为根的子树失去平衡。我们可以拆分来看，以B为根节点的最小不平衡子树来看，是一个RR操作，需要一次左旋操作；作为根节点A的最小不平衡子树来看，是一个LL操作，需要一次右旋操作。

因此，调整最小不平衡子树（LR）需要进行两次旋转操作:（先左后右双旋转):

• 先左旋转后右旋转。先将A结点的左孩子B的右子树的根结点C向左上旋转提升到B结点的位置；
• 然后再把该C结点向右上旋转提升到A结点的位置。
  

---

3.4 调整最小不平衡子树（RL）

如上图，在A的右孩子B的左子树(BL)上插入新结点，A的平衡因
子=AL-(BL+1)=-2，导致以A为根的子树失去平衡。我们可以拆分来看，以B为根节点的最小不平衡子树来看，是一个LL操作，需要一次右旋操作；作为根节点A的最小不平衡子树来看，是一个RR操作，需要一次左旋操作。

因此，调整最小不平衡子树（RL）需要进行两次旋转操作:(先右后左双旋转)：

• 先右旋转后左旋转。先将A结点的右孩子B的左子树的根结点C向右上旋转提升到B结点的位置；
• 然后再把该C结点向左上旋转提升到A结点的位置。

---

总之在插入操作中，只有将最小不平衡子树调整平衡，则其他祖先结点都会自然而然的恢复平衡。

---

四、ASL查找效率分析

若树高为h，则最坏情况下，查找一个关键字最多需要对比 h 次，即查找操作的时间复杂度不可能超过 O(h)。
平衡二叉树——树上任一结点的左子树和右子树的高度之差不超过1。
假设以 Nh 表示深度为h的平衡树中含有的最少结点数。则有n0 = 0, n1 = 1, n2 = 2，并且有Nh = Nh-1 + Nh−2 + 1，可以证明含有n个结点的平衡二叉树的最大深度为O(log2n) ，平衡二叉树的平均查找长度为O(log2n)。

例如：T4 = T3 +T2 +1 = 9+4+1 = 14

---

注：资料摘自"王道考研"，侵权请联系删除，谢谢！