1、武漢科技大學(xué)Wuhan University of Science and Technology張 凱計(jì)算機(jī)學(xué)院 軟件工程系2019年3月12日:第第9 9章章 查找查找查找的根本概念靜態(tài)查找表動(dòng)態(tài)查找表哈希表:v動(dòng)態(tài)查找表動(dòng)態(tài)查找表 9.2 動(dòng)態(tài)查找表動(dòng)態(tài)查找表 特點(diǎn)：表構(gòu)造本身是在查找過(guò)程中動(dòng)態(tài)生成的，即對(duì)于給定值 key ，假設(shè)表中存在關(guān)鍵字等于 key 的記錄，那么查找勝利前往；否那么，插入關(guān)鍵字等于 key 的記錄。 :v動(dòng)態(tài)查找表動(dòng)態(tài)查找表 9.2 動(dòng)態(tài)查找表動(dòng)態(tài)查找表 動(dòng)態(tài)查找表主要有二叉樹(shù)構(gòu)造和樹(shù)構(gòu)造兩種類型。二叉樹(shù)構(gòu)造有二叉排序樹(shù)、平衡二叉樹(shù)等。樹(shù)構(gòu)造有B-樹(shù)、B+樹(shù)等。:v

2、二叉排序樹(shù)二叉排序樹(shù)9.2 動(dòng)態(tài)查找表動(dòng)態(tài)查找表定義：二叉排序樹(shù)或者是一棵空樹(shù)；或者是具有如下特性的二叉樹(shù)： 1假設(shè)它的左子樹(shù)不空，那么左子樹(shù)上一切結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值； 2假設(shè)它的右子樹(shù)不空，那么右子樹(shù)上一切結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值； 3它的左、右子樹(shù)也都分別是二叉排序樹(shù)。 :v二叉排序樹(shù)二叉排序樹(shù)9.2 動(dòng)態(tài)查找表動(dòng)態(tài)查找表45 12 53 3 37 61 99 24 90 78 caozhaodingchenwang二叉排序樹(shù) 例： :v二叉排序樹(shù)二叉排序樹(shù)9.2 動(dòng)態(tài)查找表動(dòng)態(tài)查找表45 12 53 3 4861 99 24 90 78 caozhaobangchenwang例：

3、非二叉排序樹(shù) 48bang:v二叉排序樹(shù)的查找算法二叉排序樹(shù)的查找算法9.2 動(dòng)態(tài)查找表動(dòng)態(tài)查找表 假設(shè)二叉排序樹(shù)為空，那么查找不勝利；否那么1)假設(shè)給定值等于根結(jié)點(diǎn)的關(guān)鍵字，那么查找勝利； 2)假設(shè)給定值小于根結(jié)點(diǎn)的關(guān)鍵字，那么繼續(xù)在左子樹(shù)上進(jìn)展查找； 3)假設(shè)給定值大于根結(jié)點(diǎn)的關(guān)鍵字，那么繼續(xù)在右子樹(shù)上進(jìn)展查找。 :v二叉排序樹(shù)二叉排序樹(shù)9.2 動(dòng)態(tài)查找表動(dòng)態(tài)查找表30802090854035883250查找關(guān)鍵字：50, 35, 90, 95 503590例： 從根結(jié)點(diǎn) 出發(fā)，沿著左 分支或右分支 逐層向下直至 關(guān)鍵字等于給 定值的結(jié)點(diǎn)。 查找勝利 從根結(jié)點(diǎn)出 發(fā)，沿著左分支 或右分支逐

