AVL平衡二叉查找樹
- 2019 年 10 月 17 日
- 筆記
二叉排序樹：
定義
二叉排序樹，又叫二叉查找樹，它或者是一棵空樹；或者是具有以下性質的二叉樹： 1. 若它的左子樹不空，則左子樹上所有節點的值均小於它的根節點的值； 2. 若它的右子樹不空，則右子樹上所有節點的值均大於它的根節點的值； 3. 它的左右子樹也分別為二叉排序樹。 比如下圖就是一棵普通的二叉排序樹： 
如果按照中序遍歷的順序，一棵二叉排序樹的輸出結果就剛好是按照從小到大的順序輸出的，可以運用於二分算法。先對其數據結構進行定義：
typedef struct Binary_Tree_node { int data; //數據域 struct Binary_Tree_node* lchild, * rchild; //左右孩子結點 }Binode, * BiTree;然後是插入操作：
//假設沒有相等的data,這裡我們不考慮相等的數據 //插入結點 void Insert_Binary_Tree(BiTree& bst ,int t) //bst是根節點 { if (bst == NULL) //空樹或者遞歸到了葉結點 { BiTree newp = new Binode; newp->data = t; newp->lchild = NULL; newp->rchild = NULL; bst = newp; } else { if (t > bst->data) //比本結點大，則插入其右孩子結點，小就插入左孩子結點 Insert_Binary_Tree(bst->rchild, t); else Insert_Binary_Tree(bst->lchild, t); } } 創建一棵樹：
//創建一棵二叉排序樹 BiTree Create_Binary_Tree() { BiTree bst = NULL; int t; cin >> t; while (t != ENDKEY) //只要輸入不等於-1，就一直往樹里插入元素 { Insert_Binary_Tree(bst, t); cin >> t; } return bst; }刪除操作：刪除操作比較複雜，本篇博客主要是記錄AVL，所以此處不做贅述
BiTree Delete_Binary_Tree(BiTree bst, int t) { Binode* newp, * f, * s, * q; newp = bst; f = NULL; while (newp) { if (newp->data == t) break; f = newp; if (t > newp->data) newp = newp->rchild; else newp = newp->lchild; } if (newp == NULL) return bst; if (newp->lchild == NULL) { if (f == NULL) bst = bst->rchild; else if (f->lchild == newp) f->lchild = newp->rchild; else f->rchild = newp->rchild; delete[]newp; } else if (newp->rchild == NULL) { if (f == NULL) bst = bst->lchild; else if (f->lchild == newp) f->lchild = newp->lchild; else f->rchild = newp->lchild; delete[]newp; } else { q = newp; s = newp->lchild; while (s->rchild) { q = s; s = s->rchild; } if (q == newp) q->lchild = s->lchild; else q->rchild = s->lchild; newp->data = s->data; delete[]s; } return bst; }搜索二叉樹：
//搜索二叉樹,根據輸入的數據搜索二叉樹，返回這個數據的結點 BiTree Search_Binary_Tree(BiTree bst, int t) { if (bst == NULL) return NULL; if (bst->data == t) return bst; else if (t > bst->data) return Search_Binary_Tree(bst->rchild, t); else return Search_Binary_Tree(bst->lchild, t); }平衡二叉排序樹：
可是當一棵二叉排序樹的某個節點的一枝相比於另一枝太長，搜索的時間複雜度就會變成O(n)，而為了提高效率，提出了AVL樹，即平衡二叉排序樹。 例如下圖就是一棵不平衡的二叉樹：
像這樣如果要搜索0元素就會變得和線性表的時間複雜度一樣。 AVL樹是一種比查找二叉樹還特別的樹，這種樹就可以幫助我們解決二叉查找樹剛才的那種所有節點都傾向一邊的缺點的。具有如下特性：
1、具有二叉查找樹的全部特性。
2、每個節點的左子樹和右子樹的高度差至多等於1。
例如：圖一就是一顆AVL樹了，而圖二則不是(節點右邊標的是這個節點的高度)。
按照這種規則進行建立二叉樹，可以保證這棵二叉樹始終是左右相對平衡的，可以保證搜索的時間複雜度達到O(log n)，提高了效率。
針對樹的失衡有四種情況，我們總結如下：
1、左左型：做右旋
2、右右型：做左旋
3、左右型：先左旋，再右旋
4、右左型：先右旋，再左旋
下面一個一個寫，對於實現每個旋轉的函數可以作為私有的對內接口（C++），不對外開放使用
1、左左型：做右旋：
像下面這種：
我們做如下右旋操作：
即順時針旋轉結點，使雙親結點被自己的左孩子替代，然後自己變成左孩子結點的右孩子結點
代碼實現：
//左左型單旋轉 void Lleft(BiTree &bst) //bst為不平衡的結點 { BiTree lch = bst->lchild; //保存不平衡結點的左孩子結點 bst->lchild = lch->rchild; lch->rchild = bst; bst = lch; }2、右右型：做左旋：
像下面這種：
逆時針旋轉結點，使自己被自己的右孩子替代，然後自己變成右孩子的左孩子結點
代碼實現：
//右右型單旋轉 void Rright(BiTree &bst) //bst為不平衡的結點 { BiTree rch = bst->rchild; //保存不平衡結點的右孩子結點 bst->rchild = rch->lchild; rch->lchild = bst; bst = rch; }3、左右型：先左旋，再右旋：
像下面這種：
先對其左旋將其變成左左型，再右旋讓其平衡
代碼實現：
//左右型雙旋轉 void Lright(BiTree &bst) { //先做左旋，將其變成左左型 BiTree lch = bst->lchild; BiTree lrch = bst->lchild->rchild; bst->lchild = lrch; bst->lchild->lchild = lch; bst->lchild->lchild->rchild = NULL; //可能存在bug todo,目前來看沒有哈哈哈 Lleft(bst); //再將其右旋 }4、右左型：先右旋，再左旋：
老規矩，先貼圖：
代碼實現：
//右左型雙旋轉 void Rleft(BiTree &bst) { //先做右旋，將其變成右右型 BiTree rch = bst->rchild; BiTree rlch = bst->rchild->lchild; bst->rchild = rlch; bst->rchild->rchild = rch; bst->rchild->rchild->lchild = NULL; Rright(bst); //再右旋 }實現重點來了
我們每插入一個結點元素都要保證整棵樹的每一個結點是平衡的，就要在插入這個結點後，從這個插入的結點往上逐個雙親結點去檢查，看是否破壞了樹的平衡，如果破壞了則對其進行左右旋轉操作，保證其平衡性，直到樹的根節點。
因為樹的遞歸性，在插入的時候是遞歸插入，
按照棧的順序，遞歸的過程中第一次遞歸的函數先入棧，以此類推，然後直到到達結束條件，前面的才依次出棧，
所以可以在插入函數最後面使用檢查每個結點的函數，出棧過程中，就可以沿着新插入結點一路回退檢查每個雙親結點了。
注意最後一行
代碼實現：
//插入結點 void Insert_Binary_Tree(BiTree& bst ,int t) //bst是根節點 { if (bst == NULL) //空樹或者葉結點 { BiTree newp = new Binode; newp->data = t; newp->lchild = NULL; newp->rchild = NULL; bst = newp; } else { if (t > bst->data) Insert_Binary_Tree(bst->rchild, t); else Insert_Binary_Tree(bst->lchild, t); } //在最後檢查這個結點，在遞歸的時候就可以將遞歸過程中從根節點往下的所有結點都檢查了，按照出棧順序，可以保證都是在插入後才依次向上檢查的。 Check_Binary_Tree(bst); }要實現這一功能就必須有一個檢查是否平衡的依據———就是每個結點的左右子樹的深度。這個函數是作為私有的對內接口。
計算深度的實現：
//一個結點的深度 int Binary_Tree_height(BiTree bst) //bst為要計算的結點 { if (bst == NULL) return 0; int l = Binary_Tree_height(bst->lchild); int r = Binary_Tree_height(bst->rchild); return max(l, r) + 1; }然後是一個檢查這個結點是否平衡的函數，對外：
檢查平衡函數：
//如果出現不平衡的情況就旋轉 void Check_Binary_Tree(BiTree &bst) //bst為要檢查的結點 { if (bst == NULL) return; if (Binary_Tree_height(bst->lchild) - Binary_Tree_height(bst->rchild) > 1) { if (Binary_Tree_height(bst->lchild->lchild) > Binary_Tree_height(bst->lchild->rchild)) Lleft(bst); else Lright(bst); } if (Binary_Tree_height(bst->rchild) - Binary_Tree_height(bst->lchild) > 1) { if (Binary_Tree_height(bst->rchild->rchild) > Binary_Tree_height(bst->rchild->lchild)) Rright(bst); else Rleft(bst); } }最後，對代碼進行一下匯總：
AVL.h文件#pragma once #include<iostream> constexpr auto ENDKEY = -1; template<typename T1, typename T2> constexpr auto max(T1 x, T2 y) { return x>y?x:y; } using namespace std; typedef struct Binary_Tree_node { int data; //數據域 struct Binary_Tree_node* lchild, * rchild; //左右孩子結點 }Binode, * BiTree; //訪問二叉樹 void visit(int c, int level) { printf("%d位於第%d層n", c, level); } //中序遍歷 void Midorder_Traverse(BiTree T, int level) { if (T) { Midorder_Traverse(T->lchild, level + 1); visit(T->data, level); Midorder_Traverse(T->rchild, level + 1); } } //一個結點的深度 int Binary_Tree_height(BiTree bst) { if (bst == NULL) return 0; int l = Binary_Tree_height(bst->lchild); int r = Binary_Tree_height(bst->rchild); return max(l, r) + 1; } //遍歷整棵樹，如果出現不平衡的情況就旋轉 //左左型單旋轉 void Lleft(BiTree &bst) { BiTree lch = bst->lchild; //保存不平衡結點的左孩子結點 bst->lchild = lch->rchild; lch->rchild = bst; bst = lch; } //右右型單旋轉 void Rright(BiTree &bst) { BiTree rch = bst->rchild; //保存不平衡結點的右孩子結點 bst->rchild = rch->lchild; rch->lchild = bst; bst = rch; } //左右型雙旋轉 void Lright(BiTree &bst) { //先做左旋，將其變成左左型 BiTree lch = bst->lchild; BiTree lrch = bst->lchild->rchild; bst->lchild = lrch; bst->lchild->lchild = lch; bst->lchild->lchild->rchild = NULL; //可能存在bug todo Lleft(bst); } //右左型雙旋轉 void Rleft(BiTree &bst) { //先做右旋，將其變成右右型 BiTree rch = bst->rchild; BiTree rlch = bst->rchild->lchild; bst->rchild = rlch; bst->rchild->rchild = rch; bst->rchild->rchild->lchild = NULL; Rright(bst); } void Check_Binary_Tree(BiTree &bst) { if (bst == NULL) return; if (Binary_Tree_height(bst->lchild) - Binary_Tree_height(bst->rchild) > 1) { if (Binary_Tree_height(bst->lchild->lchild) > Binary_Tree_height(bst->lchild->rchild)) Lleft(bst); else Lright(bst); } if (Binary_Tree_height(bst->rchild) - Binary_Tree_height(bst->lchild) > 1) { if (Binary_Tree_height(bst->rchild->rchild) > Binary_Tree_height(bst->rchild->lchild)) Rright(bst); else Rleft(bst); } //Check_Binary_Tree(bst->lchild); //Check_Binary_Tree(bst->rchild); } //假設沒有相等的data //插入結點 void Insert_Binary_Tree(BiTree& bst ,int t) //bst是根節點 { if (bst == NULL) //空樹或者葉結點 { BiTree newp = new Binode; newp->data = t; newp->lchild = NULL; newp->rchild = NULL; bst = newp; } else { if (t > bst->data) Insert_Binary_Tree(bst->rchild, t); else Insert_Binary_Tree(bst->lchild, t); } Check_Binary_Tree(bst); } //創建一棵二叉排序樹 BiTree Create_Binary_Tree() { BiTree bst = NULL; int t; cin >> t; while (t != ENDKEY) { Insert_Binary_Tree(bst, t); cin >> t; } return bst; } //二叉排序樹的刪除 BiTree Delete_Binary_Tree(BiTree bst, int t) { Binode* newp, * f, * s, * q; newp = bst; f = NULL; while (newp) { if (newp->data == t) break; f = newp; if (t > newp->data) newp = newp->rchild; else newp = newp->lchild; } if (newp == NULL) return bst; if (newp->lchild == NULL) { if (f == NULL) bst = bst->rchild; else if (f->lchild == newp) f->lchild = newp->rchild; else f->rchild = newp->rchild; delete[]newp; } else if (newp->rchild == NULL) { if (f == NULL) bst = bst->lchild; else if (f->lchild == newp) f->lchild = newp->lchild; else f->rchild = newp->lchild; delete[]newp; } else { q = newp; s = newp->lchild; while (s->rchild) { q = s; s = s->rchild; } if (q == newp) q->lchild = s->lchild; else q->rchild = s->lchild; newp->data = s->data; delete[]s; } Check_Binary_Tree(bst); return bst; } //搜索二叉樹 BiTree Search_Binary_Tree(BiTree bst, int t) { if (bst == NULL) return NULL; if (bst->data == t) return bst; else if (t > bst->data) return Search_Binary_Tree(bst->rchild, t); else return Search_Binary_Tree(bst->lchild, t); }測試數據#include<iostream> #include"BST.h" using namespace std; int main() { BiTree bst = Create_Binary_Tree(); int level = 1; Midorder_Traverse(bst, level); system("pause"); }測試結果:
