數(shù)據(jù)結(jié)構(gòu)第六章 平衡樹(shù)

1、6.5平衡二叉樹(shù)平衡二叉樹(shù)（balancedbinarytree）是對(duì)二叉搜索樹(shù)的一種改進(jìn)。二叉搜索樹(shù)有一個(gè)缺點(diǎn)，那就是樹(shù)的結(jié)構(gòu)事先無(wú)法預(yù)料，隨意性很大，它只與結(jié)點(diǎn)的值和插入次序有關(guān)，往往得到的是一棵很不“平衡”的二叉樹(shù)。二叉搜索樹(shù)與理想平衡樹(shù)相差越遠(yuǎn)，樹(shù)的高度就越高，其運(yùn)算時(shí)間就越長(zhǎng)，在最壞的情況下，就是對(duì)單鏈表進(jìn)行運(yùn)算的時(shí)間，其時(shí)間復(fù)雜度由O(n)變?yōu)镺(n)，從而部分或2log全部地喪失了利用二叉搜索樹(shù)組織數(shù)據(jù)的優(yōu)點(diǎn)。為了克服二叉

2、搜索樹(shù)的這個(gè)缺點(diǎn)，需要在插入和刪除結(jié)點(diǎn)時(shí)對(duì)樹(shù)的結(jié)構(gòu)進(jìn)行必要的調(diào)整，使二叉搜索樹(shù)始終處于一種平衡的狀態(tài)，即始終成為一種平衡二叉樹(shù)(balancedbinarytree)，簡(jiǎn)稱(chēng)平衡樹(shù)。當(dāng)然它不是理想平衡樹(shù)，因?yàn)槟菍⑹拐{(diào)整操作更為復(fù)雜，使調(diào)整帶來(lái)的好處得不償失。本節(jié)將首先討論平衡樹(shù)的定義和調(diào)整操作，然后討論B_樹(shù)的定義以及查找、插入和刪除等運(yùn)算。6.5.1平衡二叉樹(shù)的定義平衡二叉樹(shù)簡(jiǎn)稱(chēng)平衡樹(shù)是由阿德?tīng)柹痪S爾斯基和蘭迪斯(AdelsonVel

3、skiiLis)于1962年首先提出的，所以又稱(chēng)為AVL樹(shù)。平衡樹(shù)的定義是：若一棵二叉樹(shù)中每個(gè)結(jié)點(diǎn)的左、右子樹(shù)的高度至多相差１，則稱(chēng)此樹(shù)為平衡樹(shù)。我們把二叉樹(shù)中每個(gè)結(jié)點(diǎn)的左子樹(shù)高度減去右子樹(shù)的高度定義為該結(jié)點(diǎn)的平衡因子(balancefact)，因此，平衡樹(shù)中每個(gè)結(jié)點(diǎn)的平衡因子只能是10或1。圖76(a)是一棵平衡樹(shù)，圖76(b)和圖76(c)分別是一棵非平衡樹(shù)，每個(gè)結(jié)點(diǎn)的上方所標(biāo)數(shù)字為該結(jié)點(diǎn)的平衡因子。雖然平衡樹(shù)的平衡性比理想平衡樹(shù)要

4、差一些，但理論上已經(jīng)證明：具有n個(gè)結(jié)點(diǎn)的平衡樹(shù)的高度在任何情況下決不會(huì)比具有相同結(jié)點(diǎn)數(shù)的理想平衡樹(shù)高出45%以上。因此，在平衡樹(shù)上進(jìn)行查找運(yùn)算雖比理想平衡樹(shù)要慢一些，但通常比任意生成的二叉搜索樹(shù)快得多，當(dāng)然，其時(shí)間復(fù)雜度的數(shù)量級(jí)表示仍為O(n).2log123611511220148010232(1)LL型調(diào)整操作它是因在Ａ結(jié)點(diǎn)的左(left)孩子（假定用B表示）的左(left)子樹(shù)上插入結(jié)點(diǎn)，使得A結(jié)點(diǎn)的平衡因子由1變?yōu)?而引起的不平

5、衡所進(jìn)行的調(diào)整操作。調(diào)整過(guò)程如圖77所示，圖中用長(zhǎng)方框表示子樹(shù)，用長(zhǎng)方框的高度表示子樹(shù)的高度，用帶陰影的小方框表示被插入的結(jié)點(diǎn)。圖77(a)為插入前的平衡子樹(shù)，、和a?的子樹(shù)高度均為h(h0，若h=0，則它們均為空樹(shù))，A結(jié)點(diǎn)和B結(jié)點(diǎn)的平衡因??子分別為1和0。圖77(b)為在B的左子樹(shù)上插入一個(gè)新結(jié)點(diǎn)，以A為根的子樹(shù)a成為最小不平衡子樹(shù)的情況。圖77(c)為調(diào)整后成為新的平衡平衡子樹(shù)的情況，調(diào)整規(guī)則是：將A的左孩子B向右旋轉(zhuǎn)代替Ａ成為