數(shù)據(jù)結(jié)構(gòu)（從概念到算法）課件

第8章查找010203目錄CONTENTS04查找概述線性表的查找技術(shù)樹表的查找技術(shù)散列表的查找技術(shù)05本章小結(jié)01PART查找概述（1）查找表：查找表是由同一類型數(shù)據(jù)元素（或記錄）構(gòu)成的集合，例如電話號(hào)碼簿和字典都可以看作一張查找表。查找表可以根據(jù)實(shí)際情況采取不同的數(shù)據(jù)結(jié)構(gòu)來(lái)表示，例如線性表、樹表以及散列表等。（2）關(guān)鍵字：關(guān)鍵字是可以標(biāo)識(shí)數(shù)據(jù)元素的數(shù)據(jù)項(xiàng)。若一個(gè)關(guān)鍵字可以唯一標(biāo)識(shí)一個(gè)數(shù)據(jù)元素，則稱其為主關(guān)鍵字（PrimaryKey）。若一個(gè)關(guān)鍵字可以識(shí)別若干數(shù)據(jù)元素，則稱其為次關(guān)鍵字（SecondaryKey）。當(dāng)數(shù)據(jù)元素中只有一個(gè)數(shù)據(jù)項(xiàng)時(shí)，其關(guān)鍵字即為該數(shù)據(jù)元素的值。8.1.1查找基本概念查找概述（3）查找：查找是根據(jù)給定的某個(gè)值，確定查找表中是否存在關(guān)鍵字等于該值的記錄或數(shù)據(jù)元素。若表中存在這樣一個(gè)記錄，則稱查找成功，否則稱查找失敗。若查找成功，則返回該數(shù)據(jù)元素的全部信息或返回該數(shù)據(jù)元素在表中的位置；若查找失敗，則返回空值或空指針。（4）靜態(tài)查找表：靜態(tài)查找表對(duì)查找表的操作僅限于查找和檢索，即靜態(tài)查找表的內(nèi)容不允許發(fā)生改變。（5）動(dòng)態(tài)查找表：動(dòng)態(tài)查找表對(duì)查找表的操作不僅允許執(zhí)行查找和檢索操作，還允許在查找過(guò)程中插入或刪除表中的元素，即動(dòng)態(tài)查找表的內(nèi)容允許發(fā)生改變。8.1.1查找基本概念查找概述

8.1.2查找操作性能分析02PART線性表的查找技術(shù)8.2.1順序查找算法對(duì)于以線性表表示的查找表，我們很容易想到順序查找的思想，即從表的一端開始，順序掃描線性表，依次將掃描到的結(jié)點(diǎn)關(guān)鍵字值與給定關(guān)鍵字（key）值進(jìn)行比較。若當(dāng)前掃描到的記錄關(guān)鍵字值與key相等，則稱查找成功；若掃描到表的另一端還沒(méi)有找到關(guān)鍵字相同的記錄，則稱查找失敗。順序查找既適用于順序表，也適用于鏈表。數(shù)據(jù)元素定義如下。順序表ST的類型定義如下。線性表的查找技術(shù)8.2.1順序查找算法順序查找算法如下。

線性表的查找技術(shù)8.2.2折半查找算法折半查找也稱為二分查找，它是一種效率較高的查找方法。但是，折半查找只適用于有序表，即表中的各個(gè)數(shù)據(jù)元素關(guān)鍵字是完全有序排列的，且僅限于順序存儲(chǔ)結(jié)構(gòu)（對(duì)線性鏈表無(wú)法有效進(jìn)行折半查找）。在本小節(jié)中，假設(shè)順序表的數(shù)據(jù)元素都是升序排列的。折半查找算法思想如下。（1）將查找表中處于中間位置的數(shù)據(jù)元素關(guān)鍵字值與要查找的key值進(jìn)行比較，如果二者相等，則查找成功，返回該中間位置的元素序號(hào)。（2）如果二者不相等，則進(jìn)一步比較這兩個(gè)元素的大小。如果該中間元素的關(guān)鍵字值大于key，則將當(dāng)前序列的前半部分作為新的待查序列（因?yàn)楹蟀氩糠值乃性囟即笥谀繕?biāo)元素，可以全都排除），否則，將當(dāng)前序列的后半部分作為新的待查序列。（3）重復(fù)第（1）步和第（2）步，直至查找成功；或者當(dāng)待查序列為空時(shí)，說(shuō)明查找失敗。線性表的查找技術(shù)8.2.2折半查找算法折半查找不使用監(jiān)視哨，可以ST.elem[0]開始順序存放數(shù)據(jù)，算法如下。線性表的查找技術(shù)8.2.2折半查找算法下面以一個(gè)實(shí)例來(lái)說(shuō)明折半查找的過(guò)程。已知有序表{3,12,24,31,46,48,52,66,69,79,82}，目標(biāo)元素target的key值為52。（1）開始時(shí)，指針low

和high

分別指示待查元素所在范圍的下界和上界，指針mid

指示區(qū)間的中間位置，在本例中，low=0，high=10，

mid

=

5

，如下圖所示。線性表的查找技術(shù)8.2.2折半查找算法（2）令查找范圍中間位置數(shù)據(jù)元素的關(guān)鍵字ST.elem[mid].key與給定值key相比較，因?yàn)镾T.elem[mid].key<key，說(shuō)明若待查元素存在，必在區(qū)間[mid+1,high]內(nèi)。此時(shí)令low指向第mid+1個(gè)元素，即

low=6，并結(jié)合high=10重新計(jì)算出mid=8，如下圖所示。線性表的查找技術(shù)8.2.2折半查找算法（3）仍以ST.elem[mid].key與給定值key相比，因?yàn)镾T.elem[mid].key>key，說(shuō)明若待查元素存在，必在區(qū)間[low,mid-1]內(nèi)。此時(shí)令high指向第mid-1個(gè)元素，即high=7，并結(jié)合low=6重新計(jì)算出mid=6，如下圖所示。此時(shí)，新的中間位置元素值和目標(biāo)元素值相等，表明查找成功，算法返回該中間位置元素的序號(hào)6并退出。線性表的查找技術(shù)8.2.2折半查找算法

線性表的查找技術(shù)8.2.2折半查找算法由此可見，折半查找在查找成功的情況下進(jìn)行比較操作的次數(shù)最多不超過(guò)樹的高度，而判定樹的高度只與有序表中元素個(gè)數(shù)有關(guān)，與元素具體取值無(wú)關(guān)。接下來(lái)，討論折半查找不成功時(shí)的平均查找長(zhǎng)度。在前面圖中所示的折半查找判定樹所有結(jié)點(diǎn)的空指針域加上一個(gè)指向?qū)嶋H上并不存在的結(jié)點(diǎn)的指針（見右圖），并稱這些實(shí)際不存在的結(jié)點(diǎn)為外結(jié)點(diǎn)，則所有外結(jié)點(diǎn)都表示查找不成功的情況。例如，外結(jié)點(diǎn)2～3表示待查找關(guān)鍵字在第2、第3號(hào)結(jié)點(diǎn)元素的關(guān)鍵字之間時(shí)會(huì)查找失敗，過(guò)程為依次與第5、第2和第3號(hào)結(jié)點(diǎn)的關(guān)鍵字比較后，進(jìn)入該外結(jié)點(diǎn)，共比較3次關(guān)鍵字后得到查找失敗的結(jié)果。線性表的查找技術(shù)8.2.2折半查找算法

