柚子快報激活碼778899分享：【數(shù)據(jù)結(jié)構(gòu)】平衡二叉樹

http://yzkb.51969.com/

導(dǎo)語

對于二叉搜索樹 而言，它的?增、 刪 、 改 、 查 ?的時間復(fù)雜度為?O()?~?O(n)?。原因是最壞情況下，二叉搜索樹會退化成?線性表 ?。換言之，樹的高度決定了它插入、刪除和查找的時間復(fù)雜度。 為了對上述缺點進一步優(yōu)化，設(shè)計了一種高度始終能夠接近?O()?的?樹形 ?的數(shù)據(jù)結(jié)構(gòu)，它既有鏈表的快速插入與刪除的特點，又有順序表快速查找的優(yōu)勢。它就是：平衡二叉樹 。

?一、平衡二叉樹基本概念

1、平衡二叉樹的定義

平衡二叉樹（AVL樹），是一種平衡(balanced)的二叉搜索樹(binary search tree, 簡稱為BST)。由兩位科學(xué)家在1962年發(fā)表的論文《An algorithm for the organization of information》當(dāng)中提出，作者是發(fā)明者G.M. Adelson-Velsky和E.M. Landis。它具有以下兩個性質(zhì)：

空樹是平衡二叉樹任意一個結(jié)點的key，比它的左孩子key大，比它的右孩子key小；任何一個結(jié)點的左子樹與右子樹都是平衡二叉樹，并且高度之差的絕對值不超過 1。

2、樹的高度

一棵樹的高度，是指從樹根結(jié)點到達最遠的葉子結(jié)點的路徑上經(jīng)過的結(jié)點數(shù)。所以，求樹的高度我們可以采用遞歸的方式。主要有以下三種情況：

1）空樹的樹高為 0；

2）葉子結(jié)點的樹高為 1；

3）其它結(jié)點的樹高，等于左右子樹樹高的大者加 1；

3、平衡因子

二叉樹上的結(jié)點的?左子樹高度?減去?右子樹高度?的值稱為 平衡因子，即 BF（Balance Factor）。 根據(jù)平衡二叉樹的定義，樹上所有結(jié)點的平衡因子只可能是 -1、0 和 1。即只要二叉樹上有一個結(jié)點的平衡因子的絕對值大于 1，則該二叉樹就是不平衡的。

二、平衡二叉樹存儲結(jié)構(gòu)

對于平衡二叉樹，首先是二叉搜索樹，所以會有 左右孩子指針 和 數(shù)據(jù)域，然后特殊之處是需要平衡因子，而平衡因子可以通過節(jié)點樹的高度來計算，所以需要加一個 高度。

struct TreeNode {

int val;

struct TreeNode* left;

struct TreeNode* right;

int height;

TreeNode(int x, int h = 1) :val(x), left(nullptr), right(nullptr), height(h){}

};

三、平衡二叉樹基本接口

1、獲取樹高

int AVLGetHeight(TreeNode* node)

{

if (node == nullptr) {

return 0;

}

return node->height;

}

獲取樹高期望做到?O(1)?的時間復(fù)雜度，height 字段是需要存儲在結(jié)點上的，并且每次樹的 插入、刪除 操作都需要更新這個值。

空結(jié)點的樹高為 0，其它結(jié)點的樹高可以直接通過獲取樹結(jié)點結(jié)構(gòu)體的成員變量height 字段快速獲取。

2、計算樹高

每次對樹進行插入、刪除操作，對樹的原結(jié)點高度會有影響，所以需要重新計算，更新這個值。

//計算樹高（結(jié)點增刪需要重新計算樹高）

void AVLCalcHeight(TreeNode* node) {

if (nullptr == node) {

return ;

}

node->height = 1 + std::max(AVLGetHeight(node->left), AVLGetHeight(node->right));

}

?3、獲取平衡因子

同理，每次對樹進行插入、刪除操作，對樹的原結(jié)點的平衡因子也會有影響，所以也需要重新計算這個值。

