來源：景禹

作者：景禹

平衡二叉樹基礎(chǔ)篇

什么是平衡二叉樹？

平衡二叉樹（Balanced Binary Tree 或 Height-Balanced Tree）又稱為 AVL 樹，其實就是一顆 平衡的二叉排序樹 ，解決了昨天講的二叉排序樹的不平衡問題，即斜樹。AVL樹或者是一顆空樹，或者是具有下列性質(zhì)的二叉排序樹：

它的左子樹和右子樹都是平衡二叉樹，且左子樹和右子樹的深度之差的絕對值不超過 1 。

什么是平衡因子？

平衡二叉樹上結(jié)點的 平衡因子 ?BF(Balanced Factor) 定義為該結(jié)點的左子樹深度減去它的右子樹的深度，平衡二叉樹上所有結(jié)點的平衡因子只可能是 -1，0，1。

上面的兩個樹就是典型的平衡二叉樹，首先它是一顆二叉排序樹，其次每一個結(jié)點的平衡因子都是 -1，0，1三個數(shù)當中的一個。比如上面的左圖，紅色的數(shù)字為結(jié)點的平衡因子，對于任意一個葉子結(jié)點而言，其左右孩子都為空，左子樹的深度為 0 ，右子樹的深度為 0 ，所以 AVL樹當中的葉子結(jié)點的平衡因子都是 0 ；其他結(jié)點的平衡因子同樣通過左子樹深度減去右子樹深度可以求得，比如上圖中 左側(cè) 的AVL樹中，結(jié)點 3 的 左子樹深度為 2，右子樹深度為1 ，所以結(jié)點3的平衡因子就是 1；上圖中 右側(cè) 的AVL樹中，結(jié)點 3 的左子樹深度為2，右子樹深度為3，則平衡因子為 2 - 3 = -1 。再來看看不平衡的情況。

上圖中就是不平衡的二叉排序樹，非AVL樹 。上圖 左側(cè) 的樹中，結(jié)點 6 的平衡因子為 2，該平衡因子是結(jié)點 6 左子樹深度 3 減去右子樹深度 1 所得；右側(cè) 的樹中，結(jié)點 6 的左子樹深度0減去右子樹深度2，即為-2， 所以這兩棵樹都不是平衡二叉樹。

什么是左旋？什么又是右旋？

為了確保每一次插入操作后，樹仍然是一顆 AVL 樹，我們就需要對之前分享的 BST(二叉排序樹) 的插入操作進行平衡操作，而左旋和右旋操作就是保證二叉排序樹特性的基礎(chǔ)之上，維持每一次插入操作后樹一直保持AVL樹的基本操作。

、 和 分別表示 或 的子樹。右旋操作 將 的右子樹 作為 的左子樹，然后將 作為 的右子樹。這樣做的原因何在？還記得平衡二叉樹的特性是，對于樹中的每一個結(jié)點，其左子樹中的結(jié)點均比結(jié)點的值小，右子樹中結(jié)點的值均比結(jié)點的值大，那么對于上圖 左側(cè) 的樹而言， 的右子樹 的值一定比 ? 的值大且一定比根結(jié)點 的值小，所以將 的右子樹 的值作為根結(jié)點 的值并不會破壞二叉排序樹的特性，此外 的值大于其左孩子 的值，將 作為根結(jié)點時， 作為右孩子也不會破壞二叉樹特性，而所謂右旋，是因為結(jié)點變化有一個向右的動作。左旋操作則是右旋操作的逆過程 。但不論如何，上面兩顆樹的中序遍歷結(jié)果，，一定是一致的，也就是任何時候都滿足 二叉排序樹 的特性。

平衡二叉樹的插入操作

對平衡二叉樹的插入操作而言，其本質(zhì)上比二叉排序樹（BST）的插入操作多了一個平衡操作，解決了二叉排序樹插入操作可能出現(xiàn)的斜樹，不平衡問題。

我們以插入一個結(jié)點 為例進行說明平衡二叉樹插入操作的具體算法步驟。

