1、9.1 概述,9.1.1 查找表,9.1.2 相關(guān)術(shù)語,9.1.3 類型說明,9.2 靜態(tài)查找表,9.2.1 概述,9.2.2 順序表的查找,9.2.3 有序表的查找,9.2.4 索引順序表的查找,9.3 動(dòng)態(tài)查找表,9.3.1 概述,9.3.2 二叉排序樹和平衡二叉樹,9.3.3 B-樹和B+樹,9.4 哈希表,9.4.1 定義,9.4.2 哈希函數(shù)的構(gòu)造,9.4.3 處理沖突的方法,9.4.4 哈希表的查找及其分析,第九章查找,（2）平衡二叉樹,定義,平衡二叉樹（Balanced Binary Tree 或Height-Balanced Tree）又稱AVL樹。它或者是一棵空樹，或者是具有

2、下列性質(zhì)的二叉樹：它的左子樹和右子樹都是平衡二叉樹，且左子樹和右子樹的深度之差的絕對值不超過1。,平衡因子BF（Balance Factor）：二叉樹上結(jié)點(diǎn)的左子樹的深度減去它的右子樹的深度的值。,由平衡二叉樹的定義易知，平衡二叉樹上所有結(jié)點(diǎn)的平衡因子只可能 是1、0和1。,（2）平衡二叉樹,定義,例如，圖9.6(a)所示為兩棵平衡二叉樹，而圖9.6(b)為兩棵不平衡二叉樹，結(jié)點(diǎn)中的值為該結(jié)點(diǎn)的平衡因子,圖形表示,(a) 平衡二叉樹,(b) 不平衡二叉樹,圖9.6平衡與不平衡二叉樹及結(jié)點(diǎn)的平衡因子,平衡二叉樹是二叉排序樹的另一種形式。 我們希望由任何初始序列構(gòu)成的二叉排序樹都是平衡二叉樹。因?yàn)?/p>

3、平衡二叉樹上任何結(jié)點(diǎn)的左右子樹的深度之差都不超過1，則可以證明它的深度和logN是同數(shù)量級的（其中N是結(jié)點(diǎn)的個(gè)數(shù)）。由此，它的平均查找長度也和logN同數(shù)量級。,typedef structBSTNode ElemTypedata; intbf;/結(jié)點(diǎn)的平衡因子 struct BSTNode *lchild, *rchild; /左、右孩子指針 BSTNode, * BSTree;,C語言描述,構(gòu)造二叉平衡（查找）樹的方法是：在插入過程中，采用平衡旋轉(zhuǎn)技術(shù)。,構(gòu)造二叉平衡（查找）樹的方法是： 在插入過程中，采用平衡旋轉(zhuǎn)技術(shù)。,例如:依次插入的關(guān)鍵字為5, 4, 2, 8, 6, 9,5,4,2

4、,4,2,5,8,6,6,5,8,4,2,向右旋轉(zhuǎn) 一次,先向右旋轉(zhuǎn) 再向左旋轉(zhuǎn),9,5,向左旋轉(zhuǎn)一次,繼續(xù)插入關(guān)鍵字 9,假設(shè)由于在二叉排序樹上插入結(jié)點(diǎn)而失去平衡的最小子樹根結(jié)點(diǎn)的指針為a（即a是離插入結(jié)點(diǎn)最近，且平衡因子絕對值超過1的祖先結(jié)點(diǎn))，則失去平衡后進(jìn)行調(diào)整的規(guī)律可歸納為下列4種情況：,平衡調(diào)整,1單向右旋平衡處理： 由于在*a的左子樹根結(jié)點(diǎn)的左子樹上插入結(jié)點(diǎn)，*a的平衡因子由1增至2，致使以*a為根的子樹失去平衡，則需進(jìn)行一次向右的順時(shí)針旋轉(zhuǎn)操作。如圖9.6(a)所示。,2單向左旋平衡處理： 由于在*a的右子樹根結(jié)點(diǎn)的右子樹上插入結(jié)點(diǎn)，*a的平衡因子由1變?yōu)?，致使以*a為根的子

5、樹失去平衡，則需進(jìn)行一次向左的順逆針旋轉(zhuǎn)操作。如圖9.6(c)所示。,3雙向旋轉(zhuǎn)（先左后右）平衡處理： 由于在*a的左子樹根結(jié)點(diǎn)的右子樹上插入結(jié)點(diǎn)，*a的平衡因子由1增至2，致使以*a為根的子樹失去平衡,則需進(jìn)行兩次旋轉(zhuǎn)（先左旋后右旋）操作。如圖9.6(b)所示。,4雙向旋轉(zhuǎn)（先右后左）平衡處理： 由于在*a的右子樹根結(jié)點(diǎn)的左子樹上插入結(jié)點(diǎn)，*a的平衡因子由1變?yōu)?，致使以*a為根的子樹失去平衡,則需進(jìn)行兩次旋轉(zhuǎn)（先右旋后左旋）操作。如圖9.6(d)所示。,插入算法,算法思想： 在平衡二叉排序樹BBST上插入一個(gè)新的數(shù)據(jù)元素e的遞歸算法可描述如下：,1若BBST為空樹，則插入一個(gè)數(shù)據(jù)元素為e的

