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

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