1. 對結(jié)點 執(zhí)行標準的二叉排序樹的插入操作；
2. 從結(jié)點 開始，向上回溯，找到第一個不平衡的結(jié)點（即平衡因子不是 -1，0或1的結(jié)點） ； 為從結(jié)點 到結(jié)點 的路徑上， 的孩子結(jié)點（這里強調(diào)路徑,所以一定要注意奧?）； 是從結(jié)點 到結(jié)點 的路徑上， 的孫子結(jié)點 。
3. 然后對以 為根結(jié)點的子樹進行平衡操作，其中 x、y、z 可以的位置有一種情況，平衡操作也就處理以下四種情況：
• y 是 z 的左孩子，x 是 y 的左孩子 （Left Left ，LL )；
• y 是 z 的左孩子，x 是 y 的右孩子 （Left Right ，LR )；
• y 是 z 的右孩子，x 是 y 的右孩子 （Right Right ，RR )；
• y 是 z 的右孩子，x 是 y 的左孩子 （Right Right ，RL )；

在所有的四種情況下，我們只需要重新平衡以 z 為根的子樹，并且保證以 z 為根的子樹的高度（在適當旋轉(zhuǎn)之后）與 w 插入之前的高度相同，整顆樹就變得平衡了。

第一種情況：LL

第二種情況：LR

第三種情況：RR

第四種情況：RL

上面就是二叉排序樹在極端情況下出現(xiàn)的問題，現(xiàn)在我們以 右斜樹 的插入序列，一起進行一遍平衡二叉樹的插入操作。初始的插入序列為：

第一步：插入結(jié)點 1 ，顯然一顆空樹或者只包含一個結(jié)點的樹為平衡二叉樹，什么都不做。結(jié)點 1 的左右子樹都為空，則平衡因子等于 左子樹的深度0減去右子樹深度0 ，即為 0 。

第二步：插入結(jié)點 3 ，先執(zhí)行 BST的標準插入 ，3 的值比 1 大，插入 1 的右子樹，又因為 1 的右子樹為空，則直接將 3 作為 1 的右孩子插入。（由于二叉排序樹的插入操作之前已經(jīng)講的很清楚了，后面就不再像剛才啰嗦 ）。3 為葉子結(jié)點，平衡因子為 0 ；此時 1 的左子樹深度為0減去右子樹深度1，即平衡因子為 -1 ，整棵樹依舊平衡。

第三步：插入結(jié)點 4 ，先執(zhí)行 BST的標準插入 ，然后計算更新結(jié)點的平衡因子（圖中使用紅色字體表示），從插入結(jié)點 4 向上回溯，找到第一個不平衡的結(jié)點 1 (相當于算法描述中的 z ) 的平衡因子為 -2 ，并不滿足平衡二叉樹的特性，找到從結(jié)點 4 到結(jié)點 1 的路徑上結(jié)點 1 的孩子結(jié)點 3 ?(相當于算法描述中的 y )，孫子結(jié)點 4 （相當于算法描述中的 x )，這顯然就是我們上面的 RR 情況；

第四步：對結(jié)點 1 進行 左旋操作 。

第五步：插入結(jié)點 6 ，并更新平衡因子，發(fā)現(xiàn)此時為平衡二叉樹，什么都不做。

第六步：插入結(jié)點 7 ，并更新平衡因子，從結(jié)點 7 向上回溯，找到相應(yīng)的 z、y、x ，對應(yīng)于結(jié)點 4、6、7。

第七步：進行平衡操作，并更新結(jié)點的平衡因子：

第八步：插入結(jié)點 8 ，并更新平衡因子，從節(jié)點 8 向上回溯找到相應(yīng)的 x、y、z ，即結(jié)點 3、6，7 。

第九步：對結(jié)點 3 進行 左旋操作 。

第十步：插入結(jié)點 10 ，并更新結(jié)點的平衡因子，從節(jié)點 10 向上回溯找到第一個不平衡的結(jié)點 7 ，并找到對應(yīng)的孩子結(jié)點 8 和孫子結(jié)點 10 。