4、層向 下直至指針指向 空樹(shù)為止。 查找失敗:v二叉排序樹(shù)的數(shù)據(jù)類型描畫(huà)二叉排序樹(shù)的數(shù)據(jù)類型描畫(huà)9.2 動(dòng)態(tài)查找表動(dòng)態(tài)查找表struct BtreeNode ElemType key; /關(guān)鍵字關(guān)鍵字 BtreeNode *lchild, *rchild;/左、右孩子左、右孩子 BtreeNode, *Bitree;:v二叉排序樹(shù)的查找算法描畫(huà)二叉排序樹(shù)的查找算法描畫(huà)9.2 動(dòng)態(tài)查找表動(dòng)態(tài)查找表BiTree SearchBST(BiTree T, KeyType key) /假設(shè)查找勝利，那么前往指向該數(shù)據(jù)元素結(jié)點(diǎn)的指針假設(shè)查找勝利，那么前往指向該數(shù)據(jù)元素結(jié)點(diǎn)的指針 /否那么前往空指針。否那么前

5、往空指針。 if ( (!T) | key = T- data.key ) return(T); else if ( key data.key) return(SearchBST (T- lchild, key); /在左子樹(shù)中繼續(xù)查在左子樹(shù)中繼續(xù)查找找 else return(SearchBST (T- rchild, key); /在右子樹(shù)中繼續(xù)查在右子樹(shù)中繼續(xù)查找找 / SearchBST:v二叉排序樹(shù)的插入算法二叉排序樹(shù)的插入算法9.2 動(dòng)態(tài)查找表動(dòng)態(tài)查找表1) 假設(shè)二叉排序樹(shù)為空樹(shù)，那么新插入的結(jié)點(diǎn)為根結(jié)點(diǎn)； 2) 假設(shè)二叉排序樹(shù)非空，那么新插入的結(jié)點(diǎn)必為一個(gè)新的葉子結(jié) 點(diǎn)，并且是查

6、找不勝利時(shí)查找途徑上訪問(wèn)的最后一個(gè)結(jié)點(diǎn) 的左孩子或右孩子結(jié)點(diǎn)。 :v二叉排序樹(shù)的插入算法二叉排序樹(shù)的插入算法9.2 動(dòng)態(tài)查找表動(dòng)態(tài)查找表例： 插入 40， 插入 50， 是 37 的右孩子。 是 53 的左孩子。 45 12 53 3 37 61 99 24 90 78 5040:v二叉排序樹(shù)的查找算法二叉排序樹(shù)的查找算法9.2 動(dòng)態(tài)查找表動(dòng)態(tài)查找表Status SearchBST (BiTree T, KeyType key, BiTree f, BiTree &p ) /假設(shè)查找勝利，那么指針假設(shè)查找勝利，那么指針 p 指向該數(shù)據(jù)元素結(jié)點(diǎn)，并前往指向該數(shù)據(jù)元素結(jié)點(diǎn)，并前往 TRUE

7、 /否那么指針?lè)衲敲粗羔?p 指向查找途徑上訪問(wèn)的最后一個(gè)結(jié)點(diǎn)，并前往指向查找途徑上訪問(wèn)的最后一個(gè)結(jié)點(diǎn)，并前往 FALSE /指針指針 f 指向指向 T 的雙親，其初始調(diào)用值為的雙親，其初始調(diào)用值為NULL。 if (!T) p = f; return FALSE; / 查找不勝利查找不勝利 else if ( key = T- data.key ) p = T; return TRUE; / 查找勝利查找勝利 else if ( key data.key ) SearchBST (T - lchild, key, T, p ); / 在左子樹(shù)中查找在左子樹(shù)中查找 else SearchBST

