數(shù)據(jù)結(jié)構(gòu)要求集合與搜索

1、數(shù)據(jù)結(jié)構(gòu)要求集合與搜索數(shù)據(jù)結(jié)構(gòu)要求集合與搜索并查集靜態(tài)搜索表二叉搜索樹AVL樹2數(shù)據(jù)結(jié)構(gòu)要求集合與搜索并查集 (Union-Find Sets)并查集支持以下三種操作： Union (Root1, Root2) /合并操作 Find (x) /搜索操作 InitUFSets (s ) /初始化操作對于并查集來說，每個集合用一棵樹表示。為此，采用樹的雙親表示作為集合存儲表示。集合元素的編號從0到 n-1。其中 n 是最大元素個數(shù)。3數(shù)據(jù)結(jié)構(gòu)要求集合與搜索在雙親表示中，第 i 個數(shù)組元素代表包含集合元素 i 的樹結(jié)點(diǎn)。初始時, 根結(jié)點(diǎn)的雙親為-1，表示集合中的元素個數(shù)。在同一棵樹上所有結(jié)點(diǎn)所代表的

2、集合元素在同一個子集合中。為此，需要有兩個映射： 集合元素到存放該元素名的樹結(jié)點(diǎn)間的對應(yīng)； 集合名到表示該集合的樹的根結(jié)點(diǎn)間的對應(yīng)。4數(shù)據(jù)結(jié)構(gòu)要求集合與搜索設(shè) S1= 0, 6, 7, 8 , S2= 1, 4, 9 , S3= 2, 3, 5 集合名 指針0 S11 S22 S30427681935為簡化討論，忽略實(shí)際的集合名，僅用表示集合的樹的根來標(biāo)識集合。5數(shù)據(jù)結(jié)構(gòu)要求集合與搜索初始時, InitUFSets(S) 構(gòu)造一個森林, 每棵樹只有一個結(jié)點(diǎn), 表示集合中各元素自成一個子集合 Si = -1, i = 0, 1, , n-1。用 Find(S, i) 尋找集合元素 i 的根。如果

3、有兩個集合元素 i 和 j: Find(S, i) = Find(S, j) 表明這兩個元素在同一個集合中，如果兩個集合元素 i 和 j 不在同一個集合中,可用 Union(S, i, j) 將它們合并到一個集合中。6數(shù)據(jù)結(jié)構(gòu)要求集合與搜索S1下標(biāo)parent集合 S1, S2 和 S3 的雙親表示-4 4 -3 2 -3 2 0 0 0 40 1 2 3 4 5 6 7 8 90768419235S2S37數(shù)據(jù)結(jié)構(gòu)要求集合與搜索S1 S2的可能的表示方法下標(biāo)parent集合 S1 S2 和 S3 的雙親表示-7 4 -3 2 0 2 0 0 0 40 1 2 3 4 5 6 7 8 9076

4、841941908768數(shù)據(jù)結(jié)構(gòu)要求集合與搜索并查集的結(jié)構(gòu)定義const int SetSize = 50; /并查集元素個數(shù)typedef struct /并查集結(jié)構(gòu)定義 int parentSetSize; /集合元素?cái)?shù)組 UFSets;void InitUFSets (UFSets *S) /集合初始化 for ( int i = 0; i parenti = -1; /每一個自成一個單元素集合9數(shù)據(jù)結(jié)構(gòu)要求集合與搜索 并查集操作的算法 查找-5012301234Find (S,4)Find (S,3) = 3 Find (S,2) =2 Find (S,1) = 1Find (S,0)

5、 = 0 = -5 parent x parent x ); -5 0 1 2 3parentParent4 =3 Parent3 =2Parent2 =1Parent1 =0Parent0 =-50 1 2 3 411數(shù)據(jù)結(jié)構(gòu)要求集合與搜索void Union (UFSets *S, int Root1, int Root2) /求兩個不相交集合Root1與Root2的并 S-parentRoot1 += S-parentRoot2; S-parentRoot2 = Root1; /將Root2連接到Root1下面Find和Union操作性能不好。假設(shè)最初 n 個元素構(gòu)成 n 棵樹組成的森林

6、，S-parenti = -1。做處理Union(n-2, n-1), , Union(1, 2), Union(0, 1)后，將產(chǎn)生退化的樹。12數(shù)據(jù)結(jié)構(gòu)要求集合與搜索合并-1-1-1-1-10234-3-503213341332202314Union(0,1)-23-41421234Union(1,2)Union(2,3)Union(3,4)13數(shù)據(jù)結(jié)構(gòu)要求集合與搜索 執(zhí)行一次Union操作所需時間是 O(1)，n-1次Union操作所需時間是O(n)。 若再執(zhí)行Find(0), Find(1), , Find(n-1), 若被搜索的元素為 i，完成 Find(i) 操作需要時間為O(i)

