文章目錄

• 一：AVL樹基本概念
• 二：AVL樹實現原理
• • （1）構建AVL樹
  • （2）構建演示
  • （3）旋轉方法
  • • A：右單旋轉調整（插入到較高左子樹左側）
    • B：左單旋轉調整（插入到較高右子樹右側）
    • C：先左后右雙旋轉調整（插入到較高左子樹右側）
    • D：先右后左雙旋轉調整（插入到較高右子樹左側）
• 三：AVL樹相關代碼

一：AVL樹基本概念

二叉排序樹有一個缺陷：樹的高度會直接影響其查找效率，且樹越高效率越差，效率最差時為一棵單分支樹

平衡二叉樹(Self-Balancing Binary Search Tree)：它首先是一顆二叉排序樹，其中每個節點的左右子樹高度之差絕對值不超過1。將二叉樹上結點左子樹和右子樹高度之差的絕對值稱之為平衡因子BF(Balance Factor)，因此，平衡因子BF的取值只可能是-1、0和1中的一種

• -1：表示該結點左子樹高度小于右子樹高度
• 0：表示該結點左子樹高度等于右子樹高度
• 1：表示該結點左子樹高度大于右子樹高度

以下是一些例子

• ①是AVL樹
• ②不是AVL樹，因為AVL樹前提必須首先是二叉排序樹
• ③不是AVL樹，因為結點58左子樹高度為2，而右子樹為高度為0，BF>1
• ④是AVL樹

最小不平衡子樹：距離插入點最近的，且平衡因子絕對值大于1的結點為根的子樹

如下，當插入新節點37時，距離它最近的平衡因子絕對值超過1的結點是58，所以58開始以下的子樹為最小不平衡子樹

二：AVL樹實現原理

（1）構建AVL樹

AVL樹構建思想：在構建二叉排序樹的過程中，每當插入一個結點時，先檢查該結點的插入是否導致了平衡性被破壞，若不是則繼續插入；若是則找出最小不平衡子樹，在保持二叉排序樹特性的前提下，調整最小不平衡子樹中各結點的鏈接關系，也即平衡調整，進行相應的旋轉，使之成為新的平衡子樹

int arr[10]={3,2,1,4,5,6,7,10,9,8}

假設上面數組需要構建為AVL樹，由于AVL樹首先是BST樹，所以會構建成下面這樣

但是我們知道，BST樹很忌諱其高度太高，所以如果能調整為下面這樣那再合適不過了，因為下面的樹依然是一棵BST樹，但是其高度小了很多，查找效率自然也會得到提高

因此對于AVL樹的研究重點就在于如何調整，也就是如何旋轉

（2）構建演示

對于$3$和$2$，構建時沒有任何問題

來到$1$并將其插入后，發現根節點$3$的平衡因子變為了2，此時整棵樹成為最小不平衡子樹，需要進行調整：右單旋轉調整(點擊跳轉查看)

• 因為此時結點插入到了較高左樹左側

• 調整后，$2$成為了根節點，$3$成為了$2$的右孩子，此樹高度平衡

接著結點$4$到來，平衡因子沒有變化

接著結點$5$到來，結點$3$的平衡因子變為-2，需要進行調整：左單旋轉調整(點擊跳轉查看)

• 因為此時結點插入到了較高右樹右側
  

• 再次達到平衡

接著結點$6$到來，此時根節點$2$的平衡因子變為了-2，進行調整 左單旋轉調整(點擊跳轉查看)

• 因為此時結點插入到了較高右樹右側

結點$7$到來，結點5的平衡因子變為了-2，進行調整 左單旋轉調整(點擊跳轉查看)

• 因為此時結點插入到了較高右樹右側

結點$10$到來，結構無變化

結點$9$到來，此時結點$7$的BF變為了-2，理應進行左單旋轉調整，但是由于此時新結點插入到了較高右樹左側，故直接使用左單旋轉調整是不可以的。（具體原因跳轉過去會詳細解釋），需要進行 先右后左雙旋轉調整(點擊跳轉查看)

• 很明顯$9$插入了$7$的右子樹左側，故不能直接使用左單旋轉

• 故先對$9$和$10$進行右旋，再對$7$、$9$和$10$進行左旋

接著結點$8$插入，使結點$6$的BF變為了-2，屬于插入到了較高右樹的左側，故需要進行 先右后左雙旋轉調整(點擊跳轉查看)

（3）旋轉方法

大家最頭疼的可能就是如何選擇旋轉方法了，總結如下，只需按照如下邏輯選擇即可

A：右單旋轉調整（插入到較高左子樹左側）

下圖中為抽象樹，三角形表示的樹為高度平衡的二叉樹排序樹。如下情況中，結點A的平衡因子絕對值為1，左子樹較高

此時來了一個新的結點恰好插入到了B結點的左樹，導致A結點的平衡因子變為2，樹不平衡，需要進行調整

調整時：將結點A下移一個高度，B上移一個高度，然后把B的右子樹掛在A的左子樹處（這樣做可以保證二叉排序樹的特性）

B：左單旋轉調整（插入到較高右子樹右側）

左單調整和右單調整情況恰好相反，調整時結點B上移，結點A下移，讓結點B的左子樹做結點A的右子樹

C：先左后右雙旋轉調整（插入到較高左子樹右側）

在右單旋轉調整中，由于新的結點插入到了較高左子樹的左側，所以調整后可以使樹平衡

但如果此時將新結點插入到較高左子樹的右側

此時如果繼續使用右單旋轉調整，你會發現怎么也調整不過去，依然不平衡

在這種情況下就要使用到雙旋轉調整了

我們先把較高左子樹的右子樹拆分一下，拆分為兩棵樹

大家會發現此時如果要在B的右側插入一個結點有兩個選擇——要么插入到C的左側，要么插入到C的右側
這里我以插入到C的右側為例

接著進行雙旋轉調整：先對B樹進行左單旋轉

形成了這樣一顆樹

然后對這顆樹再進行右單旋轉調整，樹就平衡了

• 本例是插入到了C的右側，如果插入到了C的左側，調整也是一樣的
  

D：先右后左雙旋轉調整（插入到較高右子樹左側）

• 特別注意：先看C部分再看本部分，C部分中解釋較為詳細，本部分只是邏輯相反

在左單旋轉調整中，面對的情況是新節點插入到了較高右子樹的右側，而如果新節點插入到了較高右子樹的左側，那么就要使用先右后左雙旋轉調整

所以在這種情況下，先對右子樹進行右單旋轉調整，然后再進行左單旋轉調整

三：AVL樹相關代碼

對于AVL樹考研數據結構基本不涉及代碼，其旋轉過程邏輯并不難，只是需要多捋一捋。其代碼實現有很多值得注意的地方，且稍不留心就容易掉坑，有興趣的同學可以查看我的另一篇文章，其中代碼都是可以跑通的，用C++實現

點擊跳轉

新人創作打卡挑戰賽發博客就能抽獎！定制產品紅包拿不停！

總結

以上是生活随笔為你收集整理的(王道408考研数据结构)第五章树-第四节2：平衡二叉树(AVL)及其旋转的全部內容，希望文章能夠幫你解決所遇到的問題。

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