8、 (T- rchild, key, T, p ); / 在右子樹(shù)中查找在右子樹(shù)中查找 / SearchBST :v二叉排序樹(shù)的插入算法二叉排序樹(shù)的插入算法9.2 動(dòng)態(tài)查找表動(dòng)態(tài)查找表Status InsertBST(BiTree &T, ElemType e ) / 當(dāng)二叉排序樹(shù)當(dāng)二叉排序樹(shù) T 中不存在關(guān)鍵字等于中不存在關(guān)鍵字等于 e.key 的數(shù)據(jù)元素時(shí)，的數(shù)據(jù)元素時(shí)， / 插入插入 e 并前往并前往 TRUE，否那么前往，否那么前往 FALSE if (!SearchBST ( T, e.key, NULL, p ) / 查找不勝利查找不勝利 s = (BiTree) mallo

9、c (sizeof (BiTNode); s - data = e; s - lchild = s - rchild = NULL; if ( !p ) T = s; / 插入插入 s 為新的根結(jié)點(diǎn)為新的根結(jié)點(diǎn) else if ( e.key data.key ) p - lchild = s; / 插入插入 s 為左孩子為左孩子 else p - rchild = s; / 插入插入 s 為右孩子為右孩子 return TRUE; else return FALSE; / 樹(shù)中已有關(guān)鍵字一樣的結(jié)點(diǎn)，不再插入樹(shù)中已有關(guān)鍵字一樣的結(jié)點(diǎn)，不再插入 / Insert BST :v二叉排序樹(shù)的生成二叉

10、排序樹(shù)的生成9.2 動(dòng)態(tài)查找表動(dòng)態(tài)查找表例：設(shè)查找的關(guān)鍵字序列為 45, 24, 53, 45, 12, 24, 90 可生成二叉排序樹(shù)如下： 從空樹(shù)開(kāi)場(chǎng)，經(jīng)過(guò)一系列的查找操作、插入操作之后，可生成一棵二叉排序樹(shù)。 4553249012:v二叉排序樹(shù)的建立二叉排序樹(shù)的建立9.2 動(dòng)態(tài)查找表動(dòng)態(tài)查找表例：關(guān)鍵字序列 10、18、3、8、12、2、7、3 生成二叉排序樹(shù)過(guò)程。1018381227注：二叉排序樹(shù)與關(guān)鍵字陳列順序有關(guān)，順序不同，得到的二叉排序樹(shù)也不同:v二叉排序樹(shù)的建立的算法二叉排序樹(shù)的建立的算法9.2 動(dòng)態(tài)查找表動(dòng)態(tài)查找表反復(fù)調(diào)用二叉排序樹(shù)的插入算法即可Bitree Creat (i

11、nt n) /建立含有n個(gè)結(jié)點(diǎn)的二叉排序樹(shù) Bitree T= NULL; for ( int i=1; ix; /輸入關(guān)鍵字序列 InsertBST ( T, x); return BST;:v中序遍歷二叉排序樹(shù)中序遍歷二叉排序樹(shù)9.2 動(dòng)態(tài)查找表動(dòng)態(tài)查找表15303778535063902970:v二叉排序樹(shù)分析二叉排序樹(shù)分析9.2 動(dòng)態(tài)查找表動(dòng)態(tài)查找表中序遍歷二叉排序樹(shù)可得到一個(gè)關(guān)鍵字的有序序列。 一個(gè)無(wú)序序列可經(jīng)過(guò)構(gòu)造二叉排序樹(shù)而變成一個(gè)有序序列。構(gòu)造樹(shù)的過(guò)程就是對(duì)無(wú)序序列進(jìn)展排序的過(guò)程。 插入的結(jié)點(diǎn)均為葉子結(jié)點(diǎn)，故無(wú)需挪動(dòng)其他結(jié)點(diǎn)。相當(dāng)于在有序序列上插入記錄而無(wú)需挪動(dòng)其他記錄。 :v

12、二叉排序樹(shù)上的刪除二叉排序樹(shù)上的刪除9.2 動(dòng)態(tài)查找表動(dòng)態(tài)查找表 對(duì)于二叉排序樹(shù)，刪去樹(shù)上一個(gè)結(jié)點(diǎn)相當(dāng)于刪去有序序列中的一個(gè)記錄，在刪除某個(gè)結(jié)點(diǎn)之后照舊要堅(jiān)持二叉排序樹(shù)的特性。如何在二叉排序樹(shù)上刪去一個(gè)結(jié)點(diǎn)呢如何在二叉排序樹(shù)上刪去一個(gè)結(jié)點(diǎn)呢? :v二叉排序樹(shù)上的刪除二叉排序樹(shù)上的刪除9.2 動(dòng)態(tài)查找表動(dòng)態(tài)查找表分三種情況進(jìn)展討論： (1)假設(shè)*p結(jié)點(diǎn)為葉子結(jié)點(diǎn)，即PL和PR均為空樹(shù)。 由于刪去葉子結(jié)點(diǎn)不破壞整棵樹(shù)的構(gòu)造，那么只需修正其雙親結(jié)點(diǎn)的指針。 (2)假設(shè)*p結(jié)點(diǎn)只需左子樹(shù)PL或者只需右子樹(shù)PR。 只需令PL或PR直接成為其雙親結(jié)點(diǎn)*f的左子樹(shù)即可。(3)假設(shè)*p結(jié)點(diǎn)的左子樹(shù)和右子樹(shù)均不

13、空。 :v二叉排序樹(shù)上的刪除二叉排序樹(shù)上的刪除9.2 動(dòng)態(tài)查找表動(dòng)態(tài)查找表2)P只需左子樹(shù)或右子樹(shù)： P只需左子樹(shù)，用P的左孩子替代P； SPPLQSPLQSPPLQSPLQ:v二叉排序樹(shù)上的刪除二叉排序樹(shù)上的刪除9.2 動(dòng)態(tài)查找表動(dòng)態(tài)查找表2)P只需左子樹(shù)或右子樹(shù)： P只需右子樹(shù)，用P的右孩子替代P； SPPRQSPRQSPPRQSPRQ:v二叉排序樹(shù)上的刪除二叉排序樹(shù)上的刪除9.2 動(dòng)態(tài)查找表動(dòng)態(tài)查找表3)P左、右子樹(shù)均非空 用P的直接前驅(qū)(或直接后繼)取代PFPCDAQBSCGEPACBQCSPEDGF中序遍歷從小到大陳列ACBQCSPEDGF:v二叉排序樹(shù)上的刪除二叉排序樹(shù)上的刪除9.