7、，完成 n 次搜索需要的總時間將達(dá)到 改進(jìn)的方法 按樹的結(jié)點(diǎn)個數(shù)合并 按樹的高度合并 壓縮元素的路徑長度14數(shù)據(jù)結(jié)構(gòu)要求集合與搜索按樹結(jié)點(diǎn)個數(shù)合并結(jié)點(diǎn)個數(shù)多的樹的根結(jié)點(diǎn)作根-1-1-1-1-101234-1-10-7256-5-222332013456233020562314Union(2, 0)15數(shù)據(jù)結(jié)構(gòu)要求集合與搜索void WeightedUnion (UFSets *S, int Rt1, int Rt2 ) /按Union的加權(quán)規(guī)則改進(jìn)的算法 int temp = S-parentRt1 + S-parentRt2; if ( S-parentRt2 parentRt1 ) S-p

8、arentRt1 = Rt2; /Root2中結(jié)點(diǎn)多 S-parentRt2 = temp; /Root1指向Root2 else S-parentRt2 = Rt1; /Root1中結(jié)點(diǎn)多 S-parentRt1 = temp; /Root2指向Root1 16數(shù)據(jù)結(jié)構(gòu)要求集合與搜索按樹高度合并 高度高的樹的根結(jié)點(diǎn)作根-0-0-0-0-001234-0-00-2256-2-122332013456233020562314Union(2, 0)17數(shù)據(jù)結(jié)構(gòu)要求集合與搜索Union操作的折疊規(guī)則為進(jìn)一步改進(jìn)樹的性能，可以使用如下折疊規(guī)則來“壓縮路徑”。即： 如果 j 是從 i 到根root的路徑

9、上的一個結(jié)點(diǎn)，且 S-parentj != rootj， 則把 S-parentj 置為 rooti。0067867819193535從 i = 5 壓縮路徑18數(shù)據(jù)結(jié)構(gòu)要求集合與搜索int CollapsingFind (UFSets *S, int i ) /使用折疊規(guī)則的搜索算法 int j = i; while ( S-parentj = 0 ) j = S-parentj; /讓 j 循雙親指針走到根 while ( i != j ) /換 parenti 到 j int temp = S-parenti; S-parenti = j; i = temp; return j;19數(shù)據(jù)

10、結(jié)構(gòu)要求集合與搜索搜索(Search)的概念靜態(tài)搜索表 所謂搜索，就是在數(shù)據(jù)集合中尋找滿足某 種條件的數(shù)據(jù)對象。 搜索的結(jié)果通常有兩種可能： 搜索成功，即找到滿足條件的數(shù)據(jù)對象 這時,作為結(jié)果, 可報告該對象在結(jié)構(gòu)中 的位置, 還可給出該對象中的具體信息。 搜索不成功，或搜索失敗。作為結(jié)果, 應(yīng)報告一些信息, 如失敗標(biāo)志、位置等。 20數(shù)據(jù)結(jié)構(gòu)要求集合與搜索通常稱用于搜索的數(shù)據(jù)集合為搜索結(jié)構(gòu)，它是由同一數(shù)據(jù)類型的對象(或記錄)組成。在每個對象中有若干屬性，其中有一個屬性，其值可唯一地標(biāo)識這個對象。稱為關(guān)鍵碼。使用基于關(guān)鍵碼的搜索，搜索結(jié)果應(yīng)是唯一的。但在實(shí)際應(yīng)用時，搜索條件是多方面的，可以使用

11、基于屬性的搜索方法，但搜索結(jié)果可能不唯一。21數(shù)據(jù)結(jié)構(gòu)要求集合與搜索實(shí)施搜索時有兩種不同的環(huán)境。靜態(tài)環(huán)境，搜索結(jié)構(gòu)在插入和刪除等操作的前后不發(fā)生改變。 靜態(tài)搜索表 動態(tài)環(huán)境，為保持較高的搜索效率, 搜索結(jié)構(gòu)在執(zhí)行插入和刪除等操作的前后將自動進(jìn)行調(diào)整，結(jié)構(gòu)可能發(fā)生變化。 動態(tài)搜索表 22數(shù)據(jù)結(jié)構(gòu)要求集合與搜索#define MaxSize 100 /搜索表最大尺寸typedef int DataType; /搜索數(shù)據(jù)的類型 typedef struct /搜索表結(jié)點(diǎn)定義 DataType key; /關(guān)鍵碼域 other; /其他數(shù)據(jù)域 ListNode;typedef struct dataL