第十一步：對結(jié)點 7 進行左旋操作：

LL的情況

首先我們有如下約定：

現(xiàn)在我們用下圖進行說明：

上圖就一個平衡二叉樹，現(xiàn)在我們插入值為 4 的結(jié)點（進行標準的BST插入操作），從結(jié)點 4 向上回溯，找到相應(yīng)的 ?z、y、x ?，如下圖所示：

然后對結(jié)點 10 進行右旋操作：

LR的情況

同樣以下圖為例：

現(xiàn)在我們向該平衡二叉樹當中插入值為 7 的結(jié)點，從結(jié)點 7 向上回溯，找到相應(yīng)的 ?z、y、x ?，如下圖所示：

根據(jù) LR 的情況，先左旋 y (即圖中的結(jié)點 6 )：

然后右旋 z （即圖中的頂點 10 ）：

這樣我們就得到對應(yīng)的平衡二叉樹，可以對應(yīng)下圖再溫習一下 LR 的情況。

RL的情況

我們以下圖為例進行說明:

此時向平衡二叉樹當中插入結(jié)點 15 ，插入過程就是標準的二叉排序樹的過程，不再累述。并更新結(jié)點的平衡因子：

第一步：右旋結(jié)點 x (即圖中的結(jié)點 15 )

第二步：左旋結(jié)點 Z (即圖中的結(jié)點 14 )

整個過程和之前提到過的 RL 的演示圖一致，只不過對應(yīng)的 ?均為空而已，各位小禹禹可不能被忽悠奧，要靈活使用。

時間復(fù)雜度分析

因為 AVL 樹上的結(jié)點的左右子樹的深度之差都不超過 1，也就是取值只能是 -1，0，1 ，則 AVL 樹的深度和 是同數(shù)量級的（其中 n 為結(jié)點個數(shù)）。因此平衡二叉樹的平均查找長度和 也是同數(shù)量級的，二叉排序樹的插入和查找的時間復(fù)雜度即為 量級。

平衡二叉樹（AVL）插入操作的實現(xiàn)

在實現(xiàn)平衡二叉樹的插入操作時，我們采用二叉排序樹（BST）的插入操作的遞歸實現(xiàn)。在 BST 的遞歸實現(xiàn)中，插入結(jié)點之后，可以自插入結(jié)點向上回溯的方式逐一獲得指向祖先結(jié)點的指針（事實上你講遞歸的過程用棧來理解就更加清楚了，首先從根結(jié)點開始，進行判斷，一直到插入結(jié)點的位置，將從插入結(jié)點到根結(jié)點經(jīng)過的路徑壓棧，那么回溯的時候，從插入結(jié)點自然可以回溯到根結(jié)點）。因此，我們就不需要專門設(shè)置一個用于保存父結(jié)點的指針了。遞歸代碼本身向上回溯并訪問從根結(jié)點到插入結(jié)點的路徑上的所以結(jié)點的祖先。

1. 執(zhí)行標準的平衡二叉樹的插入操作；
2. 更新當前結(jié)點（從根結(jié)點到新插入結(jié)點的路徑上經(jīng)過的結(jié)點）的深度。
3. 獲取當前結(jié)點的平衡因子（左子樹的深度 - 右子樹的深度）。
4. 如果平衡因子大于 1 ，則當前結(jié)點是不平衡結(jié)點，且當前結(jié)點的子樹存在 LL 或 LR 的情況；檢查是否是 LL 的情況，將新插入結(jié)點的值與當結(jié)點的左孩子的值進行比較，如果小于則是 LL 的情況，否則是 LR 的情況。
5. 如果平衡因子小于 -1 ，則當前結(jié)點是不平衡結(jié)點，且當前結(jié)點的子樹存在 RR 或 RL 的情況；檢查是否是 RR 的情況，判斷新插入結(jié)點的值是否大于當前結(jié)點的右孩子的值，如果大于，則屬于 RR 的情況，否則為 RL 的情況。

平衡二叉樹插入操作代碼：

