數(shù)據(jù)結(jié)構(gòu)之AVL樹詳解
1. 概述
AVL樹是最早提出的自平衡二叉樹,在AVL樹中任何節(jié)點(diǎn)的兩個(gè)子樹的高度最大差別為一,所以它也被稱為高度平衡樹。AVL樹得名于它的發(fā)明者G.M. Adelson-Velsky和E.M. Landis。AVL樹種查找、插入和刪除在平均和最壞情況下都是O(log n),增加和刪除可能需要通過一次或多次樹旋轉(zhuǎn)來重新平衡這個(gè)樹。本文介紹了AVL樹的設(shè)計(jì)思想和基本操作。
2. 基本術(shù)語
有四種種情況可能導(dǎo)致二叉查找樹不平衡,分別為:
(1)LL:插入一個(gè)新節(jié)點(diǎn)到根節(jié)點(diǎn)的左子樹(Left)的左子樹(Left),導(dǎo)致根節(jié)點(diǎn)的平衡因子由1變?yōu)?
(2)RR:插入一個(gè)新節(jié)點(diǎn)到根節(jié)點(diǎn)的右子樹(Right)的右子樹(Right),導(dǎo)致根節(jié)點(diǎn)的平衡因子由-1變?yōu)?2
(3)LR:插入一個(gè)新節(jié)點(diǎn)到根節(jié)點(diǎn)的左子樹(Left)的右子樹(Right),導(dǎo)致根節(jié)點(diǎn)的平衡因子由1變?yōu)?
(4)RL:插入一個(gè)新節(jié)點(diǎn)到根節(jié)點(diǎn)的右子樹(Right)的左子樹(Left),導(dǎo)致根節(jié)點(diǎn)的平衡因子由-1變?yōu)?2
針對(duì)四種種情況可能導(dǎo)致的不平衡,可以通過旋轉(zhuǎn)使之變平衡。有兩種基本的旋轉(zhuǎn):
(1)左旋轉(zhuǎn):將根節(jié)點(diǎn)旋轉(zhuǎn)到(根節(jié)點(diǎn)的)右孩子的左孩子位置
(2)右旋轉(zhuǎn):將根節(jié)點(diǎn)旋轉(zhuǎn)到(根節(jié)點(diǎn)的)左孩子的右孩子位置
3. AVL樹的旋轉(zhuǎn)操作
AVL樹的基本操作是旋轉(zhuǎn),有四種旋轉(zhuǎn)方式,分別為:左旋轉(zhuǎn),右旋轉(zhuǎn),左右旋轉(zhuǎn)(先左后右),右左旋轉(zhuǎn)(先右后左),實(shí)際上,這四種旋轉(zhuǎn)操作兩兩對(duì)稱,因而也可以說成兩類旋轉(zhuǎn)操作。
基本的數(shù)據(jù)結(jié)構(gòu):
typedef struct Node* Tree;
typedef struct Node* Node_t;
typedef Type int;
struct Node{
Node_t left;
Node_t right;
int height;
Type data;
};
int Height(Node_t node) {
return node->height;
}
3.1 LL
LL情況需要右旋解決,如下圖所示:
代碼為:
Node_t RightRotate(Node_t a) {
b = a->left;
a->left = b->right;
b->right = a;
a->height = Max(Height(a->left), Height(a->right));
b->height = Max(Height(b->left), Height(b->right));
return b;
}
3.2 RR
RR情況需要左旋解決,如下圖所示:
代碼為:
Node_t LeftRotate(Node_t a) {
b = a->right;
a->right = b->left;
b->left = a;
a->height = Max(Height(a->left), Height(a->right));
b->height = Max(Height(b->left), Height(b->right));
return b;
}
3.3 LR
LR情況需要左右(先B左旋轉(zhuǎn),后A右旋轉(zhuǎn))旋解決,如下圖所示:
代碼為:
Node_t LeftRightRotate(Node_t a) {
a->left = LeftRotate(a->left);
return RightRotate(a);
}
3.4 RL
RL情況需要右左旋解決(先B右旋轉(zhuǎn),后A左旋轉(zhuǎn)),如下圖所示:
代碼為:
Node_t RightLeftRotate(Node_t a) {
a->right = RightRotate(a->right);
return LeftRotate(a);
}
4. AVL數(shù)的插入和刪除操作
(1) 插入操作:實(shí)際上就是在不同情況下采用不同的旋轉(zhuǎn)方式調(diào)整整棵樹,具體代碼如下:
Node_t Insert(Type x, Tree t) {
if(t == NULL) {
t = NewNode(x);
} else if(x < t->data) {
t->left = Insert(t->left);
if(Height(t->left) - Height(t->right) == 2) {
if(x < t->left->data) {
t = RightRotate(t);
} else {
t = LeftRightRotate(t);
}
}
} else {
t->right = Insert(t->right);
if(Height(t->right) - Height(t->left) == 2) {
if(x > t->right->data) {
t = LeftRotate(t);
} else {
t = RightLeftRotate(t);
}
}
}
t->height = Max(Height(t->left), Height(t->right)) + 1;
return t;
}
(2) 刪除操作:首先定位要?jiǎng)h除的節(jié)點(diǎn),然后用該節(jié)點(diǎn)的右孩子的最左孩子替換該節(jié)點(diǎn),并重新調(diào)整以該節(jié)點(diǎn)為根的子樹為AVL樹,具體調(diào)整方法跟插入數(shù)據(jù)類似,代碼如下:
Node_t Delete(Type x, Tree t) {
if(t == NULL) return NULL;
if(t->data == x) {
if(t->right == NULL) {
Node_t temp = t;
t = t->left;
free(temp);
} else {
Node_t head = t->right;
while(head->left) {
head = head->left;
}
t->data = head->data; //just copy data
t->right = Delete(t->data, t->right);
t->height = Max(Height(t->left), Height(t->right)) + 1;
}
return t;
} else if(t->data < x) {
Delete(x, t->right);
if(t->right) Rotate(x, t->right);
} else {
Delete(x, t->left);
if(t->left) Rotate(x, t->left);
}
if(t) Rotate(x, t);
}
5. 總結(jié)
AVL樹是最早的自平衡二叉樹,相比于后來出現(xiàn)的平衡二叉樹(紅黑樹,treap,splay樹)而言,它現(xiàn)在應(yīng)用較少,但研究AVL樹對(duì)于了解后面出現(xiàn)的常用平衡二叉樹具有重要意義。
6. 參考資料
(1) 數(shù)據(jù)結(jié)構(gòu)(C語言版) 嚴(yán)蔚敏,吳偉民著
(2) http://zh.wikipedia.org/wiki/AVL%E6%A0%91
相關(guān)文章
舉例分析private的作用(c/c++學(xué)習(xí))
我知道我們可以用 public 中的值,把private中的數(shù)據(jù)給提出來,但是還是搞不懂private該怎么用,或者說在一個(gè)具體程序中,private有什么用2020-08-08Qt圖形圖像開發(fā)之曲線圖表庫QChart編譯安裝詳細(xì)方法與使用實(shí)例
這篇文章主要介紹了Qt圖形圖像開發(fā)之曲線圖表庫QChart編譯安裝詳細(xì)方法與使用實(shí)例,需要的朋友可以參考下2020-03-03VSCode配置C/C++語言環(huán)境(2023最新版)
這篇文章主要介紹了VSCode配置C/C++語言環(huán)境(2023最新版)的全過程,本文給大家講解的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友參考下吧2023-11-11深入剖析C++中的struct結(jié)構(gòu)體字節(jié)對(duì)齊
要求數(shù)據(jù)內(nèi)存的起始地址的值是某個(gè)數(shù)k的倍數(shù),這就是所謂的內(nèi)存對(duì)齊,本文就來深入剖析C++中的struct結(jié)構(gòu)體字節(jié)對(duì)齊,需要的朋友可以參考下2016-05-05