12、ist /搜索表結(jié)點(diǎn)定義 ListNode dataMaxSize; /數(shù)據(jù)存儲數(shù)組 int n; /數(shù)組當(dāng)前長度靜態(tài)搜索表結(jié)構(gòu)的定義23數(shù)據(jù)結(jié)構(gòu)要求集合與搜索衡量一個搜索算法的時間效率的標(biāo)準(zhǔn)是：在搜索過程中關(guān)鍵碼的平均比較次數(shù)，也稱為平均搜索長度ASL(Average Search Length)，通常它是搜索結(jié)構(gòu)中對象總數(shù) n的函數(shù)。在靜態(tài)搜索表中, 利用數(shù)組元素的下標(biāo)作為數(shù)據(jù)對象的存放地址。搜索算法根據(jù)給定值x, 在數(shù)組中進(jìn)行搜索。直到找到x在數(shù)組中的位置或可確定在數(shù)組中找不到x為止。另外衡量一個搜索算法還要考慮算法所需要的存儲量和算法的復(fù)雜性等問題。24數(shù)據(jù)結(jié)構(gòu)要求集合與搜索順序搜索

13、(Sequential Search)所謂順序搜索, 又稱線性搜索, 主要用于在線性結(jié)構(gòu)中進(jìn)行搜索。設(shè)若表中有 n 個對象，則順序搜索從表的先端 (或后端) 開始, 順序用各對象的關(guān)鍵碼與給定值 x 進(jìn)行比較, 直到找到與其值相等的對象, 則搜索成功; 給出該對象在表中的位置。若整個表都已檢測完仍未找到關(guān)鍵碼與x相等的對象, 則搜索失敗。給出失敗信息。25數(shù)據(jù)結(jié)構(gòu)要求集合與搜索int LinearSearch ( dataList A, DataType x ) /在數(shù)據(jù)表A.data1.n中順序搜索關(guān)鍵碼為 x/的數(shù)據(jù)對象, A.data0.key 作為控制搜索自動/結(jié)束的“監(jiān)視哨”使用 A

14、.data0.key = x; int; /將x送0號位置設(shè)置監(jiān)視哨 while ( A.datai.key != x ) i- ; /從后向前順序搜索 return i;設(shè)置“監(jiān)視哨”的順序搜索算法26數(shù)據(jù)結(jié)構(gòu)要求集合與搜索順序搜索的平均搜索長度 設(shè)搜索第 i 個元素的概率為 pi , 搜索到第 i 個元素所需比較次數(shù)為 ci , 則搜索成功的平均搜索長度:在順序搜索并設(shè)置“監(jiān)視哨”情形： ci = n- i +1, i = n, n-1, , 1，因此27數(shù)據(jù)結(jié)構(gòu)要求集合與搜索在等概率情形，pi = 1/n, i = 1, 2, , n。 在搜索不成功情形，ASLunsucc = n+1.

15、 28數(shù)據(jù)結(jié)構(gòu)要求集合與搜索順序搜索的遞歸算法int SequentSearch ( dataList A, dataType x, int& loc ) /在數(shù)據(jù)表 A.data0.n-1 中搜索其關(guān)鍵碼與/給定值匹配的對象, 函數(shù)返回其表中位置。/參數(shù) loc 是在表中開始搜索位置 if ( loc = A.n ) return -1; /搜索失敗 else if ( A.dataloc.key = x ) return loc; /搜索成功 else return SequentSearch ( A, x, loc+1 ); /遞歸搜索29數(shù)據(jù)結(jié)構(gòu)要求集合與搜索int SequentSe

16、arch ( dataList A, DataType x ) /在數(shù)據(jù)表 A.data0.n-1 中順序搜索關(guān)鍵碼為 x 的數(shù)據(jù)對象 for ( int i = 0; i+ ) if ( A.datai.key = x ) return i; /成功 else if ( A.datai.key x ) break; return -1; /順序搜索失敗, 返回失敗信息基于有序順序表的順序搜索算法30數(shù)據(jù)結(jié)構(gòu)要求集合與搜索有序順序表的順序搜索 ( 10, 20, 30, 40, 50, 60 )105060=20304031數(shù)據(jù)結(jié)構(gòu)要求集合與搜索基于有序順序表的折半搜索設(shè)n個對象存放在一個按其

