數據結構（從概念到算法）課件

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

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

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

和high

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

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

mid

=

5

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

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

線性表的查找技術8.2.2折半查找算法由此可見，折半查找在查找成功的情況下進行比較操作的次數最多不超過樹的高度，而判定樹的高度只與有序表中元素個數有關，與元素具體取值無關。接下來，討論折半查找不成功時的平均查找長度。在前面圖中所示的折半查找判定樹所有結點的空指針域加上一個指向實際上并不存在的結點的指針（見右圖），并稱這些實際不存在的結點為外結點，則所有外結點都表示查找不成功的情況。例如，外結點2～3表示待查找關鍵字在第2、第3號結點元素的關鍵字之間時會查找失敗，過程為依次與第5、第2和第3號結點的關鍵字比較后，進入該外結點，共比較3次關鍵字后得到查找失敗的結果。線性表的查找技術8.2.2折半查找算法

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

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

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

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

p

為空時，轉步驟（3），否則重復下列操作。①將key值與p指向結點的關鍵字比較，若相等，則查找成功，返回p。②

若p

結點關鍵字小于

key

值，修改

p

指向

p

的右孩子，轉步驟（2），否則，修改

p

指向

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

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

4

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

是root

的左結點（或者右結點），并且

bottom

也同樣是

pivot

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

是

root

的左結點（或者右結點），而

bottom

卻是

pivot

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

RR

型不平衡樹。RR

型不平衡樹指的是針對一棵初始的平衡樹，在結點右孩子（R）的右子樹（R）上插入新結點，導致結點平衡因子的絕對值大于1。在RR

型不平衡樹中，應當以3

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

Nh-1

+

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

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

的兄弟結點為

S（即父親結點的另一個兒子結點），N

的父親結點為P；S

的左兒子結點為SL，S

的右兒子結點為SR。8.3.3紅黑樹樹表的查找技術如果N

和P

是黑色，則刪除P

導致通過N的路徑都比不通過N的路徑少了一個黑色結點。因為這樣違反性質4，所以樹需要被重新平衡。刪除情景3.1：N是新的根。在這種情景下，從所有路徑去除一個黑色結點，而新根是黑色的，所以性質都能得以保持。在下述刪除情景3.2、刪除情景3.5和刪除情景3.6下，假定N是P的左兒子結點。因為如果N是右兒子結點，則在上述情景中進行左旋和右旋操作對調即可。8.3.3紅黑樹樹表的查找技術刪除情景3.2：兄弟結點S是紅色，替換結點N是父親結點P的左兒子結點。在該刪除情景下，首先為了保證性質3，將S設為黑色，P設為紅色，在N的父親結點上做左旋轉（如果N

是右兒子結點，則在N

的父親結點上做右旋轉），把紅色兄弟轉換成N

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

S

上做右旋轉（如果

N

是右兒子結點，則在

S

上做左旋轉），這樣

S

的左兒子結點成為S

的父親結點和N

的新兄弟結點。我們接著交換S

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

有了一個黑色兄弟結點，它的右兒子結點是紅色的，所以我們進入刪除情景6

進行處理。N

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

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

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

階B

樹插入的過程。5

階B

樹中，除根結點以外的結點最多有4

個關鍵字，最少有2

個關鍵字。當向圖（a）所示的B

樹中插入8

時，該結點的關鍵字數超過m-1=4，因此引起結點分裂，分裂后的樹如圖（c）所示。繼續(xù)向樹中插入11、17，都不會引起結點分裂，如圖（d）所示。但當向樹中插入13

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

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

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

keymodp除留余數法的關鍵是選好p，使得每個關鍵字經過散列函數轉換后盡可能均勻地映射到散列空間中的任一地址。理論研究表明，除留余數法的模p取不大于表長m且最接近表長m的質數時，效果最好。

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

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

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

當

di=0,12,-12,22,-22,…,k2,-k2時，稱為平方探測（Quadratic

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