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

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

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

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

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

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