14、2 動(dòng)態(tài)查找表動(dòng)態(tài)查找表3)P左、右子樹(shù)均非空 用P的直接前驅(qū)(或直接后繼)取代PFPCDAQBSCGEPFPCDAQBCGESS:v二叉排序樹(shù)上的刪除二叉排序樹(shù)上的刪除9.2 動(dòng)態(tài)查找表動(dòng)態(tài)查找表3)P左、右子樹(shù)均非空 用P的直接前驅(qū)(或直接后繼)取代PFPCDAQBSCGEPFPCDAQBGEESC:v二叉排序樹(shù)的刪除算法二叉排序樹(shù)的刪除算法9.2 動(dòng)態(tài)查找表動(dòng)態(tài)查找表Status DeleteBST(BiTree &T, KeyType key) if(!T) return FALSE; /不存在關(guān)鍵字等于不存在關(guān)鍵字等于key的數(shù)據(jù)元素的數(shù)據(jù)元素 else if EQ(key,

15、 T-key) return Delete(T); /查找勝利查找勝利 else if LT(key，T-key) return DeleteBST (T-lchild,key); else return DeleteBST (T-rchild,key); /DelectBST:v二叉排序樹(shù)的刪除算法二叉排序樹(shù)的刪除算法9.2 動(dòng)態(tài)查找表動(dòng)態(tài)查找表Status Delete (BiTree &p) if(!p-rchild) /右子樹(shù)空那么只需重接它的左子樹(shù)右子樹(shù)空那么只需重接它的左子樹(shù) q=p; p=p-lchild; free(q); else if (!p-lchild) /左子