17、關(guān)鍵碼從小到大排好了序的有序順序表中。折半搜索時, 先求位于搜索區(qū)間正中的對象的下標(biāo)mid，用其關(guān)鍵碼與給定值x比較: A.datamid.key = x, 搜索成功； A.datamid.key x, 把搜索區(qū)間縮小到 表的前半部分，繼續(xù)折半搜索； A.datamid.key x，把搜索區(qū)間縮小到表的后半部分，繼續(xù)折半搜索。如果搜索區(qū)間已縮小到一個對象，仍未找到想要搜索的對象，則搜索失敗。32數(shù)據(jù)結(jié)構(gòu)要求集合與搜索搜索成功的例子-1 0 1 3 4 6 8 10 1260 1 2 3 4 5 6 7 8搜索lowmidhigh6 6 8 10 125 6 7 8lowmidhigh665lo

18、wmidhigh633數(shù)據(jù)結(jié)構(gòu)要求集合與搜索搜索失敗的例子-1 0 1 3 4 6 8 10 1250 1 2 3 4 5 6 7 8搜索lowmidhigh5 6 8 10 125 6 7 8lowmidhigh655lowmidhigh534數(shù)據(jù)結(jié)構(gòu)要求集合與搜索int BinarySearch ( dataList A, DataType x, int low, int high ) int mid = -1; if ( low = high ) mid = ( low + high ) / 2; if ( A.datamid.key x )mid = BinarySearch ( A,

19、 x, low, mid -1 ); return mid;基于有序順序表的折半搜索遞歸算法35數(shù)據(jù)結(jié)構(gòu)要求集合與搜索int BinarySearch ( dataList A, DataType x ) int-1, low = 0, mid; while ( low = high ) mid = ( low + high ) / 2; if ( A.datamid.key x ) high = mid - 1; /左縮搜索區(qū)間 else return mid; /搜索成功 return -1; /搜索失敗基于有序順序表的折半搜索迭代算法36數(shù)據(jù)結(jié)構(gòu)要求集合與搜索有序順序表的折半搜索的判定樹

20、 ( 10, 20, 30, 40, 50, 60 )1050=30204060ASLunsucc = (2*1+3*6)/7 = 20/7 ASLsucc = (1+2*2+ 3*3)/6 = 14/6 37數(shù)據(jù)結(jié)構(gòu)要求集合與搜索折半搜索性能分析若設(shè) n = 2h-1，則描述折半搜索的判定樹是高度為 h-1 的滿二叉樹。 2h = n+1, h = log2(n+1)。第0層結(jié)點(diǎn)有1個, 搜索第0層結(jié)點(diǎn)要比較1次; 第1層結(jié)點(diǎn)有2個, 搜索第1層結(jié)點(diǎn)要比較2次; , 第 i (0 i h) 層結(jié)點(diǎn)有 2i 個, 搜索第 i 層結(jié)點(diǎn)要比較 i+1次，。假定每個結(jié)點(diǎn)的搜索概率相等，即 pi =

21、1/n，則搜索成功的平均搜索長度為38數(shù)據(jù)結(jié)構(gòu)要求集合與搜索可以用歸納法證明這樣39數(shù)據(jù)結(jié)構(gòu)要求集合與搜索定義 二叉搜索樹或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹： 每個結(jié)點(diǎn)都有一個作為搜索依據(jù)的關(guān)鍵碼(key)，所有結(jié)點(diǎn)的關(guān)鍵碼互不相同。 左子樹(如果存在)上所有結(jié)點(diǎn)的關(guān)鍵碼都小于根結(jié)點(diǎn)的關(guān)鍵碼。 右子樹(如果存在)上所有結(jié)點(diǎn)的關(guān)鍵碼都大于根結(jié)點(diǎn)的關(guān)鍵碼。 左子樹和右子樹也是二叉搜索樹。二叉搜索樹 ( Binary Search Tree )40數(shù)據(jù)結(jié)構(gòu)要求集合與搜索351545504025102030二叉搜索樹例結(jié)點(diǎn)左子樹上所有關(guān)鍵碼小于結(jié)點(diǎn)關(guān)鍵碼右子樹上所有關(guān)鍵碼大于結(jié)點(diǎn)關(guān)鍵碼注意：若

