排序二叉樹和平衡二叉樹.doc

9.2.1 二叉排序樹和平衡二叉樹 一、二叉排序樹及其查找過程 什么是二叉排序樹? 二叉排序樹(Binary Sort Tree)或者是一棵空樹；或者是具有下列性質(zhì)的二叉樹：(1)若它的左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；(2)若它的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值；(3)它的左、右子樹也分別為二叉排序樹。 二叉排序樹又稱二叉查找樹，根據(jù)上述定義的結(jié)構(gòu)特點(diǎn)可見，它的查找過程和次優(yōu)二叉樹類似。即當(dāng)二叉排序樹不空時(shí)，首先將給定值和根結(jié)點(diǎn)的關(guān)鍵字比較，若相等，則查找成功，否則將依據(jù)給定值和根結(jié)點(diǎn)的關(guān)鍵字之間的大小關(guān)系，分別在左子樹或右子樹上繼續(xù)進(jìn)行查找。 通常，可取二叉鏈表作為二叉排序樹的存儲(chǔ)結(jié)構(gòu)，則上述查找過程如算法 9.5(a)所描述。BiTree SearchBST (BiTree T，KeyType key)/在根指針T所指二叉排序樹中遞歸地查找某關(guān)鍵字等于key的數(shù)據(jù)元素/若查找成功，則返回指向該數(shù)據(jù)元素結(jié)點(diǎn)的指針，否則返回空指針 if( (!T)|EQ(key，Tdata.key) return (T)； /查找結(jié)束 else if LT(key，Tdata.key) return(SearchBST(Tlchild，key)； /在左子樹中繼續(xù)查找 else return(SearchBST(T rchild，key)；/ 在右子樹中繼續(xù)查找/SearchBST 算法 95(a)圖9.7 二叉排序樹示例 例如：在圖9.7所示的二叉排序樹中查找關(guān)鍵字等于100的記錄（樹中結(jié)點(diǎn)內(nèi)的數(shù)均為記錄的關(guān)鍵字）。首先以 key=100和根結(jié)點(diǎn)的關(guān)鍵字比較，因?yàn)閗ey45，則查找以45為根的右子樹，此時(shí)右子樹不空，且key53，則繼續(xù)查找以53為根的右子樹，由于key和53的右子樹根的關(guān)鍵字100相等，則查找成功，返回指向結(jié)點(diǎn)100的指針值。二、二叉排序樹的插入和刪除 和次優(yōu)二叉樹相對(duì)，二叉排序樹是一種動(dòng)態(tài)樹表。其特點(diǎn)是：樹的結(jié)構(gòu)通常不是一次生成的，而是在查找過程中，當(dāng)樹中不存在關(guān)鍵字等于給定值的結(jié)點(diǎn)時(shí)再進(jìn)行插入。新插入的結(jié)點(diǎn)一定是一個(gè)新添加的葉子結(jié)點(diǎn)，并且是查找不成功時(shí)查找路徑上訪問的最后一個(gè)結(jié)點(diǎn)的左孩子或右孩子結(jié)點(diǎn)。為此，需將上一小節(jié)的二叉排序樹的查找算法改寫成算法9.5(b)，以便能在查找不成功時(shí)返回插入位置。插入算法如算法9.6所示。Status SearchBST(BiTree T，KeyType key，BiTree f，BiTree &p)/在根指針T所指二叉排序樹中遞歸地查找其關(guān)鍵字等于key的數(shù)據(jù)元素，/若查找成功，則指針p指向該數(shù)據(jù)元素結(jié)點(diǎn)，并返回TRUE，/否則指針p指向查找路徑上訪問的最后一個(gè)結(jié)點(diǎn)并返回FALSE，/指針f指向T的雙親，其初始調(diào)用值為NULL if(!T) p=f；return FALSE； /查找不成功 else if EQ(key, Tdata.key) p=T；return TRUE； /查找成功 else if LT(key，Tdata.key) SearchBST(Tlchild，key，T，p)； /在左子樹中繼續(xù)查找 else SearchBST(Trchild，key，T，p)；/在右子樹中繼續(xù)查找/SearchBST算法 9.5(b)Status Insert BST(BiTree &T，ElemType e)/當(dāng)二叉排序樹T中不存在關(guān)鍵字等于e.key的數(shù)據(jù)元素時(shí),插入e并返回TRUE，否則返回FALSE if(!SearchBST(T，e.key，NULL，p) /查找不成功 s=(BiTree)malloc(sizeof(BiTNode)； sdata=e； slchild= srchild=NULL； if (!p) T = s； /被插結(jié)點(diǎn)*s為新的根結(jié)點(diǎn) ，原樹為空 else if LT(e.key，pdata.key) plchild=s； /被插結(jié)點(diǎn)*s為左孩子 else prchild=s /被插結(jié)點(diǎn)*s為右孩子 return TRUE； else return FALSE; /樹中已有關(guān)鍵字相同的結(jié)點(diǎn)，不再插入/ Insert BST算法 9.6 若從空樹出發(fā)，經(jīng)過一系列的查找插入操作之后，可生成一棵二叉樹。設(shè)查找的關(guān)鍵字序列為45，24，53，45，12，24，9，則生成的二叉排序樹如圖9.8所示。 圖9.8 二義排序樹的構(gòu)造過程 容易看出，中序遍歷二叉排序樹可得到一個(gè)關(guān)鍵字的有序序列(這個(gè)性質(zhì)是由二叉排序樹的定義決定的)。這就是說，一個(gè)無(wú)序序列可以通過構(gòu)造一棵二叉排序樹而變成一個(gè)有序序列，構(gòu)造樹的過程即為對(duì)無(wú)序序列進(jìn)行排序的過程。不僅如此，從上面的插入過程還可以看到，每次插入的新結(jié)點(diǎn)都是二叉排序樹上新的葉子結(jié)點(diǎn)，則在進(jìn)行插入操作時(shí)，不必移動(dòng)其它結(jié)點(diǎn)，僅需改動(dòng)某個(gè)結(jié)點(diǎn)的指針，由空變?yōu)榉强占纯?。這就相當(dāng)于在一個(gè)有序序列上插入一個(gè)記錄而不需要移動(dòng)其它記錄。它表明，二叉排序樹既擁有類似于折半查找的特性，又采用了鏈表作存儲(chǔ)結(jié)構(gòu)，因此是動(dòng)態(tài)查找表的一種適宜表示。 同樣，在二叉排序樹上刪去一個(gè)結(jié)點(diǎn)也很方便。刪去樹上一個(gè)結(jié)點(diǎn)相當(dāng)于刪去有序序列中的一個(gè)記錄，只要在刪除某個(gè)結(jié)點(diǎn)之后依舊保持二叉排序樹的特性即可。 那末，如何在二叉排序樹上刪去一個(gè)結(jié)點(diǎn)呢? 假設(shè)在二叉排序樹上被刪結(jié)點(diǎn)為*p(指向結(jié)點(diǎn)的指針為p)，其雙親結(jié)點(diǎn)為*f(結(jié)點(diǎn)指針為f)，且不失一般性，可設(shè)*p是*f的左孩子。 下面分三種情況進(jìn)行討論： (1)若*p結(jié)點(diǎn)為葉子結(jié)點(diǎn)，即PL和PR均為空樹。由于刪去葉子結(jié)點(diǎn)不破壞整棵樹的結(jié)構(gòu)，則只需修改其雙親結(jié)點(diǎn)的指針即可。 (2)若*p結(jié)點(diǎn)只有左子樹PL或者只有右子樹PR，此時(shí)只要令PL或PR直接成為其雙親結(jié)點(diǎn)*f的左子樹即可。顯然，作此修改也不破壞二叉排序樹的特性。 (3)若*p結(jié)點(diǎn)的左子樹和右子樹均不空。顯然，此時(shí)不能如上簡(jiǎn)單處理。從圖9.9 (b)可知，在刪去*p結(jié)點(diǎn)之前，中序遍歷該二叉樹得到的序列為CLCQLQSLSPPRF，在刪去*p之后，為保持其它元素之間的相對(duì)位置不變，可以有兩種做法：其一是令*p的左子樹為*f的左子樹，而*p的右子樹為*s的右子樹，如圖9.9(c)所示；其二是令*p的直接前驅(qū)(或直接后繼)替代*p，然后再?gòu)亩媾判驑渲袆h去它的直接前驅(qū)(或直接后繼)。如圖9.9(d)所示，當(dāng)以直接前驅(qū)*s替代*p時(shí)，由于*s只有左子樹SL，則在刪去*s之后，只要令SL為*s的雙親*q的右子樹即可。圖9.9 在二叉排序樹中刪除*p(a)*f為根的子樹；(b)刪除*p之前；(c)刪除*p之后，PR作為*s右子樹的情形；(d)刪除*p之后，*s替代的情形 三、二叉排序樹的查找分析 在二叉排序樹上查找其關(guān)鍵字等于給定值的結(jié)點(diǎn)的過程，恰是走了一條從根結(jié)點(diǎn)到該結(jié)點(diǎn)的路徑的過程，和給定值比較的關(guān)鍵字個(gè)數(shù)等于路徑長(zhǎng)度加1(或結(jié)點(diǎn)所在層次數(shù))，因此，和折半查找類似，與給定值比較的關(guān)鍵字個(gè)數(shù)不超過樹的深度。然而，折半查找長(zhǎng)度為n的表的判定樹是唯一的，而含有n個(gè)結(jié)點(diǎn)的二叉排序樹卻不唯一。例如：圖9.10中(a)和(b)的兩棵二叉排序樹中結(jié)點(diǎn)的值都相同，但前者由關(guān)鍵字序列(45，24，53，12，37，93)構(gòu)成，而后者由關(guān)鍵字序列(12，24，37，45，53，93)構(gòu)成。(a)樹的深度為3，而(b)樹的深度為6。 因此，含有n個(gè)結(jié)點(diǎn)的二叉排序樹的平均查找長(zhǎng)度和樹的形態(tài)有關(guān)。當(dāng)先后插入的關(guān)鍵字有序時(shí)，構(gòu)成的二叉樹蛻變?yōu)閱沃?。樹的深度為n，其平均查找長(zhǎng)度和順序查找相同，這是最差的情況。顯然，最好的情況是二叉排序樹的形態(tài)和折半查找的判定樹相同，其平均查找長(zhǎng)度和log2n成正比。 四、平衡二叉樹 平衡二叉樹(Balanced Binary Tree或Height-Balanced Tree)又稱AVL樹。它或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹：它的左子樹和右子樹都是平衡二叉樹，且左子樹和右子樹的深度之差的絕對(duì)值不超過1。若將二叉樹上結(jié)點(diǎn)的平衡因子BF(Balance Factor)定義為該結(jié)點(diǎn)的左子樹的深度減去它的有子樹的深度，則平衡二叉樹上所有結(jié)點(diǎn)的平衡因子只可能是-1、0和1。只要二叉樹上有一個(gè)結(jié)點(diǎn)的平衡因子的絕對(duì)值大于1，則該二叉樹就是不平衡的。如圖9.11(a)為兩棵平衡二叉樹，而圖9.11(b)為兩棵不平衡的二叉樹，結(jié)點(diǎn)中的值為該結(jié)點(diǎn)的平衡因子。圖9.11 平衡與不平衡的二叉樹及結(jié)點(diǎn)的平衡因子 我們希望由任何初始序列構(gòu)成的二叉排序樹都是AVL樹。因?yàn)锳VL樹上任何結(jié)點(diǎn)的左右子樹的深度之差都不超過1，則可以證明它的深度和logN是同數(shù)量級(jí)的(其中N為結(jié)點(diǎn)個(gè)數(shù))。由此，它的平均查找長(zhǎng)度也和logN同數(shù)量級(jí)。 如何使構(gòu)成的二叉排序樹成為平衡樹呢?先看一個(gè)具體例子(參見圖9.12)。假設(shè)表中關(guān)鍵字序列為(13，24，37，90，53)。 圖8.12 一般情況下，假設(shè)由于在二叉排序樹上插入結(jié)點(diǎn)而失去平衡的最小根結(jié)點(diǎn)的指針為a(即a是離插入結(jié)點(diǎn)最近，且平衡因子絕對(duì)值超過1的祖先結(jié)點(diǎn))，則失去平衡后進(jìn)行調(diào)整的規(guī)律可歸納為下列四種情況： (1)單向右旋平衡處理：由于在*a的左子樹根結(jié)點(diǎn)的左子樹上插入結(jié)點(diǎn)，*a的平衡因子由1增至2，致使以*a為根的子樹失去平衡，則需進(jìn)行一次向右的順時(shí)針旋轉(zhuǎn)操作。 (2)單向左旋平衡處理：由于在*a的右子樹根結(jié)點(diǎn)的右子樹上插入結(jié)點(diǎn)，*a的平衡因子由-1增至-2，致使以*a為根結(jié)點(diǎn)的子樹失去平衡，則需進(jìn)行一次向左的逆時(shí)針旋轉(zhuǎn)操作。 (3)雙向旋轉(zhuǎn)(先左后右)平衡處理：由于在*a的左子樹根結(jié)點(diǎn)的右子樹上插入結(jié)點(diǎn)，*a的平衡因子由1增至2，致使以*a為根結(jié)點(diǎn)的子樹失去平衡，則需進(jìn)行兩次旋轉(zhuǎn) (先左旋后右旋)操作。 (4)雙向旋轉(zhuǎn)(先右后左)子衡處理：由于在*a的右子樹根結(jié)點(diǎn)的左子樹上插入結(jié)點(diǎn)，*a的平衡因子由-1增至-2，致使以*a為根結(jié)點(diǎn)的子樹失去平衡，則需進(jìn)行兩次旋轉(zhuǎn)(先右旋后左旋)操作。 上述四種情況