線性表的查找技術(shù)8.2.3索引查找算法索引查找又稱分塊查找，它是順序查找的一種改進(jìn)方法。索引查找將查找表分為若干個(gè)子表（也稱為塊），并對(duì)子表建立索引表，查找表的每一個(gè)子表由索引表中的索引項(xiàng)確定。索引項(xiàng)包括關(guān)鍵字字段（存放對(duì)應(yīng)塊的最大關(guān)鍵字值）和指針字段（存放塊起始位置）兩個(gè)字段，并且要求索引項(xiàng)按照關(guān)鍵字有序排列，如對(duì)于查找表中的任意兩個(gè)相鄰子表，第一個(gè)子表中的最大關(guān)鍵字小于第二個(gè)子表中的最小關(guān)鍵字（即第一個(gè)子表中所有關(guān)鍵字都比第二個(gè)子表中所有關(guān)鍵字要小）。查找時(shí)，先用給定值在索引表中檢測(cè)索引項(xiàng)，確定查找塊后在塊內(nèi)進(jìn)行順序查找。因?yàn)樵谒饕碇嘘P(guān)鍵字是有序排列的，所以我們可以先用折半查找提升第一步確定塊時(shí)的查找效率。線性表的查找技術(shù)8.2.3索引查找算法已知有如下關(guān)鍵字序列：{14,31,8,22,43,62,49,35,52,88,78,71,83}，按關(guān)鍵字值31、62、88分為3塊建立的查找表及索引表如下圖所示。索引查找算法思想如下。（1）選取各塊中的最大關(guān)鍵字構(gòu)成一個(gè)索引表。（2）查找分兩個(gè)部分：先對(duì)索引表進(jìn)行折半查找或順序查找，以確定待查記錄在具體哪一塊中，然后在已確定的塊中用順序查找法進(jìn)行查找。線性表的查找技術(shù)8.2.3索引查找算法

03PART樹表的查找技術(shù)1．二叉排序樹的定義首先給出二叉排序樹的嚴(yán)格定義：二叉排序樹或者是一棵空樹，或者是擁有下列性質(zhì)的非空二叉樹。（1）若左子樹非空，則左子樹上所有結(jié)點(diǎn)關(guān)鍵字值均小于根結(jié)點(diǎn)關(guān)鍵字值。（2）若右子樹非空，則右子樹上所有結(jié)點(diǎn)關(guān)鍵字值均大于根結(jié)點(diǎn)關(guān)鍵字值。（3）左、右子樹也分別是一棵二叉排序樹。右圖所示的樹是一棵二叉排序樹。二叉排序樹是一個(gè)遞歸定義的數(shù)據(jù)結(jié)構(gòu)，因此我們可以很方便地用遞歸算法對(duì)其進(jìn)行操作。8.3.1二叉排序樹樹表的查找技術(shù)2．二叉排序樹的查找二叉排序樹的查找是從根結(jié)點(diǎn)開始，沿某一路徑逐層向下查找的

過(guò)程。由二叉排序樹的遞歸定義，很容易給出二叉排序樹查找的遞歸

算法。其算法思想如下。（1）若二叉排序樹為空，則查找失敗。（2）若二叉樹非空，則將key值和根結(jié)點(diǎn)的關(guān)鍵字比較。①若相等，則查找成功。②若根結(jié)點(diǎn)關(guān)鍵字大于key值，則在左子樹中查找，否則在右子樹中查找。8.3.1二叉排序樹樹表的查找技術(shù)通常遞歸算法形式上比非遞歸算法簡(jiǎn)單，但遞歸算法運(yùn)行過(guò)程中需進(jìn)行多次遞歸調(diào)用，所以實(shí)際運(yùn)行效率要低于非遞歸算法。對(duì)于二叉排序樹，由于其結(jié)點(diǎn)的關(guān)鍵字具有有序性，因此開發(fā)者在不使用棧的情況下也能夠非常方便地設(shè)計(jì)其非遞歸查找算法。其算法思想如下。（1）指針p指向根結(jié)點(diǎn)。（2）當(dāng)

p

為空時(shí)，轉(zhuǎn)步驟（3），否則重復(fù)下列操作。①將key值與p指向結(jié)點(diǎn)的關(guān)鍵字比較，若相等，則查找成功，返回p。②

若p

結(jié)點(diǎn)關(guān)鍵字小于

key

值，修改

p

指向

p

的右孩子，轉(zhuǎn)步驟（2），否則，修改

p

指向

p的左孩子，轉(zhuǎn)步驟（2）。（3）返回空指針，表示查找失敗。含有n個(gè)結(jié)點(diǎn)二叉排序樹的平均查找長(zhǎng)度與樹的形態(tài)有關(guān)。在最壞情況下，二叉排序樹為單枝樹，此時(shí)查找簡(jiǎn)化為順序查找。在最好情況下，類似折半查找，其平均查找長(zhǎng)度與logn成正比。8.3.1二叉排序樹樹表的查找技術(shù)3．二叉排序樹的插入二叉排序樹的插入是以查找為基礎(chǔ)的。要將一個(gè)關(guān)鍵字值為key的結(jié)點(diǎn)插入二叉排序樹中，則需要從根結(jié)點(diǎn)向下尋找，當(dāng)樹中不存在關(guān)鍵字等于key的結(jié)點(diǎn)時(shí)才進(jìn)行插入。新插入的結(jié)點(diǎn)一定是一個(gè)新添加的葉子結(jié)點(diǎn)，并且它的父親結(jié)點(diǎn)是查找失敗的路徑上訪問(wèn)的最后一個(gè)結(jié)點(diǎn)。二叉排序樹的插入實(shí)際上是在做查找操作，因此其時(shí)間復(fù)雜度也為O(logn)。二叉排序樹插入關(guān)鍵字為key的結(jié)點(diǎn)，其算法思想如下。（1）若二叉排序樹為空，則將結(jié)點(diǎn)作為根結(jié)點(diǎn)插入樹中。（2）若二叉排序樹不為空，則比較key與根結(jié)點(diǎn)關(guān)鍵字的大小。①若key==T->data.key，則停止插入。②若key<T->data.key，則插入左子樹中。③若key>T->data.key，則插入右子樹中。8.3.1二叉排序樹樹表的查找技術(shù)4．二叉排序樹的創(chuàng)建二叉排序樹的創(chuàng)建是從初始狀態(tài)為空的二叉排序樹開始，通過(guò)不斷調(diào)用二叉排序樹插入算法函數(shù)，依次插入給定值的結(jié)點(diǎn)。二叉排序樹的創(chuàng)建算法思想如下。（1）初始化一棵空二叉排序樹。（2）讀入一個(gè)元素，根據(jù)元素的關(guān)鍵字，查找合適位置并插入結(jié)點(diǎn)。（3）重復(fù)第（2）步，直至所有元素插入完成。假設(shè)有n個(gè)待插入結(jié)點(diǎn)，插入一個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度為O(logn)，則創(chuàng)建整棵二叉排序樹的時(shí)間復(fù)雜度為O(nlogn)。假設(shè)有關(guān)鍵字序列為{45,53,12,9,50}，右圖給出二叉排序樹的建立過(guò)程。8.3.1二叉排序樹樹表的查找技術(shù)5．二叉排序樹的刪除二叉排序樹刪除結(jié)點(diǎn)的算法思想如下。（1）若被刪除結(jié)點(diǎn)z是葉子結(jié)點(diǎn)，直接刪除z即可，不會(huì)破壞二叉排序樹的性質(zhì)。（2）若被刪除結(jié)點(diǎn)z僅有左孩子或僅有右孩子，則讓z的孩子成為z父親結(jié)點(diǎn)的子樹，替代z的位置。（3）若被刪除結(jié)點(diǎn)z既有左孩子也有右孩子，則令z的直接后繼（或直接前驅(qū)）替代z，然后從二叉排序樹中刪除這個(gè)直接后繼（或直接前驅(qū)），這樣就轉(zhuǎn)換成了第一種或者第二種情況。簡(jiǎn)單來(lái)說(shuō)，我們可以從當(dāng)前刪除結(jié)點(diǎn)z的右子樹中找到最小的值（直接后繼）來(lái)替代當(dāng)前結(jié)點(diǎn)，因?yàn)樵撝禐閦的右子樹中最左下結(jié)點(diǎn)一定沒(méi)有左子樹；或者，可以從當(dāng)前刪除結(jié)點(diǎn)z的左子樹中找到最大的值（直接前驅(qū)）來(lái)替代當(dāng)前結(jié)點(diǎn)，因?yàn)樵撝禐閦的左子樹中最右下結(jié)點(diǎn)一定沒(méi)有右子樹。8.3.1二叉排序樹樹表的查找技術(shù)下圖展示了前面示例中創(chuàng)建的二叉排序樹在3種情況下刪除結(jié)點(diǎn)的過(guò)程，其中圖（c）展示的是令z的直接后繼替代z的情況。8.3.1二叉排序樹樹表的查找技術(shù)1．平衡二叉樹的定義平衡二叉樹（BalancedBinaryTree或Height-BalancedTree），又稱為AVL樹。下面給出平衡二叉樹的定義。平衡二叉樹或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹。（1）左子樹和右子樹高度差的絕對(duì)值不超過(guò)1。（2）它的左子樹和右子樹也都是平衡二叉樹。平衡二叉樹結(jié)點(diǎn)數(shù)據(jù)類型的定義如下。8.3.2平衡二叉樹樹表的查找技術(shù)這里定義結(jié)點(diǎn)左子樹和右子樹的高度差為平衡因子。顯然，平衡二叉樹上所有結(jié)點(diǎn)的平衡因子取值只可能為-1、0、1。圖（a）所示為一棵平衡二叉樹，圖（b）所示為一棵不平衡的二叉樹，結(jié)點(diǎn)中的值為該結(jié)點(diǎn)的平衡因子。8.3.2平衡二叉樹樹表的查找技術(shù)2．平衡二叉樹的插入與二叉排序樹相同，平衡二叉樹的插入和刪除操作也是一個(gè)查找的過(guò)程。不同的是，每當(dāng)在平衡二叉樹中插入（或刪除）一個(gè)結(jié)點(diǎn)時(shí)，AVL