22、從根結(jié)點(diǎn)到某個葉結(jié)點(diǎn)有一條路徑，路徑左邊的結(jié)點(diǎn)的關(guān)鍵碼不一定小于路徑上的結(jié)點(diǎn)的關(guān)鍵碼。41數(shù)據(jù)結(jié)構(gòu)要求集合與搜索n 個結(jié)點(diǎn)的二叉搜索樹的數(shù)目【例】3 個結(jié)點(diǎn)的二叉搜索樹122133132123123123 132 213 231 312 32142數(shù)據(jù)結(jié)構(gòu)要求集合與搜索 二叉搜索樹的結(jié)構(gòu)定義typedef char DataType; /樹結(jié)點(diǎn)數(shù)據(jù)類型typedef struct node /搜索樹結(jié)點(diǎn)定義 DataType data; struct node *leftChild, *rightChild; BstNode;typedef BstNode *BST; /二叉搜索樹定義 如果對

23、一棵二叉搜索樹進(jìn)行中序遍歷，可以按從小到大的順序，將各結(jié)點(diǎn)關(guān)鍵碼排列起來，所以也稱二叉搜索樹為二叉排序樹。43數(shù)據(jù)結(jié)構(gòu)要求集合與搜索 在二叉搜索樹上進(jìn)行搜索，是一個從根結(jié)點(diǎn)開始，沿某一個分支逐層向下進(jìn)行比較判等的過程。它可以是一個遞歸的過程。二叉搜索樹上的搜索351545504025102030搜索45 搜索成功 搜索28搜索失敗44數(shù)據(jù)結(jié)構(gòu)要求集合與搜索假設(shè)想要在二叉搜索樹中搜索關(guān)鍵碼為x的元素，搜索過程從根結(jié)點(diǎn)開始。如果根指針為NULL，則搜索不成功；否則用給定值 x 與根結(jié)點(diǎn)的關(guān)鍵碼進(jìn)行比較：如果給定值等于根結(jié)點(diǎn)的關(guān)鍵碼，則搜索成功。 如果給定值小于根結(jié)點(diǎn)的關(guān)鍵碼，則繼續(xù)遞歸搜索根結(jié)點(diǎn)的

