版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
4.5平衡二叉樹假定二叉搜索樹中每個(gè)結(jié)點(diǎn)的查找概率都是相同的,稱查找所有結(jié)點(diǎn)的比較次數(shù)的平均值為樹的“平均查找長(zhǎng)度”(ASL)。一、什么是平衡二叉樹〖例〗搜索樹結(jié)點(diǎn)不同插入次序,將導(dǎo)致不同的深度和平均查找長(zhǎng)度ASL
Jan AprAprFeb
MarJuneMayFebJulyMayAugAugJulySeptAugJanMarOctOctDecOctAprDecJuneNovSeptSeptNov
(a)自然月份序列ASL(a)=(1+2×2+3×3+4×3+5×2+6×1)/12=3.5
(b)按July,Feb,May,Mar,Aug,Jan,Apr,Jun,Oct,Sept,Nov,Dec
ASL(b)=3.0
(c)月份字符串大小順序
ASL(c)=6.5
樹深在最好的情況下是O(logN),所以,二叉搜索樹在最好情況下的查找復(fù)雜度是O(logN)。上述ASL的計(jì)算結(jié)果表明,一棵樹的ASL值越小,它的結(jié)構(gòu)越好,與完全二叉樹越接近,其查找時(shí)間復(fù)查度也越接近O(logN)。因此,為了保證二叉搜索樹查找的對(duì)數(shù)級(jí)時(shí)間效率,應(yīng)盡可能創(chuàng)建枝繁葉茂的樹,而避免樹枝過長(zhǎng)、過少。最好的結(jié)構(gòu)是完美二叉樹,從根到葉的各條路徑都是相同的,稱這種樹為完全平衡的。
二、定義
“平衡因子(BalanceFactor,簡(jiǎn)稱BF):BF(T)=hL-hR, 其中hL和hR分別為T的左、右子樹的高度。
平衡二叉樹(BalancedBinaryTree)(AVL樹)
①空樹,或者
②任一結(jié)點(diǎn)左、右子樹高度差的絕對(duì)值不超過1,即|BF(T)|≤1
因此,平衡二叉樹上每個(gè)結(jié)點(diǎn)的平衡因子只可能是-1、0和1,否則,只要有一個(gè)結(jié)點(diǎn)的平衡因子的絕對(duì)值大于1,該二叉樹就不是平衡二叉樹。三、平衡二叉樹的調(diào)整
一般的二叉排序樹是不平衡的,若能通過某種方法使其既保持有序性,又具有平衡性,就找到了構(gòu)造平衡二叉排序樹的方法,該方法稱為平衡化旋轉(zhuǎn)。
在對(duì)AVL樹進(jìn)行插入或刪除一個(gè)結(jié)點(diǎn)后,通常會(huì)影響到從根結(jié)點(diǎn)到插入(或刪除)結(jié)點(diǎn)的路徑上的某些結(jié)點(diǎn),這些結(jié)點(diǎn)的子樹可能發(fā)生變化。這時(shí)就需要做“平衡化”處理,即相應(yīng)的局部“旋轉(zhuǎn)”調(diào)整,使得調(diào)整后的樹達(dá)到平衡。1000MarMayNov
2Mar1右單旋
MayMay0
0Mar
0Nov
Nov
不平衡的“發(fā)現(xiàn)者”是Mar,“麻煩結(jié)點(diǎn)”Nov在發(fā)現(xiàn)者右子樹的右邊, 因而叫RR插入,需要RR旋轉(zhuǎn)(右單旋)AL1
A0BRR插入AL2
A1
BRR旋轉(zhuǎn)0A0BBRBLBRBLBRALBL1.單旋調(diào)整cc1010011AugApr2
2May0
LL旋轉(zhuǎn)左單旋1
2May0
0AugMarNov
0AprAug
0MarNov
0
Apr“發(fā)現(xiàn)者”是Mar,“麻煩結(jié)點(diǎn)”Apr在發(fā)現(xiàn)者左子樹的左邊,因而叫LL插入,需要LL旋轉(zhuǎn)(左單旋)0B1AAR
LL插入1B2AAR
LL旋轉(zhuǎn)BL0B0ABLBRBLBRBRARcc001000110001Jan
0
Apr
1Aug
0
2May
1Mar
0Nov
LR左-右雙旋
0
Apr
1Aug
2Mar
0Jan
1May
0NovJan旋轉(zhuǎn)“發(fā)現(xiàn)者”是May,“麻煩結(jié)點(diǎn)”Jan在左子樹的右邊,因而叫LR插入,需要LR旋轉(zhuǎn)
LR2LR0B0A插入1
B
A1旋轉(zhuǎn)0or1
0C1or0CARCARBABLCLCRBLCLCRBLCLCRAROROR2.雙旋調(diào)整DDDDD0Apr200110110200011010001DecJulyFeb
0Apr
1Aug
1Dec
2
Mar
0
Jan0
1May
0July
2
0NovRL
右-左雙旋旋轉(zhuǎn)1
Dec
1
Aug
0
Feb
2Mar
1Jan
1May
0July
0Nov
Feb一般情況調(diào)整如下:
RL2RLA00B插入A
11B旋轉(zhuǎn)0or1
0C1or0ALCALCABCLCRBRCLCRBRALCLCRBRORORDDDDD101Jan110012110DecMarMay110100AprApr0Feb0July0112020010202011Nov00JuneOctSeptAprJune
110
DecDecMar AugAugFebJanJuly AugFebJuly000
11
JanMar110001June
2May Nov
0May June
1Nov0
Oct
0
Oct0
Sept
注意:有時(shí)候插入元素即便不需要調(diào)整結(jié)構(gòu),也可能需要重新計(jì)算 一些平衡因子。typedefstructAVLNode*Position;typedefPositionAVLTree;
/*AVL樹類型*/typedefstructAVLNode{
ElementTypeData;
/*結(jié)點(diǎn)數(shù)據(jù)*/AVLTreeLeft;/*指向左子樹*/AVLTreeRight;/*指向右子樹*/intHeight;/*樹高*/}四、AVL樹的插入intMax(inta,intb){returna>b?a:b;}AVLTreeInsert(AVLTreeT,ElementTypeX){/*將X插入AVL樹T中,并且返回調(diào)整后的AVL樹*/if(!T)
{/*若插入空樹,則新建包含一個(gè)結(jié)點(diǎn)的樹*/
T=(AVLTree)malloc(sizeof(structAVLNode));T->Data=X;
T->Height=0;
T->Left=T->Right=NULL;}/*if(插入空樹)結(jié)束*/elseif(X<T->Data){/*插入T的左子樹*/T->Left=Insert(T->Left,X);
/*如果需要左旋*/
if(GetHeight(T->Left)-GetHeight(T->Right)==2)
if(X<T->Left->Data)
T=SingleLeftRotation(T);/*左單旋*/
else
T=DoubleLeftRightRotation(T);/*左-右雙旋*/}/*elseif(插入左子樹)結(jié)束*/elseif(X>T->Data){/*插入T的右子樹*/T->Right=Insert(T->Right,X);/*如果需要右旋*/if(GetHeight(T->Left)-GetHeight(T->Right)==-2)
if(X>T->Right->Data)T=SingleRightRotation(T);/*右單旋*/
else
T=DoubleRightLeftRotation(T);/*右-左雙旋*/}/*elseif(插入右子樹)結(jié)束*//*elseX==T->Data,無須插入*/T->Height=Max(GetHeight(T->Left),GetHeight(T->Right))+1;
/*別忘了更新樹高*/returnT;}AVLTreeSingleLeftRotation(AVLTreeA)16.{/*注意:A必須有一個(gè)左子結(jié)點(diǎn)B*/17./*將A與B做左單旋,更新A與B的高度,返回新的根結(jié)點(diǎn)B*/18.19.AVLTreeB=A->Left;20.A->Left=B->Right;21.B->Right=A;22.A->Height=Max(GetHeight(A->Left),GetHeight(A->Right))+1;23.B->Height=Max(GetHeight(B->Left),A->Height)+1;24.25.returnB;26.}27.28.AVLTreeDoubleLeftRightRotation(AVLTreeA)29.{/*注意:A必須有一個(gè)左子結(jié)點(diǎn)B,且B必須有一個(gè)右子結(jié)點(diǎn)C*/30./*將A、B與C做兩次單旋,返回新的根結(jié)點(diǎn)C*/31.32./*將B與C做右單旋,C被返回*/33.A->Left=SingleRightRotation(A->Left);34./*將A與C做左單旋,C被返回*/35.returnSingleLeftRotation(A);36.}37.38./*************************************/39./*對(duì)稱的右單旋與右-左雙旋請(qǐng)自己實(shí)現(xiàn)*/40./*************************************/41.AVLTreeSingleLeftRotation(AVLTreeA){/*注意:A必須有一個(gè)左子結(jié)點(diǎn)B*//*將A與B做左單旋,更新A與B的高度,返回新的根結(jié)點(diǎn)B*/
AVLTreeB=A->Left;
A->Left=B->Right;
B->Right=A;
A->Height=Max(GetHeight(A->Left),GetHeight(A->Right))+1;
B->Height=Max(GetHeight(B->Left),A->Height)+1;returnB;
}AVLTreeDoubleLeftRightRotation(AVLTreeA){/*注意:A必須有一個(gè)左子結(jié)點(diǎn)B,且B必須有一個(gè)右子結(jié)點(diǎn)C*//*將A、B與C做兩次單旋,返回新的根結(jié)點(diǎn)C*/A->Left=SingleRightRotation(A->Left);/*將B與C做右單旋,C被返回*/returnSingleLeftRotation(A);/*將A與C做左單旋,C被返回*/}
作業(yè):1、在分量1~11的數(shù)組中按從小到大順序存放11個(gè)元素,如果用順序查找和二分查找分別查找這11個(gè)元素,哪個(gè)位置的元素在這兩種方法的查找中總次數(shù)最少?..A.1B.2C.3D.62、在分量1~11的數(shù)組中按從小到大順序存放11個(gè)元素,如果進(jìn)行二分查找,查找次數(shù)最少的元素位于什么位置?..A.1B.5C.6D.11測(cè)驗(yàn):1.設(shè)有如圖6-27所示的二叉樹。①分別用順序存儲(chǔ)方法和鏈接存儲(chǔ)方法畫出該二叉樹的存儲(chǔ)結(jié)構(gòu)。②寫出該二叉樹的先序、中序、后序遍歷序列。2.已知一棵二叉樹的先序遍歷序列和中序遍歷序列分別為ABDGHCEFI和GDHBAECIF,請(qǐng)畫出這棵二叉樹,然后給出該樹的后序遍歷序列。圖6-27二叉樹adebfgchkmn3、一棵度為m的樹有n個(gè)節(jié)點(diǎn)。若每個(gè)節(jié)點(diǎn)直接用m個(gè)鏈指向相應(yīng)的兒子,則表示這個(gè)樹所需要的總空間是n*(m+1)(假定每個(gè)鏈以及表示節(jié)點(diǎn)的數(shù)據(jù)域都是一個(gè)單位空間).。當(dāng)采用兒子/兄弟(FirstChild/NextSibling)表示法時(shí),所需的總空間是:..A.3nB.2nC.n*mD.n*(m-1)4、如果一個(gè)完全二叉樹最底下一層為第六層(根為第一層)且該層共有8個(gè)葉結(jié)點(diǎn),那么該完全二叉樹共有多少個(gè)結(jié)點(diǎn)?..A.31B.39C.63D.715、若有一二叉樹的總結(jié)點(diǎn)數(shù)為98,只有一個(gè)兒子的結(jié)點(diǎn)數(shù)為48,則該樹的葉結(jié)點(diǎn)數(shù)是多少?..A.25B.50C.不確定D.這樣的樹不存在6、設(shè)深度為d(只有一個(gè)根結(jié)點(diǎn)時(shí),d為1)的二叉樹只有度為0和2的結(jié)點(diǎn),則此類二叉樹的結(jié)點(diǎn)數(shù)至少為2d-1..A.√B.×7、假定只有四個(gè)結(jié)點(diǎn)A、B、C、D的二叉樹,其前序遍歷序列為ABCD,則下面哪個(gè)序列是不可能的中序遍歷序列?..A.ABCDB.ACDBC.DCBAD.DABC8、對(duì)于二叉樹,如果其中序遍歷結(jié)果與前序遍歷結(jié)果一樣,那么可以斷定該二叉樹________..A.是完全二叉樹B.所有結(jié)點(diǎn)都沒有左兒子C.所有結(jié)點(diǎn)都沒有右兒子D.這樣的樹不存在9、已知一二叉樹的后序和中序遍歷的結(jié)果分別是FDEBGCA和FDBEACG,那么該二叉樹的前序遍歷結(jié)果是什么?..A.ABDFECGB.ABDEFCGC.ABDFEGCD.ABCDEFG10、假定只有四個(gè)結(jié)點(diǎn)A、B、C、D的二叉樹,其前序遍歷序列為ABCD,則下面哪個(gè)序列是不可能的中序遍歷序列?..A.ABCDB.ACDBC.DCBAD.DABC11、對(duì)于二叉樹,如果其中序遍歷結(jié)果與前序遍歷結(jié)果一樣,那么可以斷定該二叉樹________..A.是完全二叉樹B.所有結(jié)點(diǎn)都沒有左兒子C.所有結(jié)點(diǎn)都沒有右兒子D.這樣的樹不存在12、已知一二叉樹的后序和中序遍歷的結(jié)果分別是FDEBGCA和FDBEACG,那么該二叉樹的前序遍歷結(jié)果是什么?..A.ABDFECGB.ABDEFCGC.ABDFEGCD.ABCDEFG13、非遞歸方法中序遍歷下面這顆二叉樹,其堆棧操作序列(P代表為push,O代表為pop)是什么?..A.PPOOPOPPOOB.PPPPPOOOOOC.PPOOOPPOOD.PPOPOOPPOO14、已知
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(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ì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 二零二五年枸杞采摘采摘技術(shù)與設(shè)備租賃合同3篇
- 二零二五年度網(wǎng)絡(luò)安全人才培養(yǎng)與輸送合同2篇
- 二零二五版果園果樹種植與農(nóng)業(yè)技術(shù)培訓(xùn)服務(wù)合同樣本3篇
- 二零二五年度采砂廠承包綜合效益評(píng)估合同范本3篇
- 二零二五版智能化住宅項(xiàng)目施工及造價(jià)管理合同3篇
- 二零二五年度環(huán)保污水處理設(shè)備采購補(bǔ)充合同范本2篇
- 2025年新型城鎮(zhèn)化項(xiàng)目場(chǎng)地租賃與開發(fā)建設(shè)合同范本2篇
- 二零二五版環(huán)保設(shè)施投資合作合同3篇
- 二零二五版交通事故車輛損失賠償合同3篇
- 二零二五版特種車輛租賃及操作培訓(xùn)合同3篇
- 寒潮雨雪應(yīng)急預(yù)案范文(2篇)
- DB33T 2570-2023 營(yíng)商環(huán)境無感監(jiān)測(cè)規(guī)范 指標(biāo)體系
- 上海市2024年中考英語試題及答案
- 房屋市政工程生產(chǎn)安全重大事故隱患判定標(biāo)準(zhǔn)(2024版)宣傳海報(bào)
- 垃圾車駕駛員聘用合同
- 2025年道路運(yùn)輸企業(yè)客運(yùn)駕駛員安全教育培訓(xùn)計(jì)劃
- 南京工業(yè)大學(xué)浦江學(xué)院《線性代數(shù)(理工)》2022-2023學(xué)年第一學(xué)期期末試卷
- 2024版機(jī)床維護(hù)保養(yǎng)服務(wù)合同3篇
- 《論拒不執(zhí)行判決、裁定罪“執(zhí)行能力”之認(rèn)定》
- 工程融資分紅合同范例
- 2024年貴州省公務(wù)員錄用考試《行測(cè)》真題及答案解析
評(píng)論
0/150
提交評(píng)論