樹中相關(guān)結(jié)點(diǎn)的平衡狀態(tài)會(huì)發(fā)生改變，因此需要從插入位置沿通向根的路徑回溯，檢查各結(jié)點(diǎn)平衡因子的絕對(duì)值是否超過(guò)1。如果在某一結(jié)點(diǎn)發(fā)現(xiàn)平衡二叉樹失衡，則停止回溯，并從發(fā)生失衡的結(jié)點(diǎn)起，檢查該結(jié)點(diǎn)及其子結(jié)點(diǎn)的連接方式。8.3.2平衡二叉樹樹表的查找技術(shù)它們的連接方式可以歸類為

4

種情況（見下圖），在這里將中間結(jié)點(diǎn)叫作pivot，它的子結(jié)點(diǎn)叫作bottom，父親結(jié)點(diǎn)叫作root。如果pivot

是root

的左結(jié)點(diǎn)（或者右結(jié)點(diǎn)），并且

bottom

也同樣是

pivot

的左結(jié)點(diǎn)（或右結(jié)點(diǎn)），則采用單旋轉(zhuǎn)的方式進(jìn)行平衡化，單旋轉(zhuǎn)又可按上述兩種連接方式分為右單旋轉(zhuǎn)和左單旋轉(zhuǎn)兩種情況，顯然，它們互為鏡像。如果pivot

是

root

的左結(jié)點(diǎn)（或者右結(jié)點(diǎn)），而

bottom

卻是

pivot

的右結(jié)點(diǎn)（或左結(jié)點(diǎn)），這類情況下需要采用雙旋轉(zhuǎn)的方式進(jìn)行平衡化，雙旋轉(zhuǎn)又可按照上述兩種連接方式分為先左后右雙旋轉(zhuǎn)和先右后左雙旋轉(zhuǎn)兩種情況。8.3.2平衡二叉樹樹表的查找技術(shù)（1）右單旋轉(zhuǎn)（RotateRight）。右單旋轉(zhuǎn)針對(duì)的是LL型不平衡樹。LL型不平衡樹指的是針對(duì)一棵初始的平衡樹，在結(jié)點(diǎn)左孩子（L）的左子樹（L）上插入新結(jié)點(diǎn)，導(dǎo)致結(jié)點(diǎn)平衡因子的絕對(duì)值大于1。在LL型不平衡樹中，應(yīng)當(dāng)以3個(gè)結(jié)點(diǎn)的中心結(jié)點(diǎn)為軸向右（順時(shí)針）旋轉(zhuǎn)。向右旋轉(zhuǎn)后，相當(dāng)于右子樹的樹高增加了1，而左子樹的樹高降低了1，因而整棵樹重新平衡。8.3.2平衡二叉樹樹表的查找技術(shù)下圖給出了一個(gè)右單旋轉(zhuǎn)示例，其具體步驟如下。①初始時(shí)，該樹是一棵平衡二叉樹，如圖（a）所示。②在子樹D中插入新結(jié)點(diǎn)，該子樹高度增1導(dǎo)致結(jié)點(diǎn)A的平衡因子變成+2，出現(xiàn)不平衡，如圖（b）所示。③沿插入路徑檢查3個(gè)結(jié)點(diǎn)A、B和D，發(fā)現(xiàn)它們處于方向?yàn)椤?”的直線上，需做右單旋轉(zhuǎn)。④以中心結(jié)點(diǎn)B為旋轉(zhuǎn)軸，讓結(jié)點(diǎn)A順時(shí)針旋轉(zhuǎn)。旋轉(zhuǎn)后，原來(lái)根結(jié)點(diǎn)A的左孩子B成為新的根結(jié)點(diǎn)，整棵樹重新平衡，如圖（c）所示。8.3.2平衡二叉樹樹表的查找技術(shù)（2）左單旋轉(zhuǎn)（RotateLeft）。左單旋轉(zhuǎn)針對(duì)的是

RR

型不平衡樹。RR

型不平衡樹指的是針對(duì)一棵初始的平衡樹，在結(jié)點(diǎn)右孩子（R）的右子樹（R）上插入新結(jié)點(diǎn)，導(dǎo)致結(jié)點(diǎn)平衡因子的絕對(duì)值大于1。在RR

型不平衡樹中，應(yīng)當(dāng)以3

個(gè)結(jié)點(diǎn)的中心結(jié)點(diǎn)為軸向左（逆時(shí)針）旋轉(zhuǎn)。向左旋轉(zhuǎn)后，相當(dāng)于左子樹的樹高增加了1，而右子樹的樹高降低了1，整棵樹重新平衡。8.3.2平衡二叉樹樹表的查找技術(shù)下圖給出了一個(gè)左單旋轉(zhuǎn)示例，其具體步驟如下。①初始時(shí)，樹是一棵平衡二叉樹，如圖（a）所示。②在以E為根的子樹中插入新結(jié)點(diǎn)，該子樹高度增1導(dǎo)致結(jié)點(diǎn)A的平衡因子變成-2，出現(xiàn)不平衡，如圖（b）所示。③沿插入路徑檢查3個(gè)結(jié)點(diǎn)A、C和E，發(fā)現(xiàn)它們處于方向?yàn)椤癨”的直線上，需做左單旋轉(zhuǎn)。④以中心結(jié)點(diǎn)C為旋轉(zhuǎn)軸，讓結(jié)點(diǎn)A逆時(shí)針旋轉(zhuǎn)。旋轉(zhuǎn)后，原來(lái)根結(jié)點(diǎn)A的右孩子C成為新的根結(jié)點(diǎn)，并調(diào)整相應(yīng)結(jié)點(diǎn)與子樹的關(guān)系以使整棵樹重新平衡，如圖（c）所示。8.3.2平衡二叉樹樹表的查找技術(shù)（3）先左后右雙旋轉(zhuǎn)（RotateLeftRight）。先左后右雙旋轉(zhuǎn)針對(duì)的是LR型不平衡樹。LR型不平衡樹指是在結(jié)點(diǎn)左孩子（L）的右子樹（R）上插入新結(jié)點(diǎn)，導(dǎo)致結(jié)點(diǎn)平衡因子的絕對(duì)值大于1。在LR型不平衡樹中，應(yīng)當(dāng)以該結(jié)點(diǎn)為軸先向左再向右旋轉(zhuǎn)。下面給出了一個(gè)先左后右雙旋轉(zhuǎn)示例，其具體步驟如下。①初始時(shí)，該樹是一棵平衡二叉樹，如圖（a）所示。②在以F或G為根的子樹中插入新結(jié)點(diǎn)，該子樹高度增1導(dǎo)致結(jié)點(diǎn)A的平衡因子變成+2，出現(xiàn)不平衡，如圖（b）所示。8.3.2平衡二叉樹樹表的查找技術(shù)③沿插入路徑檢查3個(gè)結(jié)點(diǎn)A、B和E，發(fā)現(xiàn)它們位于一條形如“<”的折線上，因此需要進(jìn)行先左后右的雙旋轉(zhuǎn)。④以結(jié)點(diǎn)E為旋轉(zhuǎn)軸，讓結(jié)點(diǎn)B逆時(shí)針旋轉(zhuǎn)，如圖（a）所示。⑤以結(jié)點(diǎn)E為旋轉(zhuǎn)軸，讓結(jié)點(diǎn)A順時(shí)針旋轉(zhuǎn)，整棵樹重新平衡，如圖（b）所示。8.3.2平衡二叉樹樹表的查找技術(shù)（4）先右后左雙旋轉(zhuǎn)（RotateRightLeft）。先右后左雙旋轉(zhuǎn)針對(duì)的是RL型不平衡樹。RL型不平衡樹指的是在結(jié)點(diǎn)右孩子（R）的左子樹（L）上插入新結(jié)點(diǎn)，導(dǎo)致結(jié)點(diǎn)平衡因子的絕對(duì)值大于1。在RL型不平衡樹中，應(yīng)當(dāng)以該結(jié)點(diǎn)為軸先向右再向左旋轉(zhuǎn)。下面給出了一個(gè)先右后左雙旋轉(zhuǎn)示例，其具體步驟如下。①初始時(shí)，該樹是一棵平衡二叉樹，如圖（a）所示。②在以F或G為根的子樹中插入新結(jié)點(diǎn)，該子樹高度增1導(dǎo)致結(jié)點(diǎn)A的平衡因子變成-2，出現(xiàn)不平衡，如圖（b）所示。8.3.2平衡二叉樹樹表的查找技術(shù)③沿插入路徑檢查3個(gè)結(jié)點(diǎn)A、C和D，發(fā)現(xiàn)它們位于一條形如“>”的折線上，因此需要進(jìn)行先右后左的雙旋轉(zhuǎn)。④以結(jié)點(diǎn)D為旋轉(zhuǎn)軸，讓結(jié)點(diǎn)C順時(shí)針旋轉(zhuǎn)，如圖（a）所示。⑤以結(jié)點(diǎn)D為旋轉(zhuǎn)軸，讓結(jié)點(diǎn)A逆時(shí)針旋轉(zhuǎn)，整棵樹重新平衡，如圖（b）所示。8.3.2平衡二叉樹樹表的查找技術(shù)3．平衡二叉樹的查找性能分析在平衡二叉樹上進(jìn)行查找的過(guò)程與在二叉排序樹上進(jìn)行查找的過(guò)程相同，因此，查找過(guò)程中所進(jìn)行的比較次數(shù)最多不超過(guò)樹的深度。假設(shè)以Nh表示深度為h的平衡二叉樹中含有的最少結(jié)點(diǎn)數(shù)，顯然，N0=0，N1=1，N2=2，并且有Nh=