//獲取平衡因子

int AVLGetBalanceFactor(TreeNode* node) {

if (node == nullptr)

return 0;

return AVLGetHeight(node->left) - AVLGetHeight(node->right);

}

4、旋轉(zhuǎn)操作

每次對樹進行插入、刪除操作，可能會引起樹的平衡，此時就需要通過旋轉(zhuǎn)操作來使樹重新回到平衡狀態(tài)。

假設(shè)本來這棵樹是平衡的，在我們在插入一個結(jié)點以后，導(dǎo)致了這棵樹的不平衡，那么必然是這棵樹根結(jié)點的平衡因子從 +1 變成了 +2，或者從 -1 變成了 -2 。我們來分別討論這兩種情況。

實際上，總共有四種情況：

1）LL（往左子樹的左子樹插入一個結(jié)點），根結(jié)點的平衡因子 +2，左子樹根結(jié)點平衡因子 +1；

2）RR（往右子樹的右子樹插入一個結(jié)點），根結(jié)點的平衡因子 -2，右子樹根結(jié)點平衡因子 -1；

3）LR（往左子樹的右子樹插入一個結(jié)點），根結(jié)點的平衡因子 +2，左子樹根結(jié)點平衡因子 -1；

4）RL（往右子樹的左子樹插入一個結(jié)點），根結(jié)點的平衡因子 -2，右子樹根結(jié)點平衡因子 +1；

結(jié)論：+1 變成 +2 的情況發(fā)生在 LL 和 LR，即往當(dāng)前樹的左子樹插入一個結(jié)點的情況；-1 變成 -2 的情況發(fā)生在 RL 和 RR，即往當(dāng)前樹的右子樹插入一個結(jié)點的情況。

（1） LL

LL，即往左子樹的左子樹插入一個結(jié)點。這種情況下，如果樹出現(xiàn)了不平衡的情況，根結(jié)點的當(dāng)前平衡因子一定是 +2。

如上圖所示，在左子樹插入T5結(jié)點后，平衡二叉樹的平衡狀態(tài)被打破，要想回到平衡狀態(tài)需要對樹進行一個右旋操作。

如圖所示，以左子樹根結(jié)點T1作支點右旋后，重新達到平衡?？偣灿幸韵玛P(guān)系發(fā)生了變化：

（1）T1變成了新的樹根

（2）T和T1父子關(guān)系發(fā)生了交換

（3）T4的父節(jié)點由T1變?yōu)門

右旋源碼

//右旋

TreeNode* RRotate(TreeNode* T)

{

TreeNode* LNode = T->left;

T->left = LNode->right;

LNode->right = T;

AVLCalcHeight(T);

AVLCalcHeight(LNode);

return LNode;

}

經(jīng)過右旋后，只有T1和T的高度發(fā)生了變化，所以需要對它們重新計算高度。

LL型旋轉(zhuǎn)處理

// LL 型右旋處理

TreeNode* AVLTreeLL(TreeNode* T) {

return RRotate(T);

}

（2）RR

RR，即往右子樹的右子樹插入一個結(jié)點。這種情況下，如果樹出現(xiàn)了不平衡的情況，根結(jié)點的當(dāng)前平衡因子一定是 -2。

如上圖所示，在右子樹插入T5結(jié)點后，平衡二叉樹的平衡狀態(tài)被打破，要想回到平衡狀態(tài)需要對樹進行一個左旋操作。

如圖所示，以右子樹根結(jié)點T2作支點左旋后，重新達到平衡?？偣灿幸韵玛P(guān)系發(fā)生了變化：

（1）T2變成了新的樹根

（2）T和T2父子關(guān)系發(fā)生了交換

（3）T3的父節(jié)點由T2變?yōu)門

左旋源碼

//左旋

TreeNode* LRotate(TreeNode* T)

{

TreeNode* RNode = T->right;

T->right = RNode->left;

RNode->left = T;

AVLCalcHeight(T);

AVLCalcHeight(RNode);

return RNode;

}

