【正文】 7 13 索引表 查 38 Data Structure Page 36 2022/1/4 ? 查找成功的平均查找長(zhǎng)度 bs b wbwASL L LLL??其 中 ： — — 查 找 索 引 表 確 定 所 在 塊 的 平 均 查 找 長(zhǎng) 度— — 在 塊 中 查 找 元 素 的 平 均 查 找 長(zhǎng) 度n b s若 將 表 長(zhǎng) 為 的 表 平 均 分 成 塊 ， 每 塊 含 個(gè) 記 錄 ， 并 設(shè) 表 中 每 個(gè) 記 錄 的查 找 概 率 相 等 ， 則 ：1121 1 1 1 1( 1 ) ( ) 12 2 2( 2) l og ( 1 )2bsbsjibsb s nASL j i sb s snsASLs????? ? ? ? ? ? ?? ? ???用 順 序 查 找 確 定 所 在 塊 ：用 折 半 查 找 確 定 所 在 塊 ：性能分析 Data Structure Page 37 2022/1/4 ?索引順序表的特點(diǎn) ? 平均查找長(zhǎng)度介于順序表和有序表之間； ? 表的結(jié)構(gòu)比較靈活 ? 例如，存儲(chǔ)記錄的線性表可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，且整個(gè)表不需要有序，可便于插入和刪除； ? 又如，索引順序表中的 “ 索引 ” 不一定按 “ 塊內(nèi)最大值 ” 建立，而是可以根據(jù)靜態(tài)查找表的特點(diǎn)建立 “ 分類索引 ” ； ? 再如，在查找表的記錄數(shù)眾多時(shí)還可建立 多層索引 等。 對(duì)給定值 k， 若查找成功 ， 則返回；否則 ， 在表中插入關(guān)鍵字等于 k的記錄 。 ? 動(dòng)態(tài)查找表的抽象數(shù)據(jù)類型定義 ADT DynamicSearchTable { 數(shù)據(jù)對(duì)象 D： D是具有相同特性的數(shù)據(jù)元素的集合。 數(shù)據(jù)關(guān)系 R：數(shù)據(jù)元素同屬一個(gè)集合。DT)。 DestroyDSTable(amp。 初始條件：動(dòng)態(tài)查找表 DT存在； 操作結(jié)果：銷毀動(dòng)態(tài)查找表 DT。 初始條件：動(dòng)態(tài)查找表 DT存在， kval 為和關(guān)鍵字類型相同的 給定值； 操作結(jié)果：若 DT中存在其關(guān)鍵字等于 kval 的數(shù)據(jù)元素，則函 數(shù)值為該元素的值或在表中的位置，否則為 “ 空 ” 。DT, e)。 DeleteDSTable(amp。 初始條件：動(dòng)態(tài)查找表 DT存在， kval 為和關(guān)鍵字類型相同的給 定值； 操作結(jié)果：若 DT中存在其關(guān)鍵字等于 kval 的數(shù)據(jù)元素，則刪 除之。 初始條件：動(dòng)態(tài)查找表 DT存在， Visit 是對(duì)結(jié)點(diǎn)操作的應(yīng)用函 數(shù)； 操作結(jié)果：按某種次序?qū)?DT的每個(gè)結(jié)點(diǎn)調(diào)用函數(shù) visit()一次且 至多一次。 } ADT DynamicSearchTable Data Structure Page 41 2022/1/4 二叉排序樹和平衡二叉樹 ?二叉排序樹 ? 定義 ? 二叉排序樹 或?yàn)橐豢每諛?， 或?yàn)榫哂腥缦滦再|(zhì)的二叉樹： ? 若它的左子樹不空 ， 則 左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值 ； ? 若它的右子樹不空 ， 則 右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值 ； ? 它的 左右子樹也分別是二叉排序樹 。 45 12 53 3 27 24 100 61 90 78 查找關(guān)鍵字等于 100的記錄 Data Structure Page 46 2022/1/4 ? 二叉排序樹的查找 若二叉排序樹為空，則查找不成功；否則 ? 若給定值等于根結(jié)點(diǎn)的關(guān)鍵字，則查找成功； ? 若給定值小于根結(jié)點(diǎn)的關(guān)鍵字，則繼續(xù)在左子樹上進(jìn)行查找； ? 若給定值大于根結(jié)點(diǎn)的關(guān)鍵字，則繼續(xù)在右子樹上進(jìn)行查找。 45 12 53 3 27 24 100 61 90 78 查找關(guān)鍵字等于 100的記錄 Data Structure Page 48 2022/1/4 ? 二叉排序樹的查找 若二叉排序樹為空，則查找不成功；否則 ? 若給定值等于根結(jié)點(diǎn)的關(guān)鍵字，則查找成功； ? 若給定值小于根結(jié)點(diǎn)的關(guān)鍵字，則繼續(xù)在左子樹上進(jìn)行查找； ? 若給定值大于根結(jié)點(diǎn)的關(guān)鍵字，則繼續(xù)在右子樹上進(jìn)行查找。 45 12 53 3 27 24 100 61 90 78 查找關(guān)鍵字等于 40的記錄 Data Structure Page 50 2022/1/4 ? 二叉排序樹的查找 若二叉排序樹為空，則查找不成功；否則 ? 若給定值等于根結(jié)點(diǎn)的關(guān)鍵字，則查找成功； ? 若給定值小于根結(jié)點(diǎn)的關(guān)鍵字，則繼續(xù)在左子樹上進(jìn)行查找； ? 若給定值大于根結(jié)點(diǎn)的關(guān)鍵字，則繼續(xù)在右子樹上進(jìn)行查找。 45 12 53 3 27 24 100 61 90 78 查找關(guān)鍵字等于 40的記錄 Data Structure Page 52 2022/1/4 ? 二叉排序樹的查找 若二叉排序樹為空，則查找不成功；否則 ? 若給定值等于根結(jié)點(diǎn)的關(guān)鍵字，則查找成功； ? 若給定值小于根結(jié)點(diǎn)的關(guān)鍵字，則繼續(xù)在左子樹上進(jìn)行查找； ? 若給定值大于根結(jié)點(diǎn)的關(guān)鍵字，則繼續(xù)在右子樹上進(jìn)行查找。 Data Structure Page 53 2022/1/4 算法 BiTree SearchBST (BSTree T, KeyType key){ // 根指針 T所指二叉查找樹中遞歸查找關(guān)鍵字等于 key的數(shù)據(jù)元素 , // 若查找成功，則返回指向該數(shù)據(jù)元素結(jié)點(diǎn)的指針，否則返回空指針。amp。 // 查找結(jié)束 else if LT(key, T) return (SearchBST(T))。 // 在右子樹中繼續(xù)查找 } // SearchBST Data Structure Page 54 2022/1/4 ? 二叉排序樹的插入 用遞歸過(guò)程實(shí)現(xiàn)在一棵二叉排序樹中插入一個(gè)結(jié)點(diǎn) ? 若 二叉排序樹為空 ，則 新結(jié)點(diǎn)作為 二叉排序樹的 根結(jié)點(diǎn) ； ? 若給定結(jié)點(diǎn)的 關(guān)鍵字值小于根結(jié)點(diǎn)關(guān)鍵字值 ，則 插入在左子樹 上； ? 若給定結(jié)點(diǎn)的 關(guān)鍵字值大于根結(jié)點(diǎn)關(guān)鍵字值 ，則 插入在右子樹 上。 45 12 53 3 27 24 100 61 90 78 59 Data Structure Page 57 2022/1/4 二叉排序樹的查找算法的修改 Status SearchBST(BiTree T, KeyType key, BiTree f, BiTree amp。 if (!T) { p=f。} // 查找不成功 else if EQ(key, T){ p=T。} // 查找成功 else if LT(key,T) return SearchBST(T,T,p)。 // 在右子樹中繼續(xù)查找 } // SearchBST Data Structure Page 58 2022/1/4 二叉排序樹的插入算法 Status InsertBST(BiTree amp。 if (!SearchBST ( T, , NULL, p ) { // 查找不成功 s = (BiTree) malloc (sizeof (BiTNode))。 // 存儲(chǔ)分配失敗 sdata = e。 if ( !p ) T = s。 // 被插結(jié)點(diǎn) *s 為 *p 的左孩子 else prchild = s。 } // if else return FALSE。 ? 設(shè)關(guān)鍵字序列 {10,18,3,8,12,2,7,3}，初始構(gòu)造二叉樹。 ?分四種情況討論： ? 被刪結(jié)點(diǎn)為 “ 葉子 ” 此時(shí)刪除該結(jié)點(diǎn)不影響其它結(jié)點(diǎn)之間的關(guān)系，因此可以直接刪除，即僅需修改其雙親結(jié)點(diǎn)的相應(yīng)指針即可； S P K Q S P Q 中序遍歷： K P S Q 中序遍歷： P S Q Data Structure Page 61 2022/1/4 ? 被刪結(jié)點(diǎn)只有左子樹 只需要將其左子樹直接鏈接到其雙親結(jié)點(diǎn)成為為其雙親的子樹即可； S P PL Q 中序遍歷： PL P S Q S PL Q 中序遍歷： PL S Q Data Structure Page 62 2022/1/4 ? 被刪結(jié)點(diǎn)只有左子樹 只需要將其左子樹直接鏈接到其雙親結(jié)點(diǎn)成為為其雙親的子樹即可； 中序遍歷： Q S PL P 中序遍歷： Q S PL S Q PL P S Q PL Data Structure Page 63 2022/1/4 ? 被刪結(jié)點(diǎn)只有右子樹 只需要將其右子樹直接鏈接到其雙親結(jié)點(diǎn)成為為其雙親的子樹即可； 中序遍歷： P PR S Q 中序遍歷： PR S Q S PR Q S P PR Q Data Structure Page 64 2022/1/4 ? 被刪結(jié)點(diǎn)只有右子樹 只需要將其右子樹直接鏈接到其雙親結(jié)點(diǎn)成為為其雙親的子樹即可； 中序遍歷： Q S P PR 中序遍歷： Q S PR S Q PR S Q PR P Data Structure Page 65 2022/1/4 ? 被刪結(jié)點(diǎn)的左右子樹均不空 被刪結(jié)點(diǎn)的數(shù)據(jù)元素賦值為它的 前驅(qū) ，然后從二叉查找樹上刪去這個(gè) 前驅(qū) 結(jié)點(diǎn)。 CL， C …… QL， Q， SL， S， P， PR， F CL C …… QL Q SL S PR F F P C PR CL Q QL S SL F S C PR CL Q QL SL Data Structure Page 67 2022/1/4 算法 Status DeleteBST (BiTree amp。 // 不存在關(guān)鍵字等于 key的數(shù)據(jù)元素 else { if (EQ(key,T) return Delete (T)。 // 返回在左子樹上查找的結(jié)果 else return DeleteBST( Trchild, key )。p ){ // 從二叉排序樹中刪除結(jié)點(diǎn) p，并重接它的左或右子樹 if (!prchild) // 右子樹為空，只需重接它的左子樹 { q = p。 free(q)。 p = prchild。 } else { // 左右子樹均不空 q = p。 while (!srchild) { q = s。 } //轉(zhuǎn)左，然后向右到盡頭 pdata = sdata。 // 重接 *q 的右子樹 else qlchild = slchild。 } } // Delete Data Structure Page 69 2022/1/4 80 50 120 60 110 150 55 70 53 80 60 120 110 150 55 70 53 80 55 120 110 150 53 70 刪除 50 Data Structure Page 70 2022/1/4 10 4 25 8 13 6 5 8 4 25 6 13 5 8 4 25 5 13 刪除 6 刪除 10 Data Structure Page 71 2022/1/4 二叉排序樹的查找分析 ?n個(gè)結(jié)點(diǎn)的二叉排序樹不唯一，由關(guān)鍵字插入的先后次序決定。 關(guān)鍵字序列 (45,24,53,12,37,93)構(gòu)成二叉排序樹。 ?二叉排序樹的平均查找長(zhǎng)度與樹的形態(tài)（深度）有關(guān)。 37 24 45 12 53 在查找概率相等的情況下， 1 2 1( 1 2 3 4 5 6 )66A S L ? ? ? ? ? ? ?93 Data Structure Page 73 2022/1/4 ?關(guān)鍵字輸入序列 ? 最差的情況 ? 二叉排序樹為單支樹，深度為 n ? 最好的情況 ? 二叉排序樹和折半查找判定樹相同，深度為 ?log2n?+1 ?在動(dòng)態(tài)生成二叉排序樹的過(guò)程中，進(jìn)行平衡化處理，使之成為平衡二叉樹。 Data Structure Page 74 2022/1/4 平衡二叉樹