Nh-1

+

Nh-2+1?？梢宰C明，含有n個(gè)結(jié)點(diǎn)的平衡二叉樹的最大深度為logn，所以平衡二叉樹的平均查找長(zhǎng)度為O(logn)。8.3.2平衡二叉樹樹表的查找技術(shù)1．紅黑樹的定義紅黑樹是一種自平衡二叉排序樹，即在進(jìn)行插入和刪除等可能會(huì)破壞樹平衡的操作時(shí)，需要重新自處理達(dá)到平衡狀態(tài)。紅黑樹在每個(gè)結(jié)點(diǎn)上都增加一個(gè)存儲(chǔ)位來(lái)表示結(jié)點(diǎn)的顏色，顏色可以是紅色（Red）或黑色（Black）。紅黑樹主要用來(lái)存儲(chǔ)有序數(shù)據(jù)，其查找、插入、刪除都具有O(logn)的時(shí)間復(fù)雜度，所以效率很高。紅黑樹的具體性質(zhì)如下。（1）每個(gè)結(jié)點(diǎn)顏色不是黑色，就是紅色。（2）根結(jié)點(diǎn)和葉結(jié)點(diǎn)（NIL）是黑色的。（3）如果一個(gè)結(jié)點(diǎn)是紅色的，則它的子結(jié)點(diǎn)必須是黑色的，即沒(méi)有連續(xù)相鄰的紅色結(jié)點(diǎn)。（4）從任一結(jié)點(diǎn)到其每個(gè)葉子的所有路徑都包含相同數(shù)目的黑色結(jié)點(diǎn)。8.3.3紅黑樹樹表的查找技術(shù)下圖所示為一棵紅黑樹。其中用圓形表示黑色結(jié)點(diǎn)，五邊形表示紅色結(jié)點(diǎn)，方形表示葉子結(jié)點(diǎn)。8.3.3紅黑樹樹表的查找技術(shù)2．紅黑樹的基本操作紅黑樹的基本操作包括旋轉(zhuǎn)和變色兩種。對(duì)紅黑樹的插入和刪除過(guò)程中會(huì)打破紅黑樹的性質(zhì)，