RR型處理源碼

//RR型左旋處理

TreeNode* AVLTreeRR(TreeNode* T) {

return LRotate(T);

}

（3）LR

LR，即往左子樹的右子樹插入一個結(jié)點。這種情況下，如果樹出現(xiàn)了不平衡的情況的話，根結(jié)點的當(dāng)前平衡因子一定是 +2。

假設(shè)以左子樹的右子樹T4結(jié)點為支點，對左子樹進行一次左旋操作，得到如下圖所示：

可以看到，經(jīng)過一次左旋得到新樹，形狀和LL型一致，所以接下來再按照型LL處理，再右旋一次即可達到平衡狀態(tài)

所以對于LR型的處理主要有兩步：

（1）對樹T的左子樹進行左旋

（2）對樹T進行右旋

LR型處理源碼

//LR型左旋+右旋處理

TreeNode* AVLTreeLR(TreeNode* T) {

T->left = LRotate(T->left); //左旋處理并修改T的左指針指向

return RRotate(T); //對T進行右旋處理

}

?（4）RL

RL，即往右子樹的左子樹插入一個結(jié)點。這種情況下，如果樹出現(xiàn)了不平衡的情況的話，根結(jié)點的當(dāng)前平衡因子一定是 -2。

假設(shè)以右的左子樹T4結(jié)點為支點，對右子樹進行一次右旋操作，得到如下圖所示：

可以看到，經(jīng)過一次右旋得到新樹，形狀和RR型一致，所以接下來再按照型RR型處理，再左旋一次即可達到平衡狀態(tài)

所以對于RL型的處理主要有兩步：

（1）對樹T的右子樹進行右旋

（2）對樹T進行左旋

RL型處理源碼

//RL型右旋+左旋處理

TreeNode* AVLTreeRL(TreeNode* T) {

T->right = RRotate(T->right); // 右子樹進行右旋處理并修改T的右指針指向

return LRotate(T); // 對T樹進行左旋處理

}

四、平衡二叉樹基本操作

1、查找

（1）查找定值

對于要查找的數(shù)據(jù) data，從根結(jié)點出發(fā)，每次選擇左子樹或者右子樹進行查找，?n?個結(jié)點的樹高最多為，所以查找的時間復(fù)雜度為?O()?，總共四種情況依次進行判斷：

1）若為空樹，直接返回 false；

2） data 小于?樹根結(jié)點的數(shù)據(jù)域，說明 data 對應(yīng)的結(jié)點不在根結(jié)點，也不在右子樹上，則遞歸返回左子樹的?查找?結(jié)果；

3） data 大于?樹根結(jié)點的數(shù)據(jù)域，說明 data 對應(yīng)的結(jié)點不在根結(jié)點，也不在左子樹上，則遞歸返回右子樹的?查找?結(jié)果；

4） data 等于?樹根結(jié)點的數(shù)據(jù)域，則直接返回 true ；

bool AVLFind(TreeNode* T, int data) {

if (T == nullptr) {

return false; // 空樹

}

if (data < T->val) {

return AVLFind(T->left, data); // data

}

else if (data > T->val) {

return AVLFind(T->right, data); // data>val，遞歸查找右子樹

}

return true; // data=val

}

（2）查找最小值結(jié)點

迭代找到樹的最左結(jié)點即可。

//找最小值結(jié)點

TreeNode* AVLGetMin(TreeNode* T) {

while (T && T->left)

T = T->left;

return T;

}

（3）查找最大值

迭代找到樹的最右結(jié)點即可。

//找最大值結(jié)點

TreeNode* AVLGetMax(TreeNode* T) {

while (T && T->right)

T = T->right;

return T;

}

2、平衡

每次當(dāng)我們對樹的結(jié)點進行插入或者刪除的時候，都有可能打破樹的平衡性，這時候就需要一些旋轉(zhuǎn)操作來使樹重新恢復(fù)平衡。 究竟是進行左旋，右旋，還是雙旋，就要通過平衡因子來判斷了。