左旋與右旋操作： 小禹禹可以對照著下面的圖看代碼，就會特別清晰。

//RL的情況下，對以 y 為根的結(jié)點進行右旋操作。
struct?Node?*rightRotate(struct?Node?*y)?
{?
?//保存y的左孩子 x
?struct?Node?*x?=?y->left;?
?//保存x的右孩子 T2
?struct?Node?*T2?=?x->right;?

?//?有旋轉(zhuǎn)操作，將x的右孩子設(shè)置為y,將y的左孩子設(shè)置為T2?
?x->right?=?y;?
?y->left?=?T2;?

?//?更新結(jié)點結(jié)點x和結(jié)點y的深度
?y->height?=?max(height(y->left),?height(y->right))+1;?
?x->height?=?max(height(x->left),?height(x->right))+1;?

?//?返回新的結(jié)點x.
?return?x;?
}?

//?左旋以 x 為根結(jié)點的子樹。
struct?Node?*leftRotate(struct?Node?*x)?
{?
?//保存x的右孩子 y
?struct?Node?*y?=?x->right;?
?//保存y的左孩子T2
?struct?Node?*T2?=?y->left;?

?//?左旋操作，將y的左孩子設(shè)置為x,將x的右孩子設(shè)置為T2
?y->left?=?x;?
?x->right?=?T2;?

?//?更新結(jié)點x和結(jié)點y的深度。
?x->height?=?max(height(x->left),?height(x->right))+1;?
?y->height?=?max(height(y->left),?height(y->right))+1;?

?//?返回新的根結(jié)點y.?
?return?y;?
}?

計算平衡因子： 結(jié)點的左子樹深度減去右子樹深度。

int?getBalance(struct?Node?*N)?
{?
?if?(N?==?NULL)?
??return?0;?
?return?height(N->left)?-?height(N->right);?
}?

平衡二叉樹的插入操作

struct?Node*?insert(struct?Node*?node,?int?key)?
{?
?/*?1.執(zhí)行標準的二叉排序樹的插入操作?*/
?if?(node?==?NULL)?
??return(newNode(key));?

?if?(key?key)?
??node->left?=?insert(node->left,?key);?
?else?if?(key?>?node->key)?
??node->right?=?insert(node->right,?key);?
?else?//二叉排序樹中不允許等于的情況。
??return?node;?

?/*?2.?更新當前結(jié)點node的深度?*/
?node->height?=?1?+?max(height(node->left),?
??????height(node->right));?

?/*?3.?獲取當前結(jié)點的平衡因子，并判斷當前結(jié)點是否是平衡結(jié)點?*/
?int?balance?=?getBalance(node);?

?//?如果當前結(jié)點是不平衡結(jié)點，則分以下四種情況處理

?//?LL的情況，對當前不平衡結(jié)點（相當于z）進行右旋操作?
?if?(balance?>?1?&&?key?left->key)?
??return?rightRotate(node);?

?// RR的情況，對當前不平衡結(jié)點進行左旋操作。
?if?(balance?-1?&&?key?>?node->right->key)?
??return?leftRotate(node);?

?// LR的情況，對不平衡結(jié)點(結(jié)點z)的左孩子(結(jié)點y)進行左旋操作
?//，然后對當前結(jié)點進行右旋操作。
?if?(balance?>?1?&&?key?>?node->left->key)?
?{?
??node->left?=?leftRotate(node->left);?
??return?rightRotate(node);?
?}?

?// RL的情況，對不平衡結(jié)點(結(jié)點z)的右孩子(結(jié)點y)進行右旋操作
?//，然后對當前結(jié)點進行左旋操作。
?if?(balance?-1?&&?key?right->key)?
?{?
??node->right?=?rightRotate(node->right);?
??return?leftRotate(node);?
?}?

?/*?返回結(jié)點指針?*/
?return?node;?
}?

LeetCode題解

題目來源于 110. 平衡二叉樹 Balanced Binary Tree

題目描述

給定一個二叉樹，判斷它是否是高度平衡的二叉樹。

本題中，一棵高度平衡二叉樹定義為：