此時(shí)借助旋轉(zhuǎn)和變色可以保持紅黑樹的平衡。旋轉(zhuǎn)包括左旋和右旋兩種，它們與上節(jié)平衡二叉樹的旋轉(zhuǎn)操作類似另外，旋轉(zhuǎn)操作不會(huì)改變樹中序遍歷的順序，旋轉(zhuǎn)操作通過(guò)降低高子樹的高度和增加低子樹的高度來(lái)維護(hù)二叉樹平衡。變色包括紅色變?yōu)楹谏秃谏優(yōu)榧t色兩種。8.3.3紅黑樹樹表的查找技術(shù)3．紅黑樹的插入紅黑樹的插入主要分為結(jié)點(diǎn)的插入和修復(fù)兩個(gè)過(guò)程。新結(jié)點(diǎn)插入后，修復(fù)過(guò)程主要是為了保持紅黑樹的性質(zhì)而進(jìn)行的操作。其中，為了紅黑樹每次能夠更簡(jiǎn)便地被修復(fù)，規(guī)定每次插入結(jié)點(diǎn)的顏色為紅色。新結(jié)點(diǎn)插入后，紅黑樹的性質(zhì)被破壞，因此，此時(shí)需要通過(guò)左旋、右旋和變色等操作來(lái)滿足紅黑樹的性質(zhì)要求，從而實(shí)現(xiàn)紅黑樹的自平衡。紅黑樹的插入有多種情況，首先約定插入操作結(jié)點(diǎn)的叫法，如右圖所示。其中N為新的插入結(jié)點(diǎn)；P為插入結(jié)點(diǎn)的父親結(jié)點(diǎn)；U為插入結(jié)點(diǎn)的叔叔結(jié)點(diǎn)；G為插入結(jié)點(diǎn)的父親結(jié)點(diǎn)P的父親結(jié)點(diǎn)，即祖父結(jié)點(diǎn)G。8.3.3紅黑樹樹表的查找技術(shù)插入情景1：紅黑樹為空樹。當(dāng)N是根結(jié)點(diǎn)，即在N插入之前是一棵空樹，根據(jù)性質(zhì)2，只需要直接將插入結(jié)點(diǎn)作為根結(jié)點(diǎn)，再經(jīng)過(guò)變色操作，將N由紅色變?yōu)楹谏?，如下圖所示。8.3.3紅黑樹插入情景2：插入結(jié)點(diǎn)N的父親結(jié)點(diǎn)P是黑色。由于插入結(jié)點(diǎn)N是紅色的，其父親結(jié)點(diǎn)P為黑色，滿足紅黑樹的各性質(zhì)，因此直接插入即可。樹表的查找技術(shù)插入情景3：插入結(jié)點(diǎn)N的父親結(jié)點(diǎn)P是紅色，叔叔結(jié)點(diǎn)U存在且為紅色。當(dāng)插入結(jié)點(diǎn)N的父親結(jié)點(diǎn)P為紅色，插入結(jié)點(diǎn)N的叔叔結(jié)點(diǎn)U存在且是紅色的，說(shuō)明具有祖父結(jié)點(diǎn)G，因?yàn)槿绻赣H結(jié)點(diǎn)P是根結(jié)點(diǎn)，那父親結(jié)點(diǎn)P就應(yīng)當(dāng)是黑色。為了維護(hù)性質(zhì)3，因此需要對(duì)N的父親結(jié)點(diǎn)P、祖父結(jié)點(diǎn)G、叔叔結(jié)點(diǎn)U進(jìn)行變色。首先將P和U設(shè)為黑色，將G設(shè)為紅色，再將G設(shè)為當(dāng)前插入結(jié)點(diǎn)即可。如果父親結(jié)點(diǎn)P和叔父親結(jié)點(diǎn)U二者都是紅色，此時(shí)新插入結(jié)點(diǎn)N作為P的左子結(jié)點(diǎn)或右子結(jié)點(diǎn)都屬于此插入情景，下圖中僅顯示N作為P左子結(jié)點(diǎn)的情況。如果G是根結(jié)點(diǎn)，就違反了性質(zhì)2，也有可能祖父結(jié)點(diǎn)G的父親結(jié)點(diǎn)是紅色的，則違反了性質(zhì)4，因此可以在祖父結(jié)點(diǎn)G上進(jìn)行遞歸。如果G不是根結(jié)點(diǎn)，此時(shí)還需要把G當(dāng)作新的插入結(jié)點(diǎn)遞歸地再次進(jìn)行檢查及調(diào)整，直到滿足紅黑樹性質(zhì)為止。8.3.3紅黑樹樹表的查找技術(shù)插入情景4：插入結(jié)點(diǎn)N的父親結(jié)點(diǎn)P是紅色，叔叔結(jié)點(diǎn)U不存在或?yàn)楹谏Y(jié)點(diǎn)，父親結(jié)點(diǎn)P是祖父結(jié)點(diǎn)G的左子結(jié)點(diǎn)，插入結(jié)點(diǎn)N是其父親結(jié)點(diǎn)P的左子結(jié)點(diǎn)。父親結(jié)點(diǎn)P是紅色，根據(jù)性質(zhì)3，可知祖父結(jié)點(diǎn)G是黑色。首先為了滿足性質(zhì)3，將父親結(jié)點(diǎn)P設(shè)置為黑色、祖父結(jié)點(diǎn)G設(shè)置為紅色，再針對(duì)祖父結(jié)點(diǎn)G進(jìn)行右旋操作，得到一棵新的樹。在旋轉(zhuǎn)產(chǎn)生的樹中，以前的父親結(jié)點(diǎn)P是插入結(jié)點(diǎn)N和以前的祖父結(jié)點(diǎn)G的父親結(jié)點(diǎn)，如下圖所示。8.3.3紅黑樹樹表的查找技術(shù)插入情景5：插入結(jié)點(diǎn)N的父親結(jié)點(diǎn)P是紅色，叔叔結(jié)點(diǎn)不存在或?yàn)楹谏Y(jié)點(diǎn)，父親結(jié)點(diǎn)P是祖父結(jié)點(diǎn)G的右子結(jié)點(diǎn)，插入結(jié)點(diǎn)N是其父親結(jié)點(diǎn)P的右子結(jié)點(diǎn)。同理，為了滿足性質(zhì)3，首先將父親結(jié)點(diǎn)P設(shè)置為黑色、祖父結(jié)點(diǎn)G設(shè)置為紅色，再針對(duì)祖父結(jié)點(diǎn)G進(jìn)行左旋操作，得到一棵新的樹，如下圖所示。8.3.3紅黑樹樹表的查找技術(shù)插入情景6：插入結(jié)點(diǎn)N的父親結(jié)點(diǎn)P是紅色，叔叔結(jié)點(diǎn)不存在或?yàn)楹谏Y(jié)點(diǎn)，父親結(jié)點(diǎn)P是祖父結(jié)點(diǎn)G的左子結(jié)點(diǎn)，插入結(jié)點(diǎn)N是其父親結(jié)點(diǎn)P的右子結(jié)點(diǎn)。該插入情景可以轉(zhuǎn)換為插入情景4。如下圖所示，首先對(duì)N的父親結(jié)點(diǎn)P進(jìn)行左旋，重新設(shè)置P為插入結(jié)點(diǎn)后，即可得到插入情景4，再按照插入情景4的方法，將父親結(jié)點(diǎn)N設(shè)置為黑色、祖父結(jié)點(diǎn)G設(shè)置為紅色，再針對(duì)祖父結(jié)點(diǎn)G進(jìn)行右旋操作。8.3.3紅黑樹樹表的查找技術(shù)插入情景7：插入結(jié)點(diǎn)N的父親結(jié)點(diǎn)P是紅色，叔叔結(jié)點(diǎn)不存在或?yàn)楹谏Y(jié)點(diǎn)，父親結(jié)點(diǎn)P是祖父結(jié)點(diǎn)G的右子結(jié)點(diǎn)，插入結(jié)點(diǎn)N是其父親結(jié)點(diǎn)P的左子結(jié)點(diǎn)。該插入情景可以轉(zhuǎn)換為插入情景5。如下圖所示，首先對(duì)N的父親結(jié)點(diǎn)P進(jìn)行右旋，重新設(shè)置P為插入結(jié)點(diǎn)后，即可得到插入情景5，再按照插入情景5的方法，將父親結(jié)點(diǎn)N設(shè)置為黑色、祖父結(jié)點(diǎn)G設(shè)置為紅色，再針對(duì)祖父結(jié)點(diǎn)G進(jìn)行左旋操作。8.3.3紅黑樹樹表的查找技術(shù)4．紅黑樹的刪除紅黑樹的刪除需要保證結(jié)點(diǎn)被刪除后，紅黑樹的性質(zhì)依然成立。首先，需要保證刪除后二叉排序樹的性質(zhì)依然成立；其次，需要保證紅黑樹自身的性質(zhì)依然成立。對(duì)于維護(hù)紅黑樹的二叉排序樹性質(zhì)，不需要關(guān)注結(jié)點(diǎn)的顏色，只需分為以下3種情況討論。（1）待刪除結(jié)點(diǎn)無(wú)子結(jié)點(diǎn)若待刪除結(jié)點(diǎn)無(wú)子結(jié)點(diǎn)，直接刪除。如下圖所示，其中5號(hào)結(jié)點(diǎn)并無(wú)子結(jié)點(diǎn)，直接刪除5號(hào)結(jié)點(diǎn)即可。8.3.3紅黑樹樹表的查找技術(shù)（2）刪除結(jié)點(diǎn)只有一個(gè)子結(jié)點(diǎn)若刪除結(jié)點(diǎn)只有一個(gè)子結(jié)點(diǎn)，將子結(jié)點(diǎn)的值復(fù)制到要?jiǎng)h除的結(jié)點(diǎn)中，接著刪除從中復(fù)制出值的那個(gè)結(jié)點(diǎn)（即子結(jié)點(diǎn)）。如下圖所示，其中6號(hào)結(jié)點(diǎn)只有5號(hào)結(jié)點(diǎn)一個(gè)子結(jié)點(diǎn)，用5號(hào)結(jié)點(diǎn)替換6號(hào)結(jié)點(diǎn)，并刪除6號(hào)結(jié)點(diǎn)即可。8.3.3紅黑樹樹表的查找技術(shù)（3）刪除結(jié)點(diǎn)有兩個(gè)子結(jié)點(diǎn)若刪除結(jié)點(diǎn)有兩個(gè)子結(jié)點(diǎn)，找到前繼結(jié)點(diǎn)（左子樹中的最大元素）或者后繼結(jié)點(diǎn)（右子樹中的最小元素），并把它的值復(fù)制到要?jiǎng)h除的結(jié)點(diǎn)中，接著刪除從中復(fù)制出值的那個(gè)結(jié)點(diǎn)（即前繼結(jié)點(diǎn)或者后續(xù)結(jié)點(diǎn)）。如圖所示，其中4號(hào)結(jié)點(diǎn)有2、7號(hào)兩個(gè)子結(jié)點(diǎn)，將后繼結(jié)點(diǎn)5號(hào)結(jié)點(diǎn)的值復(fù)制到4號(hào)結(jié)點(diǎn)中，再刪除5號(hào)結(jié)點(diǎn)即可。由于只是復(fù)制了一個(gè)值，沒(méi)有復(fù)制顏色，因此不會(huì)破壞紅黑樹的性質(zhì)。8.3.3紅黑樹樹表的查找技術(shù)由上述分析可知，如果需要?jiǎng)h除的結(jié)點(diǎn)有兩個(gè)子結(jié)點(diǎn)，那么問(wèn)題可以被轉(zhuǎn)換成刪除另一個(gè)只有一個(gè)子結(jié)點(diǎn)的問(wèn)題。因此，對(duì)于維護(hù)紅黑樹的性質(zhì)，下述只需要討論“刪除結(jié)點(diǎn)只有一個(gè)子結(jié)點(diǎn)”的情況。對(duì)于二叉排序樹，在刪除帶有兩個(gè)非葉子兒子的結(jié)點(diǎn)時(shí)，要么找到它左子樹中的最大元素（前繼），要么找到它右子樹中的最小元素（后繼），并把它的值轉(zhuǎn)移到要?jiǎng)h除的結(jié)點(diǎn)中，且刪除從中復(fù)制出值的那個(gè)結(jié)點(diǎn)。由于只是復(fù)制一個(gè)值，沒(méi)有復(fù)制顏色，因此不違反任何性質(zhì)。在只有一個(gè)子結(jié)點(diǎn)的情況下，該子結(jié)點(diǎn)分為替換結(jié)點(diǎn)N的左子樹和右子樹兩種情況。因此，首先找到替換結(jié)點(diǎn)N兄弟結(jié)點(diǎn)，再進(jìn)行后續(xù)分析即可。由于替換結(jié)點(diǎn)N的左子樹和右子樹兩種情況類似，只是進(jìn)行了簡(jiǎn)單的對(duì)稱變換，因此這里只以該子結(jié)點(diǎn)為替換結(jié)點(diǎn)N的左子結(jié)點(diǎn)為例進(jìn)行介紹。8.3.3紅黑樹樹表的查找技術(shù)刪除情景1：刪除紅色結(jié)點(diǎn)。把替換結(jié)點(diǎn)換到刪除結(jié)點(diǎn)的位置時(shí)，由于替換結(jié)點(diǎn)是紅色的，刪除后也不會(huì)影響紅黑樹的平衡，只要把替換結(jié)點(diǎn)的顏色設(shè)為刪除結(jié)點(diǎn)的顏色即可重新保持平衡。通過(guò)被刪除結(jié)點(diǎn)的所有路徑只是少了一個(gè)紅色結(jié)點(diǎn)，這樣可以繼續(xù)保證紅黑樹的各個(gè)性質(zhì)。刪除情景2：刪除結(jié)點(diǎn)是黑色，而它的兒子結(jié)點(diǎn)是紅色。被刪除結(jié)點(diǎn)是黑色，而它的兒子結(jié)點(diǎn)是紅色的時(shí)候，如果只是去除這個(gè)黑色結(jié)點(diǎn)，用它的紅色兒子結(jié)點(diǎn)頂替會(huì)破壞性質(zhì)4。但是如果重繪它的兒子結(jié)點(diǎn)為黑色，則曾經(jīng)通過(guò)它的所有路徑將通過(guò)它的黑色兒子結(jié)點(diǎn)，這樣可以繼續(xù)保持性質(zhì)4。8.3.3紅黑樹樹表的查找技術(shù)刪除情景3：刪除結(jié)點(diǎn)是黑色，其兒子結(jié)點(diǎn)是黑色。這種情況下該結(jié)點(diǎn)的兩個(gè)兒子結(jié)點(diǎn)都是葉子結(jié)點(diǎn)，否則若其中一個(gè)兒子結(jié)點(diǎn)是黑色非葉子結(jié)點(diǎn)、另一個(gè)兒子結(jié)點(diǎn)是葉子結(jié)點(diǎn)，那么從該結(jié)點(diǎn)通過(guò)非葉子結(jié)點(diǎn)路徑上的黑色結(jié)點(diǎn)數(shù)最小為2，而從該結(jié)點(diǎn)到另一個(gè)葉子結(jié)點(diǎn)路徑上的黑色結(jié)點(diǎn)數(shù)為1，會(huì)違反性質(zhì)4。因此，應(yīng)該首先把要?jiǎng)h除的結(jié)點(diǎn)替換為它的兒子結(jié)點(diǎn)。當(dāng)刪除結(jié)點(diǎn)是黑色，而它的兒子結(jié)點(diǎn)是黑色的時(shí)候，該情景下的討論情況比較多，因此分類討論。首先給出刪除操作結(jié)點(diǎn)的叫法約定，如圖所示。其中，替代結(jié)點(diǎn)為N（即刪除結(jié)點(diǎn)），N