令根結(jié)點為?T?，左子樹的根結(jié)點為?L?，右子樹的根結(jié)點為?R?，?代表根結(jié)點的平衡因子，代表左子樹根的平衡因子，?代表右子樹根的平衡因子?？偣卜譃橐韵滤姆N情況：

1）???> 1?，??> 0?，則為 LL 型，需要進行一次右旋；

2）???> 1?，??≤ 0?，則為 LR 型，需要進行一次雙旋；

3）???< ?1?，??> 0?，則為 RL 型，需要進行一次雙旋；

4）???< ?1?，??≤ 0?，則為 RR 型，需要進行一次左旋

?平衡源碼

//平衡選轉(zhuǎn)

TreeNode* AVLBalance(TreeNode* T) {

int bf = AVLGetBalanceFactor(T);

if (bf > 1) {

if (AVLGetBalanceFactor(T->left) > 0)

T = AVLTreeLL(T); // LL型，右旋一次

else

T = AVLTreeLR(T); // LR型，左旋+右旋

}

if (bf < -1) {

if (AVLGetBalanceFactor(T->right) > 0)

T = AVLTreeRL(T); // RL型，右旋+左旋

else

T = AVLTreeRR(T); // RR型，左旋一次

}

AVLCalcHeight(T); // 重新計算根結(jié)點高度，因為之前旋轉(zhuǎn)時并未完成相關(guān)操作

return T;

}

3、插入

對于要插入的數(shù)據(jù) data?，從根結(jié)點出發(fā)，分情況依次判斷：

1）若為空樹，則創(chuàng)建一個值為 data?的結(jié)點并且返回；

2） data?的值 等于?樹根結(jié)點的值，無須執(zhí)行插入，直接返回根結(jié)點；

3） data?的值 小于?樹根結(jié)點的值，那么插入位置一定在?左子樹，遞歸執(zhí)行插入左子樹的過程，并且返回插入結(jié)果作為新的左子樹；

4） data?的值 大于?樹根結(jié)點的值，那么插入位置一定在?右子樹，遞歸執(zhí)行插入右子樹的過程，并且返回插入結(jié)果作為新的右子樹；

最后，在3或4情況執(zhí)行完成后，需要對樹執(zhí)行?平衡?操作。

插入源碼

TreeNode* AVLInsert(TreeNode* T, int data) {

if (T == nullptr) {

T = new TreeNode(data); // 空樹，創(chuàng)建val=data的結(jié)點

return T;

}

if (data == T->val) {

return T; // data已經(jīng)存在

}

else if (data < T->val) {

T->left = AVLInsert(T->left, data); // 遞歸查找左子樹適合位置，插入

}

else {

T->right = AVLInsert(T->right, data); // 遞歸查找右子樹適合位置，插入

}

return AVLBalance(T); // 重新平衡

}

4、刪除

（1）刪除根結(jié)點

對一棵平衡二叉樹，刪除它的根結(jié)點，需要保證它還是一棵二叉平衡樹，則有如下四種情況：

1）空樹，無須執(zhí)行刪除，直接返回空；

2）只有左子樹時，將根結(jié)點空間釋放后，返回左子樹；

3）只有右子樹時，將根結(jié)點空間釋放后，返回右子樹；

4）當(dāng)左右子樹都有時，根據(jù)左右子樹的平衡性分情況討論：如果左子樹更高，則從左子樹選擇最大值替換根結(jié)點，并且遞歸刪除左子樹對應(yīng)結(jié)點；右子樹更高，則從右子樹選擇最小值替換根結(jié)點，并且遞歸刪除右子樹對應(yīng)結(jié)點；

5）最后，重新計算所有樹高，并且返回根結(jié)點；

//刪除根結(jié)點