6、新結(jié)點(diǎn)作為BBST的根結(jié) 點(diǎn)，樹的深度增1；,2若e的關(guān)鍵字和BBST的根結(jié)點(diǎn)的關(guān)鍵字相等，則不進(jìn)行插入；,3若e的關(guān)鍵字小于BBST的根結(jié)點(diǎn)的關(guān)鍵字，而且在BBST的左子樹中不存在和e有相同關(guān)鍵字的結(jié)點(diǎn)，則將e插入在BBST的左子樹上，并且當(dāng)插入之后的左子樹深度增加（1）時(shí)，分別就下列不同情況處理之：,iBBST的根結(jié)點(diǎn)的平衡因子為1（右子樹的深度大于左子樹的深度）：則將根結(jié)點(diǎn)的平衡因子更改為0，BBST的深度不變；,iiBBST的根結(jié)點(diǎn)的平衡因子為0（左、右子樹的深度相等）：則將根結(jié)點(diǎn)的平衡因子更改為1，BBST的深度增1；,iiiBBST的根結(jié)點(diǎn)的平衡因子為1（左子樹的深度大于右子樹的深

7、度）： a.若BBST的左子樹根結(jié)點(diǎn)的平衡因子為1，則需進(jìn)行單向右旋平衡處理，并且在右旋處理之后，將根結(jié)點(diǎn)和其右子樹根結(jié)點(diǎn)的平衡因子更改為0，樹的深度不變； b. 若BBST的左子樹根結(jié)點(diǎn)的平衡因子為1，則需進(jìn)行先向左、后向右的雙向旋轉(zhuǎn)平衡處理，并且在旋轉(zhuǎn)處理之后，修改根結(jié) 點(diǎn)和其左、右子樹根結(jié)點(diǎn)的平衡因子，樹的深度不變。,4若e的關(guān)鍵字大于BBST的根結(jié)點(diǎn)的關(guān)鍵字，而且在BBST的右子樹中不存在和e有相同關(guān)鍵字的結(jié)點(diǎn)，則將e插入在BBST的右子樹上，并且當(dāng)插入之后的右子樹深度增加（1）時(shí)，分別就不同情況處理之。其處理操作和上述3中描述相對稱。,typedef structBSTNode El

8、emTypedata; intbf;/結(jié)點(diǎn)的平衡因子 struct BSTNode *lchild, *rchild; /左、右孩子指針 BSTNode, * BSTree;,算法9.7如下： void R_Rotate (BSTree /p指向新的根結(jié)點(diǎn) / R_Rotate,p,lc,算法9.8如下： void L_Rotate (BSTree /p指向新的根結(jié)點(diǎn) / L_Rotate,p,lc,算法9.10如下：,#defineLH+1/左高 #defineEH0/等高 #defineRH-1/右高 Status InsertAVL (BSTree Tdata = e; Tlchild

9、= Trchild = NULL;,Tbf = EH; taller = TRUE; ,else /應(yīng)繼續(xù)在*T的右子樹中進(jìn)行搜索 if (!InsertAVL(Trchild, e, taller)/未插入 return 0; if (taller)/已插入到*T的右子樹中且右子樹“長高” switch (Tbf) /檢查*T的平衡度 case LH:/原本右子樹比左子樹高，現(xiàn)左、右子樹等高 Tbf = EH; taller = FALSE; break; case EH:/原本左右子樹等高，現(xiàn)因右子樹增高而使樹增高 Tbf = RH; taller = TRUE; break; case

10、RH:/原本右子樹比左子樹高，需要作右平衡處理 RightBalance (T); taller = FALSE; break; / switch (Tbf) / else / else return 1; / InsertAVL,void LeftBalance (BSTree ,case RH: Tbf = EH; lcbf = LH; break; / switch (rdbf) rdbf = EH; L_Rotate (Tlchild);/對*T的左子樹作左旋平衡處理 R_Rotate (T);/對*T作右旋平衡處理 / switch (lcbf) / LeftBalance,在平衡樹上進(jìn)行查找的過程和二叉排序樹相同，因此，查找過程中和給定值進(jìn)行比較的關(guān)鍵字的個(gè)數(shù)不超過平衡 樹的深度。,平衡樹的查找性能分析：,問：含 n 個(gè)關(guān)鍵字的二叉平衡樹可能達(dá)到的最大深度是多少？,n = 0,空樹,最大深度為 0,n = 1,最大深度為 1,n = 2,最大深度為 2,n = 4,最大深度為 3,n = 7,最大深度為 4,先看幾個(gè)具體情況:,反過來問，深度為 h 的二叉平衡樹中所含結(jié)點(diǎn)的最小值 Nh 是多少？,h = 0,N0 = 0,h = 1,h = 2,h = 3,一般情況下，,N1 = 1,N2 = 2,N3 = 4,Nh = Nh-1 +