的兄弟結(jié)點(diǎn)為

S（即父親結(jié)點(diǎn)的另一個(gè)兒子結(jié)點(diǎn)），N

的父親結(jié)點(diǎn)為P；S

的左兒子結(jié)點(diǎn)為SL，S

的右兒子結(jié)點(diǎn)為SR。8.3.3紅黑樹樹表的查找技術(shù)如果N

和P

是黑色，則刪除P

導(dǎo)致通過(guò)N的路徑都比不通過(guò)N的路徑少了一個(gè)黑色結(jié)點(diǎn)。因?yàn)檫@樣違反性質(zhì)4，所以樹需要被重新平衡。刪除情景3.1：N是新的根。在這種情景下，從所有路徑去除一個(gè)黑色結(jié)點(diǎn)，而新根是黑色的，所以性質(zhì)都能得以保持。在下述刪除情景3.2、刪除情景3.5和刪除情景3.6下，假定N是P的左兒子結(jié)點(diǎn)。因?yàn)槿绻鸑是右兒子結(jié)點(diǎn)，則在上述情景中進(jìn)行左旋和右旋操作對(duì)調(diào)即可。8.3.3紅黑樹樹表的查找技術(shù)刪除情景3.2：兄弟結(jié)點(diǎn)S是紅色，替換結(jié)點(diǎn)N是父親結(jié)點(diǎn)P的左兒子結(jié)點(diǎn)。在該刪除情景下，首先為了保證性質(zhì)3，將S設(shè)為黑色，P設(shè)為紅色，在N的父親結(jié)點(diǎn)上做左旋轉(zhuǎn)（如果N

是右兒子結(jié)點(diǎn)，則在N

的父親結(jié)點(diǎn)上做右旋轉(zhuǎn)），把紅色兄弟轉(zhuǎn)換成N

的祖父結(jié)點(diǎn)，如圖（b）所示。完成這兩個(gè)操作后，盡管所有路徑上黑色結(jié)點(diǎn)的數(shù)量沒(méi)有改變，但現(xiàn)在N有了一個(gè)黑色的兄弟結(jié)點(diǎn)和一個(gè)紅色的父親結(jié)點(diǎn)，可以得到刪除情景3.3，所以繼續(xù)按刪除情景3.3進(jìn)行處理。8.3.3紅黑樹樹表的查找技術(shù)刪除情景3.3：替換結(jié)點(diǎn)N的父親結(jié)點(diǎn)P、兄弟結(jié)點(diǎn)S和兄弟結(jié)點(diǎn)的兒子結(jié)點(diǎn)都是黑色。在這種情景下，因?yàn)镹即將被刪除，會(huì)導(dǎo)致少一個(gè)黑色結(jié)點(diǎn)，子樹也需要少一個(gè)，所以為了在P所在的子樹中保持平衡，把兄弟結(jié)點(diǎn)S設(shè)為紅色，如圖8.32（b）所示。由于刪除N結(jié)點(diǎn)所有通過(guò)N的所有路徑少了一個(gè)黑色結(jié)點(diǎn)，所有通過(guò)S的路徑都少了一個(gè)黑色結(jié)點(diǎn)，因此整棵樹得到平衡。但是，通過(guò)P的所有路徑現(xiàn)在比不通過(guò)P的路徑少了一個(gè)黑色結(jié)點(diǎn)，所以仍然違反性質(zhì)4。要修正這個(gè)問(wèn)題，需要在P上重新進(jìn)行遞歸平衡處理。8.3.3紅黑樹樹表的查找技術(shù)刪除情景3.4：兄弟結(jié)點(diǎn)S和S的兒子結(jié)點(diǎn)都是黑色，替換結(jié)點(diǎn)N的父親結(jié)點(diǎn)P是紅色。如圖（b）所示，將S設(shè)置為紅色，將P設(shè)置為黑色。這樣不影響不通過(guò)N的路徑上黑色結(jié)點(diǎn)的數(shù)量，但是在通過(guò)N的路徑上對(duì)黑色結(jié)點(diǎn)數(shù)量增加1，剛好添補(bǔ)在這些路徑上刪除的黑色結(jié)點(diǎn)，因此滿足紅黑樹的性質(zhì)。8.3.3紅黑樹樹表的查找技術(shù)刪除情景3.5：兄弟結(jié)點(diǎn)S是黑色，S的左兒子結(jié)點(diǎn)是紅色，S的右兒子結(jié)點(diǎn)是黑色，替換結(jié)點(diǎn)N是父親結(jié)點(diǎn)P的左兒子結(jié)點(diǎn)。如圖所示，在