TreeNode* AVLRemoveRoot(TreeNode* T) {

TreeNode* delNode = nullptr;

TreeNode* retNode = nullptr;

if (T == nullptr) {

return nullptr; // 空樹，直接返回

}

if (T->right == nullptr) { // 只有左子樹（包含單節(jié)點情況），釋放根結(jié)點空間后，返回左子樹根結(jié)點

retNode = T->left;

delete T;

}

else if (T->left == nullptr) { // 只有右子樹，釋放根結(jié)點空間后，返回右子樹根結(jié)點

retNode = T->right;

delete T;

}

else { // 左右子樹都存在

if (AVLGetHeight(T->left) > AVLGetHeight(T->right)) { // 左子樹高于右子樹

retNode = T;

//獲取左子樹最大值結(jié)點,并以它的值作為根結(jié)點的新值

TreeNode* cur = T->left;

TreeNode* pcur = T;

while (cur->right)

{

pcur = cur;

cur = cur->right;

}

delNode = cur;

retNode->val = cur->val;

if (pcur->right == cur) {//左子樹的最大值在左子樹的右子樹上

pcur->right = cur->left;

}

else {//左子樹的最大值為左子樹的根

pcur->left = cur->left;

}

delete delNode;

retNode = AVLBalance(T);

AVLCalcAllHeight(retNode);

}

else { // 右子樹高于左子樹

retNode = T;

//獲取右子樹最小值結(jié)點,并以它的值作為根結(jié)點的新值

TreeNode* cur = T->right;

TreeNode* pcur = T;

while (cur->left)

{

pcur = cur;

cur = cur->left;

}

delNode = cur;

retNode->val = cur->val;

if (pcur->left == cur) {//右子樹的最小值在右子樹的左子樹上

pcur->left = cur->right;

}

else {//右子樹的最小值為右子樹的根

pcur->right = cur->right;

}

delete delNode;

retNode = AVLBalance(T);

AVLCalcAllHeight(retNode);

}

}

return retNode;

}

（2）刪除指定結(jié)點

刪除值為 data 的結(jié)點的過程，從根結(jié)點出發(fā)，總共四種情況依次判斷：

1）空樹，不存在結(jié)點，直接返回空?；

2） data 的值 等于?樹根結(jié)點的值，則調(diào)用?刪除根結(jié)點?的接口，這個過程下文會詳細介紹；

3） data 的值 小于?樹根結(jié)點的值，則需要刪除的結(jié)點一定不在右子樹上，遞歸調(diào)用刪除左子樹的對應(yīng)結(jié)點，并且將刪除結(jié)點返回的子樹作為新的左子樹；

4） data 的值 大于?樹根結(jié)點的值，則需要刪除的結(jié)點一定不在左子樹上，遞歸調(diào)用刪除右子樹的對應(yīng)結(jié)點，并且將刪除結(jié)點返回的子樹作為新的右子樹；

5）最后，對于 3） 和 4） 這兩步，需要對樹執(zhí)行?平衡?操作。

TreeNode* AVLRemove(TreeNode* root,int val)

{

if (nullptr == root) {

return nullptr;

}

if (val == root->val) {

return AVLRemoveRoot(root);

}

else if (val < root->val) {

root->left = AVLRemove(root->left, val);

}

else if (val > root->val) {

root->right = AVLRemove(root->right, val);

}

root = AVLBalance(root);

AVLCalcAllHeight(root);

return root;

}

五、平衡二叉樹的缺點

由于AVL樹必須保證左右子樹平衡，Max(最大樹高-最小樹高) <= 1，所以在插入的時候很容易出現(xiàn)不平衡的情況，一旦這樣，就需要進行旋轉(zhuǎn)以求達到平衡。

正是由于這種嚴格的平衡條件，導(dǎo)致AVL需要花大量時間在調(diào)整上，故AVL樹一般使用場景在于查詢場景， 而不是?增加、刪除頻繁的場景。

柚子快報激活碼778899分享：【數(shù)據(jù)結(jié)構(gòu)】平衡二叉樹

http://yzkb.51969.com/

精彩文章