24、左子樹；否則。遞歸搜索根結(jié)點(diǎn)的右子樹。45數(shù)據(jù)結(jié)構(gòu)要求集合與搜索搜索成功時檢測指針停留在樹中某個結(jié)點(diǎn)。搜索不成功時檢測指針停留在某個外結(jié)點(diǎn)（失敗結(jié)點(diǎn)）。3515455025102030搜索22搜索4546數(shù)據(jù)結(jié)構(gòu)要求集合與搜索BstNode * Find ( BstNode *ptr, DataType x ) /二叉搜索樹的迭代的搜索算法 if ( ptr != NULL ) BstNode * p = ptr; /從根搜索 while ( p != NULL ) if ( p-data = x ) return p; if ( p-data rightChild; /右子樹 else p

25、= p-leftChild; /左子樹 return NULL; /搜索失敗 47數(shù)據(jù)結(jié)構(gòu)要求集合與搜索35154550402510203028插入新結(jié)點(diǎn)28二叉搜索樹的插入每次結(jié)點(diǎn)的插入，都要從根結(jié)點(diǎn)出發(fā)搜索插入位置，然后把 新結(jié)點(diǎn)作為葉結(jié)點(diǎn) 插入。為了向二叉搜索樹 中插入一個新元素， 必須先檢查這個元 素是否在樹中已經(jīng) 存在。48數(shù)據(jù)結(jié)構(gòu)要求集合與搜索在插入之前，先使用搜索算法在樹中檢查要插入元素有還是沒有。搜索成功: 樹中已有這個元素,不再插入。搜索不成功: 樹中原來沒有關(guān)鍵碼等于給定值的結(jié)點(diǎn)，把新元素加到搜索操作停止的地方。 遞歸的二叉搜索樹插入算法void Insert ( Data

26、Type x, BstNode * & ptr) /將新元素x插到以*ptr為根的二叉搜索樹中49數(shù)據(jù)結(jié)構(gòu)要求集合與搜索 if ( ptr = NULL ) /空二叉樹 ptr = new BstNode; /創(chuàng)建結(jié)點(diǎn) if ( ptr = NULL ) cout “存儲不足 data = x; ptr-leftChild = ptr-rightChild = NULL; else if ( x data ) /在左子樹插入 Insert ( x, ptr-leftChild ); else if ( x ptr-data ) /在右子樹插入 Insert ( x, ptr-rightChil

27、d );50數(shù)據(jù)結(jié)構(gòu)要求集合與搜索 輸入數(shù)據(jù)，建立二叉搜索樹的過程輸入數(shù)據(jù) 53, 78, 65, 17, 87, 09, 81, 15 53537853786553786517537865871753786509178753786581178709537865151787098151數(shù)據(jù)結(jié)構(gòu)要求集合與搜索void CreateBST ( BstNode *& T, DataType Refvalue ) /輸入數(shù)據(jù), 建立二叉搜索樹。RefValue 是輸入/結(jié)束標(biāo)志。這個值應(yīng)取不可能在輸入序列中/出現(xiàn)的值, 例如輸入序列的值都是正整數(shù)時, /取RefValue為0或負(fù)數(shù)。 dataType

28、 x; T = NULL; cin x; while ( x != RefValue ) if ( Find (T, x) = NULL ) Insert ( x, T ); cin x; 52數(shù)據(jù)結(jié)構(gòu)要求集合與搜索 同樣 3 個數(shù)據(jù) 1, 2, 3 ，輸入順序不同，建立起來的二叉搜索樹的形態(tài)也不同。這直接影響到二叉搜索樹的搜索性能。 如果輸入序列選得不好，會建立起一棵單支樹，使得二叉搜索樹的高度達(dá)到最大。 2, 1, 3 1, 2, 3 1, 3, 2 2, 3, 1 3, 1, 2 3, 2, 1 12311113222332353數(shù)據(jù)結(jié)構(gòu)要求集合與搜索二叉搜索樹的刪除在二叉搜索樹中刪除一

29、個結(jié)點(diǎn)時，必須將因刪除結(jié)點(diǎn)而斷開的二叉鏈表重新鏈接起來，同時確保二叉搜索樹的性質(zhì)不會失去。為保證在刪除后樹的搜索性能不至于降低，還需要防止重新鏈接后樹的高度增加。刪除葉結(jié)點(diǎn)，只需將其雙親結(jié)點(diǎn)指向它的指針清零，再釋放它即可。被刪結(jié)點(diǎn)缺右子樹，可以拿它的左子女結(jié)點(diǎn)頂替它的位置，再釋放它。54數(shù)據(jù)結(jié)構(gòu)要求集合與搜索被刪結(jié)點(diǎn)缺左子樹，可以拿它的右子女結(jié)點(diǎn)頂替它的位置，再釋放它。被刪結(jié)點(diǎn)左、右子樹都存在，可以在它的右子樹中尋找中序下的第一個結(jié)點(diǎn)(關(guān)鍵碼最小),用它的值填補(bǔ)到被刪結(jié)點(diǎn)中，再來處理這個結(jié)點(diǎn)的刪除問題。5378651787092345刪除45缺右子樹, 用左子女頂替53786517870923

30、55數(shù)據(jù)結(jié)構(gòu)要求集合與搜索8853788817940923刪除78缺左子樹, 用右子女頂替53948817092353788117940945刪除78在右子樹上找中序下第一個結(jié)點(diǎn)填補(bǔ)236553818817940945236556數(shù)據(jù)結(jié)構(gòu)要求集合與搜索 二叉搜索樹性能分析對于有 n 個關(guān)鍵碼的集合，其關(guān)鍵碼有 n! 種不同排列，可構(gòu)成不同二叉搜索樹有 (棵)用樹的搜索效率來評價這些二叉搜索樹。在樹中增加失敗結(jié)點(diǎn)(外部結(jié)點(diǎn)), 它們是搜索失敗時到達(dá)的結(jié)點(diǎn), 物理上實(shí)際不存在。增加了外部結(jié)點(diǎn)的二叉搜索樹稱為擴(kuò)充二叉搜索樹。57數(shù)據(jù)結(jié)構(gòu)要求集合與搜索在擴(kuò)充二叉搜索樹中 表示內(nèi)部結(jié)點(diǎn)，包含了關(guān)鍵碼集合

31、中的某一個關(guān)鍵碼； 表示外部結(jié)點(diǎn)，代表各關(guān)鍵碼間隔中的不在關(guān)鍵碼集合中的關(guān)鍵碼。在每兩個外部結(jié)點(diǎn)間必存在一個內(nèi)部結(jié)點(diǎn)。58數(shù)據(jù)結(jié)構(gòu)要求集合與搜索例，已知關(guān)鍵碼集合 a1, a2, a3 = do, if, to ，對應(yīng)搜索概率 p1, p2, p3, 在各搜索不成功間隔內(nèi)搜索概率分別為 q0, q1, q2, q3?？赡艿亩嫠阉鳂淙缦滤?。doiftodoiftoq0q1p1q2p2q3p3q0q1q2q3p1p2p3(a)(b)59數(shù)據(jù)結(jié)構(gòu)要求集合與搜索doifto擴(kuò)充二叉搜索樹q0q1p1q2p2q3p3doiftoq0q1p1q2p2q3p3(d)(c)doiftoq0q1p1q2p2

32、q3p3(e)60數(shù)據(jù)結(jié)構(gòu)要求集合與搜索 一棵擴(kuò)充二叉搜索樹的搜索成功的平均搜索長度ASLsucc可以定義為該樹所有內(nèi)部結(jié)點(diǎn)上的權(quán)值pi與搜索該結(jié)點(diǎn)時所需的關(guān)鍵碼比較次數(shù)ci (= li + 1)乘積之和： 搜索不成功的平均搜索長度ASLunsucc為樹中所有外部結(jié)點(diǎn)上權(quán)值qj與到達(dá)外部結(jié)點(diǎn)所需關(guān)鍵碼比較次數(shù)cj(= lj)乘積之和：61數(shù)據(jù)結(jié)構(gòu)要求集合與搜索(1) 相等搜索概率的情形 設(shè)樹中所有內(nèi)、外部結(jié)點(diǎn)的搜索概率都相等： pi = 1/3, 1 i 3 qj = 1/4，0 j 3 圖(a)：ASLsucc = 1/3*3+1/3*2+1/3*1 = 6/3 = 2 ASLunsucc

33、= 1/4*3*2+1/4*2+1/4*1 = 9/4 圖(b)：ASLsucc = 1/3*1+1/3*2*2 = 5/3 ASLunsucc = 1/4*2*4 = 2 圖(c) 圖(e)：ASLsucc = 2, ASLunsucc = 9/4 圖(b)的情形所得的平均搜索長度最小。 62數(shù)據(jù)結(jié)構(gòu)要求集合與搜索 一般把平均搜索長度達(dá)到最小的擴(kuò)充二叉搜索樹稱作最優(yōu)二叉搜索樹。 在相等搜索概率的情形下，所有內(nèi)部、外部結(jié)點(diǎn)的搜索概率都相等，視它們的權(quán)值都為 1。同時，第 k 層有 2k 個結(jié)點(diǎn)，k = 0, 1, 。則有 n 個內(nèi)部結(jié)點(diǎn)的擴(kuò)充二叉搜索樹的內(nèi)部路徑長度 I 至少等于序列 63數(shù)據(jù)

34、結(jié)構(gòu)要求集合與搜索 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 的前 n 項(xiàng)的和。 因此，最優(yōu)二叉搜索樹的搜索成功的平均搜索長度和搜索不成功的平均搜索長度分別為:(2) 不相等搜索概率的情形 設(shè)樹中所有內(nèi)、外部結(jié)點(diǎn)的搜索概率互不相等。64數(shù)據(jù)結(jié)構(gòu)要求集合與搜索 q0 = 0.15, q1 = 0.1, q2 = 0.05, q3 = 0.05 doiftodoiftoq3=(a)(b)圖(a)：ASLsucc， ASLunsucc。 ASL = ASLsucc + ASLunsucc。65數(shù)據(jù)結(jié)構(gòu)要求集合與搜索doifto q0=doi

35、fto(d)(c)圖(c) : ASLsucc = 0.5*1+0.1*2+0.05*3 = 0.85,ASLunsucc = 0.15*1+0.1*2+0.05*3+0.05*3 = 0.75.ASL圖(b) : ASL = 1.9; 圖(d) : ASL = 2.15; 66數(shù)據(jù)結(jié)構(gòu)要求集合與搜索doifto(e) 圖(e) : ASLsucc = 0.5*1 +0.05*2+0.1*3 = 0.9; ASLunsucc = 0.15*1+ 0.1*3+0.05*3+0.05*2 = 0.7; ASL = 0.9+0.7 = 1.6. 由此可知，圖(c)和圖(e)的情形下樹的平均搜索長度達(dá)

36、到最小，因此，圖(c)和圖(e)的情形是最優(yōu)二叉搜索樹。67數(shù)據(jù)結(jié)構(gòu)要求集合與搜索AVL樹 高度平衡的二叉搜索樹AVL樹的定義 一棵AVL樹或者是空樹，或者是具有下列性質(zhì)的二叉搜索樹：它的左子樹和右子樹都是AVL樹，且左子樹和右子樹的高度之差的絕對值不超過1。 高度不平衡 高度平衡ABCABCDEDE68數(shù)據(jù)結(jié)構(gòu)要求集合與搜索 結(jié)點(diǎn)的平衡因子balance (balance factor)每個結(jié)點(diǎn)附加一個數(shù)字, 給出該結(jié)點(diǎn)右子樹的高度減去左子樹的高度所得的高度差,這個數(shù)字即為結(jié)點(diǎn)的平衡因子balance AVL樹任一結(jié)點(diǎn)平衡因子只能取 -1, 0, 1如果一個結(jié)點(diǎn)的平衡因子的絕對值大于1,則這

37、棵二叉搜索樹就失去了平衡, 不再是AVL樹。如果一棵二叉搜索樹是高度平衡的, 且有 n 個結(jié)點(diǎn)，其高度可保持在O(log2n),平均搜索長度也可保持在O(log2n)。69數(shù)據(jù)結(jié)構(gòu)要求集合與搜索AVL樹的結(jié)構(gòu)定義typedef int DataType; /結(jié)點(diǎn)數(shù)據(jù)類型typedef struct node /AVL樹結(jié)點(diǎn)定義 DataType data; /結(jié)點(diǎn)數(shù)據(jù)域 int balance; /結(jié)點(diǎn)平衡因子域 struct node *leftChild, *rightChild; /結(jié)點(diǎn)左、右子女指針域 AVLNode;typedef AVLNode * AVLTree; /AVL樹70

38、數(shù)據(jù)結(jié)構(gòu)要求集合與搜索平衡化旋轉(zhuǎn)如果在一棵平衡的二叉搜索樹中插入一個新結(jié)點(diǎn)，造成了不平衡。此時必須調(diào)整樹的結(jié)構(gòu)，使之平衡化。平衡化旋轉(zhuǎn)有兩類： 單旋轉(zhuǎn) (左旋和右旋) 雙旋轉(zhuǎn) (左平衡和右平衡)每插入一個新結(jié)點(diǎn)時, AVL 樹中相關(guān)結(jié)點(diǎn)的平衡狀態(tài)會發(fā)生改變。因此, 在插入一 個新結(jié)點(diǎn)后，需要從插入位置沿通向根的路徑回溯，檢查各結(jié)點(diǎn)的平衡因子。71數(shù)據(jù)結(jié)構(gòu)要求集合與搜索如果在某一結(jié)點(diǎn)發(fā)現(xiàn)高度不平衡，停止回溯。從發(fā)生不平衡的結(jié)點(diǎn)起，沿剛才回溯的路徑取直接下兩層的結(jié)點(diǎn)。如果這三個結(jié)點(diǎn)處于一條直線上，則采用單旋轉(zhuǎn)進(jìn)行平衡化。單旋轉(zhuǎn)可按其方向分為左單旋轉(zhuǎn)和右單旋轉(zhuǎn), 其中一個是另一 個的鏡像，其方向與不

39、平衡的形狀相關(guān)。如果這三個結(jié)點(diǎn)處于一條折線上，則采用雙旋轉(zhuǎn)進(jìn)行平衡化。雙旋轉(zhuǎn)分為先左后右和先右后左兩類。72數(shù)據(jù)結(jié)構(gòu)要求集合與搜索右單旋轉(zhuǎn)左單旋轉(zhuǎn) 左右雙旋轉(zhuǎn)右左雙旋轉(zhuǎn)左單旋轉(zhuǎn) (RotateLeft )hhhACEBDhhh+1BACEDhhh+1CEABD+1+20+10073數(shù)據(jù)結(jié)構(gòu)要求集合與搜索右單旋轉(zhuǎn)左單旋轉(zhuǎn) 左右雙旋轉(zhuǎn)右左雙旋轉(zhuǎn)左單旋轉(zhuǎn) (RotateLeft )hhhACEBDhhh+1BACEDhhh+1CEABD+1+20+10074數(shù)據(jù)結(jié)構(gòu)要求集合與搜索在子樹E中插入新結(jié)點(diǎn)，該子樹高度增1導(dǎo)致結(jié)點(diǎn)A的平衡因子變成+2，出現(xiàn)不平衡。沿插入路徑檢查三個結(jié)點(diǎn)A、C和E。它們處于方向?yàn)椤啊钡闹本€上，需做左單旋轉(zhuǎn)。以結(jié)點(diǎn)C為旋轉(zhuǎn)軸，讓結(jié)點(diǎn)A反時針旋轉(zhuǎn)。右單旋轉(zhuǎn) (RotateRight )在左子樹D上插入新結(jié)點(diǎn)使其高度增1，導(dǎo)致結(jié)點(diǎn)A的平衡因子增到 -2，造成不平衡。為使樹恢復(fù)平衡，從A沿插入路徑連續(xù)取3 個結(jié)點(diǎn)A、B和D，它們處于一條方向?yàn)椤?”的直線上，需要做右