S

上做右旋轉(zhuǎn)（如果

N

是右兒子結(jié)點(diǎn)，則在

S

上做左旋轉(zhuǎn)），這樣

S

的左兒子結(jié)點(diǎn)成為S

的父親結(jié)點(diǎn)和N

的新兄弟結(jié)點(diǎn)。我們接著交換S

與它的新父親結(jié)點(diǎn)的顏色。所有路徑仍有同樣數(shù)量的黑色結(jié)點(diǎn)，但是現(xiàn)在N

有了一個(gè)黑色兄弟結(jié)點(diǎn)，它的右兒子結(jié)點(diǎn)是紅色的，所以我們進(jìn)入刪除情景6

進(jìn)行處理。N

和它的父親結(jié)點(diǎn)都不受這個(gè)變換的影響。8.3.3紅黑樹樹表的查找技術(shù)刪除情景3.6：S是黑色，S的右兒子結(jié)點(diǎn)是紅色，替換結(jié)點(diǎn)N是父親結(jié)點(diǎn)P的左兒子結(jié)點(diǎn)。如圖所示，在N的父親結(jié)點(diǎn)上做左旋轉(zhuǎn)（如果N是右兒子結(jié)點(diǎn)，則在N的父親結(jié)點(diǎn)上做右旋轉(zhuǎn)），接著交換N的父親結(jié)點(diǎn)與S的顏色，并使S的右兒子結(jié)點(diǎn)變色為黑色。子樹在它的根上的仍是同樣的顏色。但是N增加了一個(gè)黑色祖先結(jié)點(diǎn)，因此要么N的父親結(jié)點(diǎn)變成黑色，要么它是黑色而S被增加為一個(gè)黑色祖父結(jié)點(diǎn)。所以通過(guò)N的路徑都增加了一個(gè)黑色結(jié)點(diǎn)。此時(shí)，如果一個(gè)路徑不通過(guò)N，則有以下兩種可能性。8.3.3紅黑樹樹表的查找技術(shù)（1）它通過(guò)N的新兄弟。那么它以前與現(xiàn)在都必定通過(guò)S和N的父親結(jié)點(diǎn)，而它們只是交換了顏色。所以路徑保持了同樣數(shù)量的黑色結(jié)點(diǎn)。（2）它通過(guò)N的新叔父結(jié)點(diǎn)，S的右兒子結(jié)點(diǎn)。那么它以前通過(guò)S、S的父親結(jié)點(diǎn)和S的右兒子結(jié)點(diǎn)，但是現(xiàn)在只通過(guò)S，它被假定為它以前父親結(jié)點(diǎn)的顏色，和S的右兒子結(jié)點(diǎn)，它被從紅色改變?yōu)楹谏：铣尚Ч沁@個(gè)路徑通過(guò)了同樣數(shù)量的黑色結(jié)點(diǎn)。8.3.3紅黑樹樹表的查找技術(shù)B樹又稱為多路平衡查找樹，B樹中所有結(jié)點(diǎn)的孩子結(jié)點(diǎn)數(shù)最大值稱為B樹的階，通常用m（m≥2）表示。一棵m階B樹或?yàn)榭諛洌驗(yàn)闈M足下列特性的m階樹。（1）樹中每個(gè)結(jié)點(diǎn)最多只有m棵子樹。（2）如果根結(jié)點(diǎn)不是葉子結(jié)點(diǎn)，則根結(jié)點(diǎn)至少有兩棵子樹。（3）每個(gè)非葉子結(jié)點(diǎn)（除了根）至少具有?m/2?棵子樹。（4）具有k個(gè)子結(jié)點(diǎn)的非葉子結(jié)點(diǎn)包含k-1個(gè)關(guān)鍵字，所有結(jié)點(diǎn)關(guān)鍵字是按遞增次序排列，并遵循從小到大的原則。（5）所有葉子結(jié)點(diǎn)都出現(xiàn)在同一層上，并且其指向子結(jié)點(diǎn)的指針默認(rèn)為null。8.3.4B樹樹表的查找技術(shù)B樹結(jié)點(diǎn)與整體結(jié)構(gòu)類型定義如下。8.3.4B樹樹表的查找技術(shù)B樹是所有結(jié)點(diǎn)的平衡因子均為0的多路查找樹，下圖所示為一棵3階的B樹。8.3.4B樹樹表的查找技術(shù)2．B

樹的查找B樹的查找與二叉排序樹的查找類似，只是每個(gè)結(jié)點(diǎn)都是多個(gè)關(guān)鍵字的有序表，并且在每個(gè)結(jié)點(diǎn)上所做的并不是兩路分支決定，而是多路分支決定。B樹的查找分為以下兩步。（1）在B樹中根據(jù)指針的索引查找結(jié)點(diǎn)。（2）在索引結(jié)點(diǎn)中尋找關(guān)鍵字。由于B樹常存儲(chǔ)在磁盤上，因而前一個(gè)查找通常是在磁盤上進(jìn)行的，而后一個(gè)查找是在內(nèi)存中進(jìn)行的，即在磁盤上找到結(jié)點(diǎn)后，將結(jié)點(diǎn)信息讀入內(nèi)存中，然后采用順序查找或者折半查找找到目標(biāo)關(guān)鍵字。在B樹上找到某個(gè)結(jié)點(diǎn)后，先在有序表中進(jìn)行查找，若找到則查找成功，否則按照對(duì)應(yīng)的指針信息到所指的子樹中去查找。8.3.4B樹樹表的查找技術(shù)3．B樹的插入

B樹結(jié)構(gòu)復(fù)雜，我們?yōu)槠洳迦虢Y(jié)點(diǎn)時(shí)需要考慮葉子結(jié)點(diǎn)元素個(gè)數(shù)不能超過(guò)m（m為階數(shù)）。針對(duì)m階高度為h的B樹插入一個(gè)元素時(shí)，首先在B樹中查找該元素是否存在，如果不存在，則在葉子結(jié)點(diǎn)處插入該新的元素。其詳細(xì)步驟如下。（1）若該結(jié)點(diǎn)元素個(gè)數(shù)小于m-1，直接插入。（2）若該結(jié)點(diǎn)元素個(gè)數(shù)等于m-1，引起結(jié)點(diǎn)分裂；以該結(jié)點(diǎn)中間元素為分界，取中間元素（若為偶數(shù)，則隨機(jī)選取中間兩個(gè)元素之一）插入父親結(jié)點(diǎn)中。（3）重復(fù)上面動(dòng)作，直到所有結(jié)點(diǎn)符合B樹的規(guī)則；最壞的情況會(huì)一直分裂到根結(jié)點(diǎn)，生成新的根結(jié)點(diǎn)，高度增加1。8.3.4B樹樹表的查找技術(shù)圖片展示了一棵5

階B

樹插入的過(guò)程。5

階B

樹中，除根結(jié)點(diǎn)以外的結(jié)點(diǎn)最多有4

個(gè)關(guān)鍵字，最少有2

個(gè)關(guān)鍵字。當(dāng)向圖（a）所示的B

樹中插入8

時(shí)，該結(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)超過(guò)m-1=4，因此引起結(jié)點(diǎn)分裂，分裂后的樹如圖（c）所示。繼續(xù)向樹中插入11、17，都不會(huì)引起結(jié)點(diǎn)分裂，如圖（d）所示。但當(dāng)向樹中插入13

