一文讀懂平衡二叉樹

作者 | 宋廣澤

出品 | CSDN(ID：CSDNnews)

平衡二叉樹，又稱AVL樹，指的是左子樹上的所有節點的值都比根節點的值小，而右子樹上的所有節點的值都比根節點的值大，且左子樹與右子樹的高度差最大為1。因此，平衡二叉樹滿足所有二叉排序（搜索）樹的性質。至於AVL，則是取自兩個發明平衡二叉樹的科學家的名字：G. M. Adelson-Velsky和E. M. Landis。

二叉搜索樹

平衡二叉樹是在二叉排序樹的基礎上發展而來的，那為什麼要引入二叉搜索樹呢？

所謂二叉搜索樹（Binary Search Tree），又叫二叉排序樹，簡單而言就是左子樹上所有節點的值均小於根節點的值，而右子樹上所有結點的值均大於根節點的值，左小右大，並不是亂序，因此得名二叉排序樹。

一個新事物不能憑空產生，那二叉搜索樹又有什麼用呢？

有了二叉搜索樹，當你要查找一個值，就不需要遍歷整個序列或者說遍歷整棵樹了，可以根據當前遍歷到的結點的值來確定搜索方向，這就好比你要去日本，假設你沒有見過世界地圖，你不知道該往哪個方向走，只能滿地球找一遍才能保證一定能夠到達日本；而如果你見過世界地圖，你知道日本在中國的東邊，你就不會往西走、往南走、往北走。這種思維在

如下圖所示的二叉搜索樹：

要想查找到8，則是先到達根節點，其值為5，8比5大因此繼續往右子樹上找，到達9，8比9小因此往左子樹上找，最終找到8；

要想查找4，則是先到達根節點其值為5，4比5小因此往左子樹上找，到達1，4比1大因此往右子樹上找，到達3，4比3大因此往右子樹上找，而值為3的節點的右子樹是空的，因此該搜索二叉樹中不存在值為4的節點。

有了二叉排序樹就可以使插入、搜索效率大大提高了，為什麼還要引入平衡二叉樹？

二叉搜索樹的結構與值的插入順序有關，同一組數，若其元素的插入順序不同，二叉搜索樹的結構是千差萬別的。舉個例子，給出一組數[1,3,5,8,9,13]。

若按照[5,1,3,9,13,8]這樣的順序插入，其流程是這樣的：

若按照[1,3,5,8,9,13]這樣的順序插入，其流程是這樣的：

如果在上面的二叉搜索樹中查找13，是要將所有節點都遍歷一遍的，時間複雜度就變成了O(n)，幾乎就是一個鏈表。

細心的朋友可能已經發現，插入的序列越接近有序，生成的二叉搜索樹就越像一個鏈表。

為了避免二叉搜索樹變成“鏈表”，我們引入了平衡二叉樹，即讓樹的結構看起來儘量“均勻”，左右子樹的節點數儘量一樣多。

生成平衡二叉樹

那給定插入序列，如何生成一棵平衡二叉樹呢？

先按照生成二叉搜索樹的方法構造二叉樹，直至二叉樹變得不平衡，即出現這樣的節點：左子樹與右子樹的高度差大於1。至於如何調整，要看插入的導致二叉樹不平衡的節點的位置。主要有四種調整方式：LL（左旋）、RR（右旋）、LR（先左旋再右旋）、RL（先右旋再左旋）。

struct node
{
//值
int val;
//左孩子
node *left;
//右孩子
node *right;
};
求樹的高度的函數：
int depth(node *root)
{
if(root==)
{
return 0;
}
int dep1=depth(root->left);
int dep2=depth(root->right);
return (dep1>dep2?dep1:dep2)+1;
}

代碼解析：二叉樹的高度取決於高度大的子樹，為高度大的子樹的高度+1。空樹的高度為0。

所謂LL（左旋）就是向左旋轉一次，下圖所示為最簡潔的左旋（插入3導致值為1的節點不平衡）：

