下載本文檔
版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
ALV樹的處理
1.概述
AVL樹是最早提出的自平衡二叉樹,在AVL樹中任何節(jié)點(diǎn)的兩個(gè)子樹的高度最大差別為一,所以
它也被稱為高度平衡樹。AVL樹得名于它的發(fā)明者GM.Adelson-Velsky和E.M.Landis。AVL樹種查
找、插入和刪除在平均和最壞情況下都是。(logn),增加和刪除可能需要通過一次或多次樹旋轉(zhuǎn)來重
新平衡這個(gè)樹。本文介紹了AVL樹的設(shè)計(jì)思想和基本操作。
2.基本術(shù)語(yǔ)
有四種種情況可能導(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):
1typedefstructNode*Tree;
2typedefstructNode*Node_t;
3typedefTypeint;
4
5structNode{
6Node_tleft;
7Node_tright;
8intheight;
9Typedata;
10};
11intHeight(Node_tnode){
12returnnode->height;
13)
3.1LL
LL情況需要右旋解決,如下圖所示:
代碼為:
1Node_tRightRotate(Node_ta){
2b=a->left;
3a->left=b->right;
4b->right=a;
5a->height=Max(Height(a->left),Height(a->right));
6b->height=Max(Height(b->left),Height(b->right));
7returnb;
8
3.2RR
RR情況需要左旋解決,如下圖所示:
代碼為:
1Node_tLeftRotate(Node_ta){
2b=a->right;
3a->right=b->left;
4b->left=a;
5a->height=Max(Height(a->left),Height(a->right));
6b->height=Max(Height(b->left),Height(b->right));
7returnb;
8}
3.3LR
LR情況需要左右(先B左旋轉(zhuǎn),后A右旋轉(zhuǎn))旋解決,如下圖所示:
代碼為:
1Node_tLeftRightRotate(Node_ta){
2a->left=LeftRotate(a->left);
3returnRightRotate(a);
4
3.4RL
RL情況需要右左旋解決(先B右旋轉(zhuǎn),后A左旋轉(zhuǎn)),如下圖所示:
代碼為:
1Node_tRightLeftRotate(Node_ta){
2a->right=RightRotate(a->right);
3returnLeftRotate(a);
4)
4.AVL數(shù)的插入和刪除操作
(1)插入操作:實(shí)際上就是在不同情況下采用不同的旋轉(zhuǎn)方式調(diào)整整棵樹,具體代碼如下:
1Node_tInsert(Typex,Treet){
2if(t==NULL){
3t=NewNode(x);
4}elseif(x<t->data){
5t->left=Insert(t->left);
6if(Height(t->left)-Height(t->right)==2){
7if(x<t->left->data){
8t=RightRotate(t);
9}else{
10t=LeftRightRotate(t);
11)
12)
13}else{
14t->right=Insert(t->right);
15if(Height(t->right)-Height(t->left)==2){
16if(x>t->right->data){
17t=LeftRotate(t);
18}else{
19t=RightLeftRotate(t);
20}
21}
22)
23t->height=Max(Height(t->left),Height(t->right))+1;
24returnt;
25)
(2)刪除操作:首先定位要?jiǎng)h除的節(jié)點(diǎn),然后用該節(jié)點(diǎn)的右孩子的最左孩子替換該節(jié)點(diǎn),并重新調(diào)
整以該節(jié)點(diǎn)為根的子樹為AVL樹,具體調(diào)整方法跟插入數(shù)據(jù)類似,代碼如下:
1Node_tDelete(Typex,Treet){
2if(t==NULL)returnNULL;
3if(t->data==x){
4if(t->right==NULL){
5Node_ttemp=t;
6t=t->left;
7free(temp);
8}else{
9Node_thead=t->right;
10while(head->left){
11head=head->left;
12)
13t->data=head->data;//justcopydata
14t->right=Delete(t->data,t->right);
15t->height=Max(Height(t->left),Height(t->right))+1;
16)
17returnt;
18}elseif(t->data<x){
19Delete(x,t->right);
20if(t->right)Rotate(x,t->right);
21}else{
22Delete(x,t->left);
23if(t->left)Rotate(x,t->left);
24)
25if(t)Rotate(x,t);
26)
5.總結(jié)
AVL樹是最早的自平衡二叉樹,相比于后來出現(xiàn)的平衡二叉樹(紅黑樹,treap,splay樹)而
言,它現(xiàn)在應(yīng)用較少,但研究AVL樹對(duì)于了解后面出現(xiàn)的常用平衡二叉樹具有重要意義。
6.參考資料
(1)數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版)嚴(yán)蔚敏,吳偉民著
(2)/wiki/AVL%E6
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 勞務(wù)派遣工作雙方協(xié)議書七篇
- 2023勞務(wù)派遣工作協(xié)議書七篇
- 魚鱗病病因介紹
- 中小學(xué)結(jié)核病防治知識(shí)
- 【中職專用】中職對(duì)口高考-機(jī)電與機(jī)制類專業(yè)-核心課-模擬試卷2(河南適用)(答案版)
- 重慶2020-2024年中考英語(yǔ)5年真題回-學(xué)生版-專題03 短文填空
- 山東省青島市即墨區(qū)2023-2024學(xué)年八年級(jí)上學(xué)期期末英語(yǔ)試題(原卷版)-A4
- 黃金卷04(新課標(biāo)卷)(新疆、西藏專用)(解析版)-A4
- 2023年新型高效飼料及添加劑項(xiàng)目融資計(jì)劃書
- 2023年硝酸鉀項(xiàng)目籌資方案
- 2025年重慶貨運(yùn)從業(yè)資格證考試題及答案詳解
- 屋面板的拆除與更換施工方案
- 生命不是游戲拒絕死亡挑戰(zhàn)主題班會(huì)
- 本地化部署合同
- 2024年云南省中考?xì)v史試卷
- 油氣管線安全保護(hù)方案
- 國(guó)家職業(yè)技術(shù)技能標(biāo)準(zhǔn) 4-07-05-04 消防設(shè)施操作員 人社廳發(fā)201963號(hào)
- 2024-2030年中國(guó)辣椒堿市場(chǎng)占有率調(diào)查及經(jīng)營(yíng)戰(zhàn)略可行性分析研究報(bào)告
- 全過程工程咨詢項(xiàng)目部管理制度
- 拒絕躺平 停止擺爛-學(xué)生心理健康主題班會(huì)(課件)
評(píng)論
0/150
提交評(píng)論