16、樹(shù)空那么只需重接它的右子樹(shù)左子樹(shù)空那么只需重接它的右子樹(shù) q=p; p=p-rchild; free(q); else q=p; s=p-lchild; while (s-rchild) q=s; s=s-lchild; /轉(zhuǎn)左轉(zhuǎn)左,然后向右到盡頭然后向右到盡頭 p-data=s-data; if(q!=p) q-rchild=s-lchild; else q-lchild=s-lchild; delete s; Return TRUE; /delete:v二叉排序樹(shù)的查找分析二叉排序樹(shù)的查找分析 9.2 動(dòng)態(tài)查找表動(dòng)態(tài)查找表二叉排序樹(shù)上查找某關(guān)鍵字等于給定值的結(jié)點(diǎn)過(guò)程，其實(shí)就是走了一條從根到

17、該結(jié)點(diǎn)的途徑。 30802090854035883250查找關(guān)鍵字：35 35比較的關(guān)鍵字次數(shù) 此結(jié)點(diǎn)所在層次數(shù) 最多的比較次數(shù) 樹(shù)的深度 :v二叉排序樹(shù)的平均查找長(zhǎng)度二叉排序樹(shù)的平均查找長(zhǎng)度9.2 動(dòng)態(tài)查找表動(dòng)態(tài)查找表452412375393(45, 24, 53, 12, 37, 93) 114(1 223 3 3)66ASL 534512243793114(1 223 3 3)66ASL 折半查找斷定樹(shù) 二叉排序樹(shù) :v二叉排序樹(shù)的平均查找長(zhǎng)度二叉排序樹(shù)的平均查找長(zhǎng)度9.2 動(dòng)態(tài)查找表動(dòng)態(tài)查找表114(1 223 3 3)66ASL (12, 24, 37, 45, 53, 93) 37

18、1245245393452412375393121(1 23456)66ASL 折半查找斷定樹(shù) 二叉排序樹(shù) 含有含有 n 個(gè)結(jié)點(diǎn)的二叉排序樹(shù)的平均查找長(zhǎng)度和樹(shù)的形狀有關(guān)個(gè)結(jié)點(diǎn)的二叉排序樹(shù)的平均查找長(zhǎng)度和樹(shù)的形狀有關(guān) :v二叉排序樹(shù)的查找分析二叉排序樹(shù)的查找分析 9.2 動(dòng)態(tài)查找表動(dòng)態(tài)查找表最壞情況：插入的 n 個(gè)元素從一開(kāi)場(chǎng)就有序， 變成單支樹(shù)的形狀！ 此時(shí)樹(shù)的深度為 n; ASL = (n + 1) / 2 查找效率與順序查找情況一樣。 最好情況： ASL=log 2(n + 1) 1; 樹(shù)的深度為：log 2n + 1; 與折半查找中的斷定樹(shù)一樣。 形狀比較平衡。 452412375393

19、452412375393:v二叉排序樹(shù)的查找分析二叉排序樹(shù)的查找分析 9.2 動(dòng)態(tài)查找表動(dòng)態(tài)查找表 設(shè)每種樹(shù)態(tài)出現(xiàn)概率一樣，查找每個(gè)關(guān)鍵字也是等概率的，那么有 n 個(gè)關(guān)鍵字的二叉排序樹(shù)的平均查找長(zhǎng)度12(1)logASLnn 由此可見(jiàn)，在隨機(jī)的情況下，二叉排序樹(shù)的ASL和logn是等數(shù)量級(jí)的。 問(wèn)題：如何提高形狀不平衡的二叉排序樹(shù)的查找效率？ 處理方法：做“平衡化處置，即盡量讓二叉樹(shù)的外形平衡！ :v平衡二叉樹(shù)平衡二叉樹(shù)9.2 動(dòng)態(tài)查找表動(dòng)態(tài)查找表 平衡二叉樹(shù)又稱 AVL樹(shù)，它是具有如下性質(zhì)的二叉樹(shù)： 即： |左子樹(shù)深度右子樹(shù)深度| 1u 左、右子樹(shù)是平衡二叉樹(shù)；u 一切結(jié)點(diǎn)的左、右子樹(shù)深度之