然而更多時候根節點並不是只有一個子樹，下圖為複雜的LL（左旋，插入13導致值為4的節點不平衡）：

紅色節點為插入後不平衡的節點，黃色部分為需要改變父節點的分支，左旋後，原紅色節點的右孩子節點變成了根節點，紅色節點變成了它的左孩子，而它原本的左孩子（黃色部分）不能丟，而此時紅色節點的右孩子是空的，於是就把黃色部分放到了紅色節點的右孩子的位置上。調整後該二叉樹還是一棵二叉排序（搜索）樹，因為黃色部分的值大於原來的根節點的值，而小於後來的根節點的值，調整後，黃色部分還是位於原來的根節點（紅色節點）和後來的根節點之間。

LL（左旋）代碼如下：

node *LeftRotate(node *root)
{
//左旋
node *temp=root->right;
root->right=temp->left;
temp->left=root;
return temp;
}

代碼解析：返回的是左旋後的根節點，左旋後的根節點是原來根節點的右孩子，左旋後的根節點的左孩子需要嫁接到原來根節點的右孩子上，原來的根節點嫁接到左旋後根節點的左孩子上。temp對應上圖中值為8的節點，root對應上圖中值為4的節點。

所謂RR（右旋）就是向右旋轉一次，下圖所示為最簡潔的右旋（插入1導致值為3的節點不平衡）：

然而更多時候根節點並不是只有一個子樹，下圖為複雜的RR（右旋，插入1導致值為9的節點不平衡）：

紅色節點為插入後不平衡的節點，黃色部分為需要改變父節點的分支，右旋後，原紅色節點的左孩子節點變成了根節點，紅色節點變成了它的右孩子，而它原本的右孩子（黃色部分）不能丟，而此時紅色節點的左孩子是空的，於是就把黃色部分放到了紅色節點的左孩子的位置上。調整後該二叉樹還是一棵二叉排序（搜索）樹，因為黃色部分的值小於原來的根節點的值，而大於後來的根節點的值，調整後，黃色部分還是位於後來的根節點和原來的根節點（紅色節點）之間。

RR（右旋）代碼如下：

node *RightRotate(node *root)
{
//右旋
node *temp=root->left;
root->left=temp->right;
temp->right=root;
return temp;
}

代碼解析：返回的是右旋後的根節點，右旋後的根節點是原來根節點的左孩子，右旋後的根節點的右孩子需要嫁接到原來根節點的左孩子上，原來的根節點嫁接到右旋後根節點的右孩子上。temp對應上圖中值為5的節點，root對應上圖中值為9的節點。

所謂LR（先左旋再右旋）就是先將左子樹左旋，再整體右旋，下圖為最簡潔的LR旋轉（插入2導致值為3的節點不平衡）：

然而更多時候根節點並不是只有一個子樹，下圖為複雜的LR旋轉（插入8導致值為9的節點不平衡）：

先將紅色節點的左子樹左旋，紅色節點的左子樹的根原本是值為4的節點，左旋後變為值為6的節點，原來的根節點變成了左旋後根節點的左孩子，左旋後根節點原本的左孩子（藍色節點）變成了原來的根節點的右孩子；再整體右旋，原來的根節點（紅色節點）變成了右旋後的根節點的右孩子，右旋後的根節點原本的右孩子（黃色節點）變成了原來的根節點（紅色節點）的左孩子。旋轉完成後，仍然是一棵二叉排序（搜索）樹。

LR旋轉代碼如下：

node *LeftRightRotate(node *root)
{
//先對root的左子樹左旋再對root右旋
root->left=LeftRotate(root->left);
return RightRotate(root);
}

代碼解析：返回的是LR旋轉後的根節點，先對根節點的左子樹左旋，再整體右旋。root對應上圖中值為9的節點。

所謂RL（先右旋再左旋）就是先將右子樹右旋，再整體左旋，下圖為最簡潔的RL旋轉（插入2導致值為1的節點不平衡）：

然而更多時候根節點並不是只有一個子樹，下圖為複雜的RL旋轉（插入8導致值為4的節點不平衡）：