一個二叉樹每個節(jié)點 的左右兩個子樹的高度差的絕對值不超過1。

輸入輸出示例

示例一：

給定二叉樹 [3,9,20,null,null,15,7]

返回 true

示例二：

給定二叉樹 [1,2,2,3,3,null,null,4,4]

返回 false 。

題目解析

考慮一顆二叉樹是否高度平衡，我們需要檢查下面的這些條件：

一顆空樹必然是高度平衡的。一顆非空的樹 是高度平衡的，當且僅當滿足下面三個條件（遞歸定義）：

1. 樹 的左子樹是平衡的；
2. 樹 的右子樹是平衡的；
3. 左右子樹的高度之差不超過1；

根據(jù)上面對于高度平衡的定義，顯然示例一當中的樹是高度平衡的；示例二中的樹不是高度平衡的，因為結(jié)點1的左子樹與右子樹的深度之差為2，大于1。

方法一

檢查一顆二叉樹是不是高度平衡，則對二叉樹的結(jié)點檢查其左右子樹的高度之差是否超過 1，超過 1則返回false，否則返回true;

int?abs(int?x){
????if(x?0){
????????return?-x;
????}
????return?x;
}
int?max(int?x,?int?y){
????return?(x?>=?y)???x?:?y;
}
//計算node的高度
int?height(struct?TreeNode*?node){
????if(node?==?NULL)
????{
????????return?0;
????}
????return?1?+?max(height(node->left),?height(node->right));
}
//判斷二叉樹是否平衡
bool?isBalanced(struct?TreeNode*?root){
????int?lh;?//左子樹高度
????int?rh;?//右子樹高度
?
????//樹為空返回true;
????if(root?==?NULL)
????????return?1;
?//獲得左子樹深度
????lh?=?height(root->left);
????//獲得右子樹深度
????rh?=?height(root->right);
????//判斷左右子樹高度之差是否小于1，并且結(jié)點的左右子樹平衡，返回true;
????if(abs(lh?-?rh)?<=?1?&&?isBalanced(root->left)?&&?isBalanced(root->right)){
????????return?1;
????}
????return?0;
}

方法二（對方法一優(yōu)化）

但是上面的方法存在性能上的問題，當輸入是一顆斜樹的時候，其時間復(fù)雜度將變成 。問題在于我們判斷二叉樹是否平衡的函數(shù) isBalanced() 當中嵌套了一個計算樹的高度的函數(shù)height() ，這樣以來，當樹為一顆斜樹的時候，時間復(fù)雜度就會達到 。解決的辦法就是將這兩個函數(shù)合并，取消單獨調(diào)用的height（）函數(shù)，而是在遞歸進行判斷的時候計算樹的高度。

int?abs(int?x){
????if(x?0){
????????return?-x;
????}
????return?x;
}

bool?isBalancedUtil(struct?TreeNode*?root,?int*?height){
????int?lh;?//保存左子樹的高度
????int?rh;?//右子樹的高度

????int?l?=?0;?//左子樹是否平衡標志
????int?r?=?0;?//右子樹是否平衡標志

????if(root?==?NULL){
????????*height?=?0;
????????return?1;
????}
????//遞歸判斷左右子樹是否平衡
????l?=?isBalancedUtil(root->left,?&lh);
????r?=?isBalancedUtil(root->right,?&rh);

????//計算樹的高度，左右子樹高度較大者加1
????*height?=?((lh?>=?rh)???lh?:?rh)?+?1;
?
????//如果左右子樹高度之差大于等于2，返回false;
????if(abs(lh?-?rh)?>=?2){
????????return?0;
????}
????//否則返回左右子樹平衡標志的與
????return?l?&&?r;
}
bool?isBalanced(struct?TreeNode*?root){
????int?height?=?0;
????return?isBalancedUtil(root,&height);
}

溫馨提示，需要AVL樹實現(xiàn)代碼的小禹禹，后臺回復(fù) 「 AVL 」就可以獲得（包括Python、Java、C++ 和 C的實現(xiàn)）。