20、差的絕對(duì)值 1。 :v例：判別以下二叉樹(shù)能否例：判別以下二叉樹(shù)能否 AVL 樹(shù)？樹(shù)？ 9.2 動(dòng)態(tài)查找表動(dòng)態(tài)查找表非平衡二叉樹(shù) 1-100-110平衡二叉樹(shù) 0012-10:v平衡二叉樹(shù)平衡二叉樹(shù)9.2 動(dòng)態(tài)查找表動(dòng)態(tài)查找表 為了方便起見(jiàn)，給每個(gè)結(jié)點(diǎn)附加一個(gè)數(shù)字， 數(shù)字=該結(jié)點(diǎn)左子樹(shù)與右子樹(shù)的深度差。這個(gè)數(shù)字稱為結(jié)點(diǎn)的平衡因子。這樣就可得到AVL樹(shù)的其它性質(zhì)任一結(jié)點(diǎn)的平衡因子只能取：-1、0 或 1；假設(shè)樹(shù)中恣意一個(gè)結(jié)點(diǎn)的平衡因子的絕對(duì)值大于 1，那么這棵二叉樹(shù)就失去平衡。 對(duì)于一棵有 n 個(gè)結(jié)點(diǎn)的 AVL 樹(shù)，其深度和 log n 同數(shù)量級(jí)， ASL 也和 log n 同數(shù)量級(jí)。 :v平衡二

21、叉樹(shù)平衡二叉樹(shù)9.2 動(dòng)態(tài)查找表動(dòng)態(tài)查找表 假設(shè)在一棵AVL樹(shù)中插入一個(gè)新結(jié)點(diǎn)，就有能夠呵斥失衡，此時(shí)必需重新調(diào)整樹(shù)的構(gòu)造，使之恢復(fù)平衡。我們稱調(diào)整平衡過(guò)程為平衡旋轉(zhuǎn)。平衡旋轉(zhuǎn)可以歸納為四類：v LL平衡旋轉(zhuǎn)v RR平衡旋轉(zhuǎn)v LR平衡旋轉(zhuǎn)v RL平衡旋轉(zhuǎn):v平衡二叉樹(shù)平衡二叉樹(shù)9.2 動(dòng)態(tài)查找表動(dòng)態(tài)查找表 假設(shè)在一棵AVL樹(shù)中插入一個(gè)新結(jié)點(diǎn)，就有能夠呵斥失衡，此時(shí)必需重新調(diào)整樹(shù)的構(gòu)造，使之恢復(fù)平衡。我們稱調(diào)整平衡過(guò)程為平衡旋轉(zhuǎn)。平衡旋轉(zhuǎn)可以歸納為四類：v LL平衡旋轉(zhuǎn)v RR平衡旋轉(zhuǎn)v LR平衡旋轉(zhuǎn)v RL平衡旋轉(zhuǎn):v平衡二叉樹(shù)平衡二叉樹(shù)9.2 動(dòng)態(tài)查找表動(dòng)態(tài)查找表假設(shè)在 A 的左子樹(shù)的左子樹(shù)上插入 結(jié)點(diǎn)，使 A 的平衡因子從 1 添加 至 2， 需求進(jìn)展一次順時(shí)針旋轉(zhuǎn)。 (以 B 為旋轉(zhuǎn)軸 1) LL 平衡旋轉(zhuǎn)： CBA A:v平衡二叉樹(shù)平衡二叉樹(shù)9.2 動(dòng)態(tài)查找表動(dòng)態(tài)查找表假設(shè)在 A 的右子樹(shù)的右子樹(shù)上插入 結(jié)點(diǎn)，使 A