先將紅色節點的右子樹右旋，紅色節點的右子樹的根原本是值為9的節點，右旋後變為值為6的節點，原來的根節點變成了右旋後根節點的右孩子，右旋後根節點原本的右孩子（藍色節點）變成了原來的根節點的左孩子；再整體左旋，原來的根節點（紅色節點）變成了左旋後的根節點的左孩子，左旋後的根節點原本的左孩子（黃色節點）變成了原來的根節點（紅色節點）的右孩子。旋轉完成後，仍然是一棵二叉排序（

RL旋轉代碼如下：

node *RightLeftRotate(node *root)
{
//先對root的右子樹右旋再對root左旋
root->right=RightRotate(root->right);
return LeftRotate(root);
}

代碼解析：返回的是RL旋轉後的根節點，先對根節點的右子樹右旋，再整體左旋。root對應上圖中值為4的節點。

構造平衡二叉樹是一個邊插入邊調整的過程，插入一個看看是否造成了不平衡，造成了不平衡就立即調整。代碼如下：

node *Insert(node *root,int v)
{
if(root==)
{
root=new node;
root->val=v; 
root->left=;
root->right=;
}
else
{
if(v<root->val)/<root->
{
//插到左子樹上
root->left=Insert(root->left,v);
if(depth(root->left)-depth(root->right)>=2)
{
//左邊高右邊低
if(v<root->left->val)/<root->
{
//右旋
root=RightRotate(root);
}
else
{
//先對其左子樹左旋再右旋
root=LeftRightRotate(root);
}
}
} 
else
{
//插到右子樹上
root->right=Insert(root->right,v);
if(depth(root->right)-depth(root->left)>=2)
{
if(v>root->right->val)
{
//左旋
root=LeftRotate(root);
}
else
{
//先對其右子樹右旋再左旋
root=RightLeftRotate(root);
}
}
}
}
return root;
}

代碼解析：

出現不平衡時到底是執行LL、RR、LR、RL中的哪一種旋轉，取決於插入的位置。可以根據值的大小關係來判斷插入的位置。插入到不平衡節點的右子樹的右子樹上，自然是要執行LL旋轉；插入到不平衡節點的左子樹的左子樹上，自然是要執行RR旋轉；插入到不平衡節點的左子樹的右子樹上，自然是要執行LR旋轉；插入到不平衡節點的右子樹的左子樹上，自然是要執行RL旋轉。

向一棵平衡二叉樹tree中插入值temp的用法是這樣的：

tree=Insert(tree,temp);

最後給大家推薦一道經典面試算法題——判斷一棵樹是不是平衡二叉樹：https://leetcode-cn.com/problems/balanced-binary-tree/

給大家分享以下我的代碼：

/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left, right {}
* };
*/
class Solution {
public:
int depth(TreeNode *root)
{
if(root==)
{ 
return 0;
}
int dep1=depth(root->left);
int dep2=depth(root->right);
return (dep1>dep2?dep1:dep2)+1;
}
bool isBalanced(TreeNode* root) {
if(root==)
{
return true;
}
int dep1=depth(root->left);
int dep2=depth(root->right);
if(abs(dep1-dep2)>1)
{
return false;
}
else
{
return isBalanced(root->left)&&isBalanced(root->right);
}
} 
};

代碼解析：遞歸進行判斷就好啦，先判斷以下左子樹是不是平衡二叉樹，再判斷一下右子樹是不是平衡二叉樹，兩個子樹有一個不是平衡二叉樹則該樹就不是平衡的。空樹一定是平衡的。

在這金九銀十的Offer收割季，衷心祝願大家都收到想要的Offer，去想去的公司，當上CTO，迎娶白富美。

作者：宋廣澤，青島某普通一本大學計算機專業在校生，本科在讀，學生開發者。喜歡用C/C++編寫有意思的程序，解決實際問題。

【END】

閱讀更多 CSDN 的文章

關鍵字: 技術 二叉樹 CSDN