時(shí)，再次引起分裂，分裂后的樹如圖（f）所示。8.3.4B樹樹表的查找技術(shù)4．B樹的刪除要?jiǎng)h除值為key的關(guān)鍵字，首先在B樹中查找該關(guān)鍵字，其有下列幾種可能的情況。（1）如果當(dāng)前需要?jiǎng)h除的關(guān)鍵字位于非葉子結(jié)點(diǎn)上，則用后繼關(guān)鍵字（這里的后繼關(guān)鍵字均指后繼記錄）覆蓋要?jiǎng)h除的關(guān)鍵字，然后在后繼關(guān)鍵字所在的子支中刪除該后繼關(guān)鍵字。此時(shí)后繼關(guān)鍵字一定位于葉子結(jié)點(diǎn)上，此過(guò)程類似二叉排序樹刪除結(jié)點(diǎn)的方式。（2）如果該結(jié)點(diǎn)關(guān)鍵字個(gè)數(shù)大于或等于?m/2?-1，不需要“合并”結(jié)點(diǎn)，刪除操作結(jié)束，否則進(jìn)行第（3）步。8.3.4B樹樹表的查找技術(shù)（3）如果兄弟結(jié)點(diǎn)關(guān)鍵字個(gè)數(shù)大于?m/2?-1，則父親結(jié)點(diǎn)中的關(guān)鍵字下移到該結(jié)點(diǎn)，兄弟結(jié)點(diǎn)中的一個(gè)關(guān)鍵字上移，如圖（a）所示。（4）如果兄弟結(jié)點(diǎn)關(guān)鍵字個(gè)數(shù)等于?m/2?-1，將父親結(jié)點(diǎn)中的關(guān)鍵字下移與當(dāng)前結(jié)點(diǎn)及它的兄弟結(jié)點(diǎn)中的關(guān)鍵字合并，形成一個(gè)新的結(jié)點(diǎn)，如圖（b）所示。8.3.4B樹樹表的查找技術(shù)在合并過(guò)程中，父親結(jié)點(diǎn)中的關(guān)鍵字會(huì)減少。若父親結(jié)點(diǎn)是根結(jié)點(diǎn)且關(guān)鍵字個(gè)數(shù)減少至0，則直接將根結(jié)點(diǎn)刪除，合并后的新結(jié)點(diǎn)成為根結(jié)點(diǎn)；若父親結(jié)點(diǎn)不是根結(jié)點(diǎn)且關(guān)鍵字個(gè)數(shù)小于?m/2?-1，

又要與父親結(jié)點(diǎn)自己的兄弟結(jié)點(diǎn)進(jìn)行合并，并重復(fù)以上操作，直至整棵樹符合B樹的要求為止。8.3.4B樹04PART散列表的查找技術(shù)8.4.1散列表概述散列技術(shù)在數(shù)據(jù)元素的存儲(chǔ)位置與它的關(guān)鍵字之間建立一個(gè)映射關(guān)系，使得每個(gè)關(guān)鍵字與結(jié)構(gòu)中唯一的存儲(chǔ)位置相對(duì)應(yīng)，記為f(key)=address，并將這種映射關(guān)系f稱為散列函數(shù)，又稱為哈希（hash）函數(shù)。采用散列技術(shù)將記錄存儲(chǔ)在一個(gè)有限的連續(xù)存儲(chǔ)空間中，這塊存儲(chǔ)空間稱為散列表或哈希表（hashtable）。當(dāng)存儲(chǔ)記錄時(shí)，通過(guò)散列函數(shù)計(jì)算出記錄的散列地址；當(dāng)查找記錄時(shí)，同樣通過(guò)散列函數(shù)計(jì)算記錄的散列地址，并按此散列地址查找該記錄。因此，散列技術(shù)既是一種存儲(chǔ)方法，也是一種查找方法。散列函數(shù)可能會(huì)把兩個(gè)，甚至兩個(gè)以上的關(guān)鍵字映射到同一地址，這種情況稱為“散列沖突”；這些發(fā)生沖突的關(guān)鍵字稱為同義詞。一般情況下，沖突只能盡可能地少，而不能完全避免。散列表的查找技術(shù)8.4.2散列函數(shù)設(shè)計(jì)

散列表的查找技術(shù)8.4.2散列函數(shù)設(shè)計(jì)（2）數(shù)字分析法假設(shè)現(xiàn)有學(xué)生生日信息為：1997.02.13、1998.12.13、1997.05.06、1999.10.12……，經(jīng)分析發(fā)現(xiàn)前3位分布不均勻，重復(fù)的可能性大。因此，應(yīng)該選擇分布較為均勻的后幾位作為散列地址。顯然，數(shù)字分析法只適用于已知關(guān)鍵字集合的情況。若更換了關(guān)鍵字集合，就需要重新分析。（3）除留余數(shù)法此方法為最常用的構(gòu)造散列函數(shù)方法。對(duì)于表長(zhǎng)為m的散列表，取一個(gè)整數(shù)p，利用以下的散列函數(shù)把關(guān)鍵字轉(zhuǎn)換成散列地址。f(key)=

keymodp除留余數(shù)法的關(guān)鍵是選好p，使得每個(gè)關(guān)鍵字經(jīng)過(guò)散列函數(shù)轉(zhuǎn)換后盡可能均勻地映射到散列空間中的任一地址。理論研究表明，除留余數(shù)法的模p取不大于表長(zhǎng)m且最接近表長(zhǎng)m的質(zhì)數(shù)時(shí)，效果最好。

散列表的查找技術(shù)8.4.2散列函數(shù)設(shè)計(jì)（4）平方取中法平方取中法是一種常用的散列函數(shù)構(gòu)造方法。該方法先取關(guān)鍵字的平方，然后根據(jù)可使用空間的大小，選取平方數(shù)的中間幾位作為散列地址。該方法得到的散列地址與關(guān)鍵字的每一位都有關(guān)系，散列地址分布比較均勻。這種方法適用于關(guān)鍵字每一位取值都不夠均勻或小于散列地址所需位數(shù)的情況。（5）折疊法折疊法是將關(guān)鍵字從左到右分割成位數(shù)相等的幾部分，然后將這幾部分疊加求和，作為散列地址。這種方法適用于關(guān)鍵字位數(shù)特別多的情況。散列表的查找技術(shù)8.4.2散列函數(shù)設(shè)計(jì)（6）隨機(jī)數(shù)法隨機(jī)數(shù)法設(shè)定散列函數(shù)為：H(key)=Random(key)其中，Random為偽隨機(jī)函數(shù)。此法適用于關(guān)鍵字長(zhǎng)度不等的情況。實(shí)際造表時(shí)，采用何種方法構(gòu)造散列函數(shù)取決于建表的關(guān)鍵字集合的情況（包括關(guān)鍵字的范圍和形態(tài)），以及散列表長(zhǎng)度（散列地址范圍）。不論使用何種方法，都要使產(chǎn)生沖突的可能性盡可能小。散列表的查找技術(shù)8.4.3處理沖突的方法

散列表的查找技術(shù)8.4.3處理沖突的方法下面以一個(gè)例子來(lái)說(shuō)明線性探測(cè)再散列法。假設(shè)散列表表長(zhǎng)m=10，散列函數(shù)為H(key)=key%7，其中key為關(guān)鍵字。采用開放定址法中的線性探測(cè)再散列法解決沖突，依次輸入9個(gè)關(guān)鍵字19,1,22,14,55,68,11,82,40，構(gòu)造散列表如下表所示。首先根據(jù)散列函數(shù)計(jì)算出記錄的地址，再按關(guān)鍵字序列順序依次向散列表中填入。從圖中可知，當(dāng)輸入元素19時(shí)，由于H(19)=5，因此將19放入5號(hào)位置，探測(cè)次數(shù)為1。當(dāng)輸入1時(shí)，H(1)=1，因此將1放入1號(hào)位置，探測(cè)次數(shù)為1。當(dāng)輸入22時(shí)，H(22)=1，但是由于1號(hào)位置已經(jīng)存放元素1，則依次探測(cè)散列表中沒(méi)有存放元素的地址。散列地址0123456789關(guān)鍵字14122

111955688240散列表的查找技術(shù)8.4.3處理沖突的方法②

當(dāng)

di=0,12,-12,22,-22,…,k2,-k2時(shí)，稱為平方探測(cè)（Quadratic

Probing），又稱為二次探測(cè)法。相較于線性探測(cè)再散列法，二次探測(cè)法相當(dāng)于沖突發(fā)生時(shí)探測(cè)長(zhǎng)度為