1.基本概念

　? ?平衡二叉樹(AVL樹)，或為空樹,或為如下性質的二叉排序樹:左右子樹深度之差的絕對值不超過1;左右子樹仍然為平衡二叉樹.

　　平衡因子BF=左子樹深度-右子樹深度.

　　平衡二叉樹每個結點的平衡因子只能是1，0，-1。若其絕對值超過1，則該二叉排序樹就是不平衡的。

　　如圖所示為平衡樹和非平衡樹示意圖：

2.平衡二叉樹的算法思想

若向平衡二叉樹中插入一個新結點后破壞了平衡二叉樹的平衡性。首先要找出插入新結點后失去平衡的最小子樹根結點的指針。然后再調整這個子樹中有關結點之間的鏈接關系，使之成為新的平衡子樹。當失去平衡的最小子樹被調整為平衡子樹后，原有其他所有不平衡子樹無需調整，整個二叉排序樹就又成為一棵平衡二叉樹。

　　失去平衡的最小子樹是指以離插入結點最近，且平衡因子絕對值大于1的結點作為根的子樹。假設用A表示失去平衡的最小子樹的根結點，則調整該子樹的操作可歸納為下列四種情況。

2.1 LL型平衡旋轉法

由于在A的左孩子B的左子樹上插入結點F，使A的平衡因子由1增至2而失去平衡。故需進行一次順時針旋轉操作。即將A的左孩子B向右上旋轉代替A作為根結點，A向右下旋轉成為B的右子樹的根結點。而原來B的右子樹則變成A的左子樹。

2.2 RR型平衡旋轉法

由于在A的右孩子C 的右子樹上插入結點F，使A的平衡因子由-1減至-2而失去平衡。故需進行一次逆時針旋轉操作。即將A的右孩子C向左上旋轉代替A作為根結點，A向左下旋轉成為C的左子樹的根結點。而原來C的左子樹則變成A的右子樹。

2.3 LR型平衡旋轉法

由于在A的左孩子B的右子數上插入結點F，使A的平衡因子由1增至2而失去平衡。故需進行兩次旋轉操作(先逆時針，后順時針)。即先將A結點的左孩子B的右子樹的根結點D向左上旋轉提升到B結點的位置，然后再把該D結點向右上旋轉提升到A結點的位置。即先使之成為LL型，再按LL型處理。

　　如圖中所示，即先將圓圈部分先調整為平衡樹，然后將其以根結點接到A的左子樹上，此時成為LL型，再按LL型處理成平衡型。

2.4 RL型平衡旋轉法

由于在A的右孩子C的左子樹上插入結點F，使A的平衡因子由-1減至-2而失去平衡。故需進行兩次旋轉操作(先順時針，后逆時針)，即先將A結點的右孩子C的左子樹的根結點D向右上旋轉提升到C結點的位置，然后再把該D結點向左上旋轉提升到A結點的位置。即先使之成為RR型，再按RR型處理。

來源于網絡

20考研的QQ群，有各個學校的考研資料，歡迎加入

群號是?984844252

您還可以在以下平臺找到我們

你點的每個在看，我都認真當成了喜歡

總結

以上是生活随笔為你收集整理的平衡二叉树平衡因子_数据结构：平衡二叉树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。