chapter數(shù)據(jù)集合上的搜索Searching算法實用

會計學(xué)1chapter數(shù)據(jù)集合上的搜索Searching算法實用24.1動態(tài)數(shù)據(jù)集(DynamicSet)與抽象數(shù)據(jù)類型(ADT)靜態(tài)數(shù)據(jù)集（StaticSet）中的數(shù)據(jù)是固定不變的。動態(tài)數(shù)據(jù)集（DynamicSet）則是由不斷變動的同類型數(shù)據(jù)元素組成的數(shù)據(jù)集合。動態(tài)數(shù)據(jù)集（DynamicSet）可以表示為一個數(shù)據(jù)元素的數(shù)組：

classDynamicSet{intsetSize;Object[arraySize]elements;...}//Object為數(shù)據(jù)元素的類型，setSize為當(dāng)前集合中的元素個數(shù)第1頁/共91頁3用數(shù)組表示集合操作方便，但當(dāng)集合中的元素個數(shù)不斷增加時，數(shù)組的長度必須擴大。一般采用空間倍增（arraydoubling）技術(shù)，即另外申請一個加倍長度的新數(shù)組，把集合中的數(shù)據(jù)傳送過來，取代原有的空間。其過程為：

arrayDouble(set){newSize=2*arraySize;newElements=newObject(newSize);Transferallelementsfromtheset.elementstothenewElement;set.elements=newElements;set.setSize=newSize;}更為靈活的存儲形式是利用指針和鏈表（例如線性鏈表和樹結(jié)構(gòu)），這種存儲形式在搜索算法中經(jīng)常用到。第2頁/共91頁4搜索問題：在集合中檢索出其關(guān)鍵字域的值等于給定值的數(shù)據(jù)元素。已知：動態(tài)數(shù)據(jù)集類型DynamicSet的一個實例set和值x。求：集合set中一個元素Objectelement，使element.key=x。數(shù)據(jù)集合上的操作（operation）可以分為兩類：查詢（queries）操作：對數(shù)據(jù)集不做任何變動，僅僅返回有關(guān)集合的某些信息；修改（modifyingoperations）操作：要對數(shù)據(jù)集合的某些域進行改動。一些典型的操作：

Search(S,k)：搜索，一個查詢操作。對于給定的數(shù)據(jù)集合S和一個關(guān)鍵字值k，返回S中一個元素（element）的指針x，使得x->key=k。當(dāng)S中沒有符合條件的元素時，返回的指針為空（NULL）。第3頁/共91頁5

Insert(S,x)：插入，一個修改操作。把由x指向的數(shù)據(jù)元素加入到集合S中，一般假定在x指向的數(shù)據(jù)元中，與集合運算相關(guān)的所有分量（域）都已經(jīng)初始化。

Delete(S,x)：刪除，一個修改操作。給定指向集合S中一個元素的指針x，將此元素從S中刪除。

Minimum(S)：求最小元，一個查詢操作。若集合S中所有數(shù)據(jù)元素的關(guān)鍵字值為一全序集，則返回具有最小關(guān)鍵字值的數(shù)據(jù)元素的指針。

Maximum(S)：求最大元，一個查詢操作。返回具有最大關(guān)鍵字值的數(shù)據(jù)元素的指針。

Deletemin(S)：刪除最小元，一個修改操作。它相當(dāng)于Minimum(S)和Delete(S,x)的聯(lián)合，即：Delete(S,Minimum(S))。第4頁/共91頁6Successor(S,x)：求后繼數(shù)據(jù)元，一個查詢操作。若S中的數(shù)據(jù)元素按關(guān)鍵字值從小到大排列，x是指向S中某一數(shù)據(jù)元素的指針，則返回x所指向的數(shù)據(jù)元素的下一個數(shù)據(jù)元素的指針。若x指向最后一個數(shù)據(jù)元素，則返回NULL。

Predecessor(S,x)：求前導(dǎo)數(shù)據(jù)元，一個查詢操作。返回x所指向的數(shù)據(jù)元素的前一個數(shù)據(jù)元素的指針。若x指向第一個數(shù)據(jù)元素，則返回NULL。搜索算法（及相關(guān)操作算法）的設(shè)計實際上是實現(xiàn)適合各種不同應(yīng)用需要的ADT，例如：字典（Dictionary）作為抽象數(shù)據(jù)類型，可以分為兩類：

·靜態(tài)字典：（靜態(tài)數(shù)據(jù)集S，Search）；

·動態(tài)字典：（動態(tài)數(shù)據(jù)集S，Search，Insert，Delete）。優(yōu)先隊列（PriorityQueue）：（動態(tài)數(shù)據(jù)集S，Insert，Deletemin）。第5頁/共91頁74.2二叉搜索樹二叉搜索樹又稱為二元字典樹，是一種最常用的動態(tài)數(shù)據(jù)集的數(shù)據(jù)結(jié)構(gòu)，可以用于實現(xiàn)字典和優(yōu)先隊列等ADT。4.2.1二叉搜索樹（BinarySearchTrees）

BST的一個結(jié)點與一個數(shù)據(jù)項相對應(yīng)，除了數(shù)據(jù)項Object或數(shù)據(jù)項的指針之外，結(jié)點主要由關(guān)鍵字key域和指針域組成，即關(guān)鍵字key與指針left、right和p，三個指針分別指向該結(jié)點的左兒子、右兒子和父結(jié)點。BST中結(jié)點的關(guān)鍵字值應(yīng)滿足BST性質(zhì)：即，設(shè)x是二叉搜索樹的一個結(jié)點，結(jié)點y位于結(jié)點x的子樹中，x、y的關(guān)鍵字值應(yīng)滿足以下關(guān)系：第6頁/共91頁8如果y是x的左子樹中的一個結(jié)點，則y->key≤x->key；如果y是x的右子樹中的一個結(jié)點，則y->key>x->key。Fig.4.1給出了由6個結(jié)點（數(shù)據(jù)項）組成的兩個二叉搜索樹。兩個BST(a)和(b)有不同的樹高，前者比后者的查詢效率更高。第7頁/共91頁9遍歷二叉搜索樹的所有結(jié)點可以采用中序遍歷（inordertreewalk）算法，即可將與二叉搜索樹樹結(jié)點相對應(yīng)的數(shù)據(jù)項按關(guān)鍵字從小到大排列出來。中序遍歷（Inorder_Tree_Walk）算法4.2.2查詢（Querying）的實現(xiàn)對二叉搜索樹的查詢主要是Search、Minimum、Maximum、Successor、Predecessor等操作，這些操作都可在O(h)時間內(nèi)完成，其中h是二叉樹的高。如Fig.4.2所示，BST查詢操作為Tree_Search(root,k)，即搜索BST上關(guān)鍵字值為k的結(jié)點。

Tree_Search算法第8頁/共91頁10求最小元（或最大元）的操作只需從根開始沿著左指針（或右指針）一直搜索至某一結(jié)點x，其left或right指針為NULL，這時結(jié)點x的關(guān)鍵字x->key為最?。ɑ蜃畲螅Ｇ笞钚≡乃惴═ree_Minimum(root)求最大元的算法Tree_Maximum(root)求數(shù)據(jù)項的后繼與前導(dǎo)項的操作要相對復(fù)雜，如Fig.4.2，結(jié)點15（指關(guān)鍵字為15的結(jié)點)的后繼是結(jié)點17，它是結(jié)點15的右子樹中的最小元。然而對于沒有右子樹的結(jié)點，例如13、4和17，其后繼分別為15、6和18，顯然計算這三個結(jié)點的后繼時需要使用父結(jié)點指針x->p。求后繼項的操作算法Successor(x)

第9頁/共91頁11Successor(x)操作根據(jù)條件x->right!=NULL決定兩種情形：第一種情況從結(jié)點x下行，直到葉結(jié)點，其路長顯然不超過樹高h；第二種情況從結(jié)點x上行，路長同樣不超過h。因此有下面的結(jié)論：定理4.1

動態(tài)數(shù)據(jù)集合的查詢操作Search、Minimum、Maximum、Successor、Predecessor可通過二叉搜索樹實現(xiàn)，其算法可在O(h)時間內(nèi)完成，其中h為二叉搜索樹的高。4.2.3插入與刪除操作動態(tài)數(shù)據(jù)集上的Insert(S,x)、Delete(S,x)操作與查詢操作不同，它們會引起二叉搜索樹本身的變化。插入操作算法Tree_Insert第10頁/共91頁12Fig.4.3表示把新的數(shù)據(jù)項14（關(guān)鍵字值為14）作為新結(jié)點插入到二叉搜索樹的過程。第11頁/共91頁13從二叉搜索樹中刪除一個結(jié)點的算法比較復(fù)雜，假定待刪除結(jié)點指針z不為NULL，有三種情形：（1）結(jié)點z沒有子結(jié)點，可直接刪除；（2）結(jié)點z只有一個子結(jié)點，可使z的父結(jié)點z->p直接指向z的子結(jié)點z->left或z->right；（3）結(jié)點z有兩個子結(jié)點，則z的后繼結(jié)點y必然在z的右子樹中，且y無左子結(jié)點，按步驟（1）或（2）刪除結(jié)點y，用y的數(shù)據(jù)取代z的數(shù)據(jù)。過程如圖所示：第12頁/共91頁14第13頁/共91頁15刪除操作算法Tree_Delete這個算法除了調(diào)用函數(shù)Tree_Successor(root,z)的時間代價為O(h)外，其余各處的時間代價均為O(1)階。Tree_Insert(root,z)的運行是在從根到某一個葉結(jié)點的一條路徑上進行的，因此有下面的結(jié)論。定理4.2

動態(tài)數(shù)據(jù)集的Insert(S,x)、Delete(S,x)操作可通過二叉搜索樹實現(xiàn)，其算法可在O(h)時間內(nèi)完成，其中h為二叉搜索樹的高。第14頁/共91頁164.3隨機二叉搜索樹隨機二叉搜索樹（RandomlyBuiltBinarySearchTree）：一個由n個結(jié)點（具有n個不同的關(guān)鍵字）按隨機順序，經(jīng)過n次Tree_Insert操作插入到一個原始空樹而得到的二叉搜索樹，稱為隨機二叉搜索樹（RBST）。這里的按隨機順序是指，n個不同關(guān)鍵字的n!種不同排列的出現(xiàn)是等可能的。定理4.3

由n個不同的關(guān)鍵字組成的隨機二叉搜索樹的平均樹高為h=O(logn)。該定理的證明基本思路與步驟：1.有關(guān)概率分布的假設(shè)：假定關(guān)鍵字輸入序列k1,k2,...,kn為n個不同值的一種排列，設(shè)各種不同排序為等可能的，因此這一特定排序出現(xiàn)的可能性為1/n!。第15頁/共91頁17假定：對任一j值（1≤j≤n），kj取n個關(guān)鍵字其中任意一個的概率為1/n，也是等可能的。2.

在RBST中結(jié)點x為結(jié)點y的祖先的充要條件：首先分析從根到樹上任一結(jié)點y（y->key=kj,1<j≤n）的路徑上的結(jié)點特征。分析的結(jié)果是，在這條路上的每個結(jié)點x（x->key=ki）都具有下列特征：

·其對應(yīng)的關(guān)鍵字ki在輸入關(guān)鍵字序列中位于kj之前，即1≤i<j≤n；

·ki值必為兩種情形之一：

①ki是k1,k2,...,ki中大于kj的若干值中的最小者；

②ki是k1,k2,...,ki中小于kj的若干值中的最大者。上述情形是充分必要的，它可以敘述為：命題4.1

設(shè)二叉搜索樹T是依次把不同關(guān)鍵字k1,k2,...,kn插入到一個原始為空的二叉搜索樹而得到的結(jié)果，則結(jié)點x（x->key=ki）在T中是結(jié)點y（y->key=kj）的祖先的充要條件是：第16頁/共91頁18在Fig.4.5中，kj=17。從圖(a)中可以看到，從根到結(jié)點17的路徑上的4個結(jié)點的關(guān)鍵字都符合上述條件，而且，從(b)表中的關(guān)鍵字序列中可以看出，關(guān)鍵字17前面的10個關(guān)鍵字中滿足命題4.1條件的關(guān)鍵字21、19、9、12全是結(jié)點17的祖先。第17頁/共91頁193.求RBST中任一結(jié)點的深度d(kj,T)：從命題4.1立即可以計算出T中任一（與關(guān)鍵字kj對應(yīng)的）結(jié)點的深度d(kj,T)恰恰等于滿足命題4.1條件的（祖先）結(jié)點的個數(shù)，即：命題4.2

在上述的隨機二叉搜索樹T中，對于給定的關(guān)鍵字kj(1≤j≤n)，令即kl是所有的先于ki輸入并大于kj的值；令即kl是所有的先于ki輸入并小于kj的值。則從根到y(tǒng)（y->key=kj）的路徑上，結(jié)點的關(guān)鍵字集合恰為Gj∪Lj，且d(kj,T)=|Gj|+|Lj|。第18頁/共91頁20從Fig4.5的實例中可以看到，對于kj=17，Gj={21，9}，Lj={9。12}，所以kj的深度為4。第19頁/共91頁214.4紅黑樹（Red-BlackTree）4.4.1Red-Black樹的性質(zhì)

Red-Black(RB)樹是一種二叉搜索樹，它的每個結(jié)點有五個域：color（取值為red或black）、key、left、right和p（省略了相關(guān)數(shù)據(jù)或指針）。RB樹把包含key域的結(jié)點作為內(nèi)部結(jié)點，而以NULL（空）作為其“外部結(jié)點”，這些外部結(jié)點與left、right、p域中的NULL指針值相對應(yīng)（見Fig.4.6），空結(jié)點與實際的數(shù)據(jù)元素或關(guān)鍵字都無關(guān)。一個在結(jié)構(gòu)上做了上述改變的二叉搜索樹稱為一個RB樹。第20頁/共91頁22第21頁/共91頁23RB樹滿足下面的性質(zhì)：1.每個結(jié)點的color域必須為red或black；2.每個葉結(jié)點（NULL）的color為black；3.如果一個結(jié)點的color為red，則其子結(jié)點全為black結(jié)點。4.從某一結(jié)點到其子樹上任意一個葉結(jié)點的所有簡單路徑，包含相同個數(shù)的black結(jié)點。從一個結(jié)點x到（其子樹中的）任一葉結(jié)點的簡單路徑上的黑結(jié)點的個數(shù)稱為結(jié)點x的black高（black-height），表示為bh(x)。定理4.4

具有n個內(nèi)部結(jié)點的RB樹的樹高h≤2ln(n+1)。證明：1.首先用歸納法證明以RB樹上任一結(jié)點x為根的子樹至少包含個內(nèi)部結(jié)點。第22頁/共91頁241°遞歸基礎(chǔ)：對于高度為0的結(jié)點x，即x為葉結(jié)點（NULL），以其為根的子樹有0個內(nèi)部結(jié)點，即至少有個內(nèi)部結(jié)點。命題成立。2°設(shè)對于高度為h-1的結(jié)點命題成立。3°考察高為h(>0)的結(jié)點x，由于h>0，x是RB樹的內(nèi)部結(jié)點，必有兩個子結(jié)點x1、x2，其高為h-1，且有根據(jù)歸納假設(shè)，以x1、x2為根的兩子樹分別至少有個內(nèi)部結(jié)點，∴以x為根的子樹至少有個內(nèi)部結(jié)點?！鄽w納完成。第23頁/共91頁252.證明對于RB樹的根r，設(shè)其高為h，bh(r)≥h/2。這一點由性質(zhì)3，即從根到葉的任一條路上，red結(jié)點數(shù)不超過一半即可證明。3.由上面兩個命題可知：高為h的RB樹，其內(nèi)部結(jié)點數(shù)n至少為，即。故有，定理得證。定理4.4說明，動態(tài)數(shù)據(jù)集上的基本操作在RB樹上的執(zhí)行代價為O(h)=O(logn)階。換句話說，用RB樹的形式實現(xiàn)動態(tài)數(shù)據(jù)集，在任何時刻，樹高h總能保持在O(logn)階。第24頁/共91頁264.4.2Red-Black樹的插入與刪除算法

在插入或刪除結(jié)點時，為了使樹重新具有Red-Black性質(zhì)，除了要改變結(jié)點間的指針鏈接關(guān)系外，還要對某些結(jié)點的著色進行調(diào)整。對于結(jié)點間指針鏈接關(guān)系的修改歸結(jié)為旋轉(zhuǎn)（Rotation）操作，旋轉(zhuǎn)是調(diào)整樹的平衡狀態(tài)的基本手段。Rotation操作對二叉搜索樹上的某一局部進行調(diào)整，通過交換一對父子結(jié)點的父子關(guān)系，在保持樹結(jié)點間的有序關(guān)系的條件下（即保持其中序遍歷的結(jié)果為單調(diào)序列），改變該子樹的平衡狀態(tài)。第25頁/共91頁27Rotation操作分為左旋（Left-Rotation）和右旋(Right-Rotation)，如Fig.4.7所示。第26頁/共91頁28左旋算法Left_Rotation(root,x)Fig.4.8給出一次左旋轉(zhuǎn)的實例的圖示。Right_Rotation(root,x)的算法與Left_Rotation(root,x)類似。第27頁/共91頁29這個算法主要完成兩件事：1°把結(jié)點x與其左子結(jié)點y的父子關(guān)系進行調(diào)整，即把x->p—x—y的父子關(guān)系改變?yōu)閤->p—y—x的順序；2°把y的左子樹變?yōu)閤的右子樹。算法不存在與結(jié)點數(shù)n相關(guān)的操作，因此時間代價為O(1)階。RB樹的插入操作，首先調(diào)用Tree_Insert(root,x)函數(shù)完成二叉搜索樹的插入操作，然后調(diào)用Tree_Rotation(root.x)函數(shù)，并對結(jié)點的著色進行調(diào)整，使之恢復(fù)為一個RB樹。插入操作算法RB_Insert(root,x)

第28頁/共91頁30Fig.4.9給出了一個簡單的實例，作為RB_Insert()算法運行的示意圖。第29頁/共91頁31從算法RB_Insert()的執(zhí)行過程可以看出：1°對于空樹或插入后x->p為black結(jié)點的情形，無需進一步處理；2°x->p為red結(jié)點時，首先按case1處理，對以x->p->p為根的子樹進行調(diào)整，然后向上擴展，分別按case2、case3處理。RB樹的Delete算法與RB_Insert()算法的思路是一致的，首先按二叉搜索樹的刪除方法刪去需要刪除的結(jié)點。在刪除過程中會出現(xiàn)三種情形，在第二、三種情形中，若被摘除（spliced-out）結(jié)點是black結(jié)點，這時Red-Black性質(zhì)4可能被破壞，就需要對RB樹進行恢復(fù)，恢復(fù)方法與插入操作后的修復(fù)類似。第30頁/共91頁324.4.3關(guān)于Red-Black樹的幾點討論

1.

RB樹是一種二叉搜索樹，在其上進行的查詢操作Search、Minimum、Maximum、Successor、Predecessor等與一般二叉搜索樹的查詢操作完全相同，而且算法簡明，也即RB樹具有一般二叉搜索樹的優(yōu)點。2.如定理4.4所指出的，RB樹是平衡樹，在其上進行的所有操作的時間代價都是O(logn)階的，RB樹的樹高h總是保持在一個很小的范圍，即h≤2ln(n-1)。3.

RB樹與一般平衡樹的平衡機制不同，雖然它不需要計算平衡因子，但Red-Black性質(zhì)（特別是性質(zhì)4）保證了整棵樹的平衡性，即絕大多數(shù)內(nèi)部結(jié)點有兩個子結(jié)點。事實上，red結(jié)點不可能僅有一個black子結(jié)點，而只可能為以下兩種情形之一：有兩個black（數(shù)據(jù)）子結(jié)點；或左、右子結(jié)點均為NULL。第31頁/共91頁33black結(jié)點的子結(jié)點有三種情形：有兩個（數(shù)據(jù)）子結(jié)點；左右子結(jié)點為NULL；第三種情形只可能出現(xiàn)在樹的下層，只有一個數(shù)據(jù)子結(jié)點，這時該子結(jié)點必為red，且子結(jié)點左右兒子為空。如Fig.4.10所示。RB樹幾乎是一個2-樹，不可能出現(xiàn)單鏈的情形，從而保證了整棵樹的平衡性。4.另一種非二叉的平衡搜索樹——2-3-4樹，很容易轉(zhuǎn)變?yōu)镽ed-Black樹。第32頁/共91頁344.52-3-4樹4.5.12-3-4樹及其實例

1.

2-3-4樹有三種不同的結(jié)點：2-結(jié)點、3-結(jié)點和4-結(jié)點。2-結(jié)點與二叉樹的結(jié)點相同，除了關(guān)鍵字域key外，有三個指針域p、p1、p2，p指針指向父結(jié)點、p1指針為左指針、p2指針為右指針。另外增加一個結(jié)點類型域type，用來區(qū)分結(jié)點類型。數(shù)據(jù)域保持?jǐn)?shù)據(jù)元素的內(nèi)容或指向數(shù)據(jù)元素的指針。3-結(jié)點有兩個關(guān)鍵字域key1和key2，其中key1<key2，并增加一個指針域p3。當(dāng)搜索結(jié)點x時，用x->key與key1、key2進行比較，如相等即找到，不相等則根據(jù)比較結(jié)果的三種情形轉(zhuǎn)入該結(jié)點的子樹：

x->key<key1轉(zhuǎn)向p1；

key1<x->key<key2轉(zhuǎn)向p2；

x->key>key2轉(zhuǎn)向p3。第33頁/共91頁354-結(jié)點與3-結(jié)點類似，增加了key3域和p4指針。在2-3-4樹種，4-結(jié)點是一種臨時結(jié)點，在插入和刪除過程中可能產(chǎn)生4-結(jié)點，但該結(jié)點可隨時由三個2-結(jié)點取代。2.2-3-4樹的最主要的特征是其所有的葉結(jié)點都在同一深度。如Fig.4.11所示：假定動態(tài)數(shù)據(jù)集的關(guān)鍵字值域為英語字母集合，即從小到大為A,B,C,D,E,...,X,Y,Z。圖中的結(jié)點I是根，是一個2-結(jié)點，其左子樹中的關(guān)鍵字值均小于I，右子樹中的關(guān)鍵字值均大于I，該樹T中只有2-結(jié)點和3-結(jié)點。第34頁/共91頁364.5.22-3-4樹上的查詢操作算法

2-3-4樹上的搜索算法與二叉搜索樹上的搜索算法差別不大，只需要區(qū)別2-結(jié)點和3-結(jié)點。2-3-4樹的搜索算法4.5.32-3-4樹的構(gòu)造過程

2-3-4樹的插入算法是保證樹的基本特征（即所有葉結(jié)點在同一深度）的關(guān)鍵。在插入時，2-結(jié)點可以變?yōu)?-結(jié)點，3-結(jié)點可以變?yōu)?-結(jié)點，當(dāng)出現(xiàn)4-結(jié)點時，自動分裂為三個2-結(jié)點，并且把中間的2-結(jié)點插入到上一層的父結(jié)點中。在一般二叉搜索樹中，每插入一個結(jié)點是在最下層添加一個葉結(jié)點，而2-3-4樹是在整體擴大的情況下進行向上擴展。每當(dāng)樹增加一層時，即是把根結(jié)點上升一層，于是樹中所有結(jié)點的深度同時加1。第35頁/共91頁37第36頁/共91頁38在插入算法中，一旦產(chǎn)生了4-結(jié)點就要進行分裂，這時就會利用到父結(jié)點指針p。在4-結(jié)點分裂時，存在三種情形：(1)4-結(jié)點是2-3-4樹的根，這時，中間的2-結(jié)點作為新的根，樹增加一層；(2)4-結(jié)點的父結(jié)點是一個2-結(jié)點，只需把4-結(jié)點中的中間關(guān)鍵字插入到2-結(jié)點，該2-結(jié)點變?yōu)?-結(jié)點；(3)4-結(jié)點的父結(jié)點是一個3-結(jié)點，把4-結(jié)點的中間關(guān)鍵字插入到這個3-結(jié)點中，該3-結(jié)點又變成一個新的4-結(jié)點，于是繼續(xù)向上分裂。假設(shè)插入時樹高為h，插入過程在最壞情形下是從根到葉、再從葉到根，至多進行2h次處理，因此插入算法的時間代價仍是O(h)階的。第37頁/共91頁394.5.42-3-4樹的性能分析

定理4.5

由n個關(guān)鍵字生成的2-3-4樹實際上是一個完全的2-3樹，設(shè)其高為h，結(jié)點數(shù)為m，則其結(jié)點數(shù)m介于同樣高度為h的完全二叉樹和完全三叉樹的結(jié)點數(shù)之間，即：2h+1-1≤m≤(3h+1-1)/2且關(guān)鍵字個數(shù)n≥m，故有n≥2h+1-1即h≤ln(n+1)-1或h=θ(logn)，定理得證。由定理4.5可知，2-3-4樹上的基本操作的代價在最壞情形下也是O(logn)階的。4.5.5有關(guān)2-3-4樹的幾點討論

1.

2-3-4樹實際上是一種2-3樹，4-結(jié)點是臨時結(jié)點，不會占用較多空間，可以分配臨時性的工作單元存放4-結(jié)點。第38頁/共91頁402.可以采用同一種數(shù)據(jù)類型來表示2-結(jié)點和3-結(jié)點（按3-結(jié)點來設(shè)計），只在type域用不同的標(biāo)記來區(qū)分結(jié)點類型即可。3.為了減少插入算法的代價，還有一種把分裂4-結(jié)點的工作分?jǐn)偟讲煌牟僮髦腥サ姆桨?，即每次生?-結(jié)點時進行一次分裂，如果其父結(jié)點又變?yōu)?-結(jié)點，則不在這一次插入操作中繼續(xù)分裂。當(dāng)進行下次插入或搜索操作時，每遇到一個4-結(jié)點就進行一次分裂，這樣可以減少一次插入操作的代價。4.與插入算法相比，刪除操作Delete算法是一個逆過程。插入操作中，關(guān)鍵字要按規(guī)則逐層向上插入，而刪除操作應(yīng)在刪除其關(guān)鍵字后按一定規(guī)則逐層向下壓，第39頁/共91頁415.

2-3-4樹獲得平衡性的方法很巧妙，但缺點是結(jié)點類型較為復(fù)雜，可以通過一種簡單的變換把2-3-4樹轉(zhuǎn)化為二叉搜索樹。方法是把2-3-4樹中的3-結(jié)點（或4-結(jié)點）用一個2-結(jié)點結(jié)構(gòu)來取代，取代的方法如Fig.4.13所示。第40頁/共91頁42用上述變換將Fig.4.11中的2-3-4樹轉(zhuǎn)化為一個二叉搜索樹，不難發(fā)現(xiàn)，這是一棵RB樹。從中也可以看出RB樹與2-3-4樹的內(nèi)在聯(lián)系。第41頁/共91頁434.6Hashing技術(shù)4.6.1Hash算法的基本思想與一般模型

Hash方法的基本思想是，首先產(chǎn)生從可能的關(guān)鍵字集合（又稱全域）U=[0..N-1]到存儲空間（Hash表）地址集合T=[0..m-1]的一個映射函數(shù)：h:U[0..m-1]。于是，要存儲或檢索關(guān)鍵字為x∈U的數(shù)據(jù)項只需計算函數(shù)h(x)，直接得到該數(shù)據(jù)項應(yīng)在的地址。Fig.4.15中給出了一個簡單的實例，其中N=100，m=7，h(x)=xmod7。第42頁/共91頁44然而對不同的關(guān)鍵字x,y∈U，h(x)=h(y)的情況可能出現(xiàn)，這種情形稱為沖突（collision）。由于一般的|U|遠遠大于m，沖突難以避免，因此Hash技術(shù)研究的基本問題是：(1)設(shè)計一個好的Hash函數(shù)，計算簡單，而又使數(shù)據(jù)項分布均勻以減少沖突；(2)設(shè)計解決沖突的策略和算法。集合為實際存于Hash表中的關(guān)鍵字集合，|S|=n≤N。=n/m稱為負載因子（loadfactor）,值是決定哈希算法性能的主要因素。Hash算法的“散列”存儲方式，使得它不能支持Minimum、Maximum、Successor、Predecessor、Mindelete這類的操作，而對于Search、Insert、Delete操作不但可以支持而且有較高的性能。第43頁/共91頁45從抽象數(shù)據(jù)類型（ADT）的觀點來說，Hash算法用于實現(xiàn)字典（Dictionary）類型，實際關(guān)鍵字集合S為固定不變時，稱為靜態(tài)字典，只支持Search操作，S為可變時，即動態(tài)數(shù)據(jù)集，稱為動態(tài)字典，動態(tài)字典支持搜索、插入和刪除操作。4.6.2Hash函數(shù)的設(shè)計

Hash函數(shù)的設(shè)計一般應(yīng)能兼顧計算簡單和分布均勻，在大多數(shù)應(yīng)用問題中，可能的關(guān)鍵字集合U往往遠遠大于地址空間的規(guī)模。例如以姓名字符串作為關(guān)鍵字，|U|=N是一個極大的值，而Hash表的長度m和實際關(guān)鍵字集合S（|S|=n）與N相比小得多。因此，分布均勻的要求就是要對于使盡量小，其中h-1(i)為被h映射至地址i的關(guān)鍵字全體。第44頁/共91頁46當(dāng)且僅當(dāng)時達到最小值，意味著將無任何沖突產(chǎn)生。無沖突的Hash函數(shù)稱為完備Hash函數(shù)（PerfectHashFunction），簡稱PHF。事實上，無沖突的要求是極難達到的。“生日悖論”指出，在23個人中，有兩個人的生日在同一天的概率為0.51，即當(dāng)|S|=n=23，m=365時，發(fā)生沖突的概率已經(jīng)在50%以上。而當(dāng)n=50時，發(fā)生沖突的概率已達0.97。在D.Knuth所舉的實例中指出，當(dāng)n=31，m=41時，無沖突的映射函數(shù)只占全部可能映射函數(shù)的1/107。因此，在大多數(shù)情形下只能追求將沖突盡可能減少。常用的Hash函數(shù)設(shè)計方法：1.除式法（Divisionmethod）令h(x)取用m除x的余數(shù)，即h(x)=xmodm。第45頁/共91頁47這種Hash函數(shù)計算速度最快。在設(shè)計時，m取值不要習(xí)慣性地取為2的n次冪。因為這會使得h(x)的取值只依賴于關(guān)鍵字的2進制值的最后幾位，這不利于數(shù)據(jù)在Hash表中的均勻分布。一般情況下m值最好取為不與某個2n值相近的素數(shù)。2.

乘式法（Multiplicationmethod）可方便地取m=2p，映射函數(shù)可表示為：其中a為常數(shù)0<a<1，表示取乘積的分?jǐn)?shù)部分，即。常數(shù)a的選取會影響到Hash函數(shù)的性能，如何選取a的值與關(guān)鍵字值的特征有關(guān)。已有的研究指出取最好。此時，Hash函數(shù)表示為：例如，取m=1024，當(dāng)x=42237時，

h(x)=h(42237)=1024×42237×0.618mod1=477

即關(guān)鍵字x=42237映射到Hash表T[0...1023]中的位置是T[477]。第46頁/共91頁483.

位選取法（Hash-bitExtraction）和平方取中法（Mid-square）基本思想是：把地址空間T的大小m取作m=2p，p為某整數(shù)，例如m=216，即T[0..65535]。無論關(guān)鍵字x為數(shù)字或字符串，都一定可以轉(zhuǎn)變?yōu)橐粋€較長的二進制串，那么h(x)的值就可以取與關(guān)鍵字對應(yīng)的二進制串中指定的16位所形成的二進制數(shù)。經(jīng)常采用的平方取中法的基本思想則是，首先計算關(guān)鍵字值的平方x2，在平方值的二進制序列中取中間的若干位，例如：U=[0..999]，x=459，m=28，

x2=4592=(210681)10=(110011011100000101)2

則h(x)=(1101110000)2=880由于在定義函數(shù)h(x)時，到底選取二進制序列的哪些位帶有任意性，映射后的地址可能有較均勻的分布，使得沖突減少。第47頁/共91頁494.6.3解決沖突的策略不同策略之間的主要區(qū)別是：(1)沖突項存到何處：一種方法是把它們?nèi)源娴紿ash表中；另一種方法則是另開辟溢出區(qū)（或鏈區(qū)）存放溢出數(shù)據(jù)。(2)如何從地址h(x)找到?jīng)_突項的存儲位置：一種方法是仍用計算的方式一次次地計算沖突項的地址；另一種方法就是用指針形成鏈表。1.開地址法（Openaddressing）開地址法是一種單區(qū)法，不需要額外的存儲空間，沖突項放在Hash表T[0..m-1]的其它空位，數(shù)據(jù)元素存儲位置的確定也通過Hash函數(shù)計算。這時Hash函數(shù)的自變量除了關(guān)鍵字之外，還有一個查找序號i，最簡單的映射方法稱作線性查找Hash函數(shù)：，i=0,1,2,...。第48頁/共91頁50例如：設(shè)h‘(x)=(5x)mod8，關(guān)鍵字為6個年代：1055、1492、1776、1812、1918、1945。直接存入Hash表會產(chǎn)生一次沖突：x=1492、x=1812都映射到地址4，如Fig.4.16所示。采用線性開地址方法，函數(shù)h(x,i)把這6個關(guān)鍵字依次插入到表中。每次插入過程中，剛開始時i的取值為0，若T[h(x,0)]為空則進行插入，若T[h(x,0)]已被占用，i值加1，繼續(xù)檢查T[h(x,1)]是否也被占用，如此重復(fù)直到完成。Hash表的插入算法Hash_Insert

第49頁/共91頁51該實例中，Hash_Insert(T,x)的執(zhí)行過程為：h(1055,0)=h'(1055)=3存入T[3]；h(1492,0)=4存入T[4]；h(1776,0)=0存入T[0]；h(1812,0)=4，已占用h(1812,1)=5存入T[5]；h(1918,0)=6存入T[6]；h(1945,0)=5，已占用h(1945,1)=6，已占用h(1945,2)=7存入T[7]。Fig.4.17為執(zhí)行結(jié)果。第50頁/共91頁52線性開地址法的搜索算法Hash_Search

另一種更一般的開地址函數(shù)稱為二次Hashing函數(shù)（DoubleHashing），其映射函數(shù)表示為：這種Hash函數(shù)緩解了由于順序查找空位造成的Hash表的局部擁擠現(xiàn)象，適當(dāng)選擇h2(x)，可以使查找序列也具有隨機性，有利于提高查找算法的性能。例如：在插入關(guān)鍵字=1613的過程中，當(dāng)?shù)刂穐(x,i)已被其它關(guān)鍵字占用時，查找空位的下標(biāo)序列為：1、9、4、12、7、2、10、5、0、8、3、11、6…，顯然折衷方案有利于關(guān)鍵字在Hash表中的均勻分布。不過在選擇h1(x)和h2(x)時必須使上述的查找空位的下標(biāo)序列遍歷整個Hash表。為此可設(shè)計映射函數(shù)為：其中取m為一素數(shù)，m'為略小于m的整數(shù)。第51頁/共91頁53開地址Hashing算法的分析分兩種情形：當(dāng)動態(tài)數(shù)據(jù)集的所有數(shù)據(jù)的關(guān)鍵字都被映射到同一地址時，最壞情形發(fā)生，這時的時間代價顯然是O(n)階的。由于影響問題的因素有：Hash函數(shù)的選擇、沖突的處理策略、關(guān)鍵字集合S在全集U中的分布情形和Hash表的大小，計算Hash函數(shù)的平均時間代價較難，但最為重要。均勻Hashing（uniformhashing）為了對開地址Hash算法的搜索與插入時間代價進行統(tǒng)一概率分析，首先要假定它是一種均等狀態(tài)。即假定：每個關(guān)鍵字有相同的機會被映射到Hash表的不同位置；每個關(guān)鍵字的查找下標(biāo)序列，應(yīng)等可能的作為0,1,...,m-1的一個排列。第52頁/共91頁54命題4.3

在uniformhashing的條件下，對于開地址Hash表的不成功搜索（或插入）操作所需的期望查找（probes）次數(shù)至多為次，其中。命題4.4

在uniformhashing的條件下，對于開地址Hash表的成功搜索操作所需的期望查找（probes）次數(shù)至多為次，其中。對于Hash表的不成功搜索，指搜索的關(guān)鍵字x不在表中，因此查找的代價應(yīng)與插入一個新數(shù)據(jù)項的代價相同。命題說明：利用Hash技術(shù)實現(xiàn)的字典抽象數(shù)據(jù)類型（ADT），其搜索和插入代價與數(shù)據(jù)項數(shù)n無關(guān)，也就是說時間代價是O(1)階的。這說明了對于大數(shù)據(jù)集合的組織與檢索，Hash技術(shù)的效率優(yōu)于平衡樹。第53頁/共91頁55負載因子的值對算法性能有影響，在接近于1時，算法性能明顯降低。很小會浪費存儲空間，接近于1則算法性能降低，所以應(yīng)取適當(dāng)?shù)闹?。開地址法有增加沖突鏈長的趨勢。例如在Fig4.17的例子中，關(guān)鍵字x=1945，本應(yīng)第一次就映射到T[5]，但T[5]卻被本應(yīng)映射到T[4]的關(guān)鍵字1812所占，因此1945不得不放到T[7]的位置，去占用“本不該屬于它的位置”。這種“喧賓奪主”的現(xiàn)象擴大了因沖突造成的負面影響。而鏈接法避免了這種缺陷。第54頁/共91頁562.鏈接法（Chainedhashing）又稱閉地址法。它打破了數(shù)據(jù)項存于Hash表T[0..m-1]之內(nèi)的限制。實際上它是一個雙區(qū)法，即沖突項不存于表內(nèi)。這時的T是一個由m個鏈表組成的數(shù)組，T[i](i=0,1,...,m-1)表示映射到地址i的關(guān)鍵字序列，也可以把T[i]作為這個鏈表的首項（或頭指針）。第55頁/共91頁57在這種情況下，表長m可以小于數(shù)據(jù)集S的大小n，負載因子n/m實際為平均表長，也就是不成功搜索和插入操作的期望代價。而成功搜索的期望代價，大致為負載因子的一半。除了每個數(shù)據(jù)項必須增加一個指針域之外，Hash表本身可能包含較多的冗余信息，m值取得越小，負載因子越大，直接影響搜索的性能。3.單區(qū)鏈接法它是對開地址法的改進。全部數(shù)據(jù)項置于Hash表中，但搜索中的查找序列不是通過計算而是通過指針鏈接。例如把關(guān)鍵字序列17、52、9、41、15、20、11按Hash函數(shù)h(x)=xmod7依單區(qū)鏈接法插入。Fig.4.19是插入的結(jié)果。

第56頁/共91頁58這種方法用指針操作代替二次Hashing函數(shù)的計算，性能有所提高。但與開地址法一樣，單區(qū)法因地址的互相占用，使映射到不同地址的沖突鏈合并到一起，往往使沖突鏈長大大增加，使搜索效率降低。4.調(diào)諧式（Tuning）鏈接法其基本思想是把Hash表分為兩個區(qū)：T:[0..m’-1]為整個存儲區(qū)，T[0..m-1]為Hash區(qū)，T[m..m’-1]為鏈接區(qū)。，，為調(diào)諧因子。關(guān)鍵字經(jīng)Hash函數(shù)h(x)映射到Hash區(qū)T[0..m-1]，如若發(fā)生沖突，首先把沖突項存于鏈接區(qū)T[m..m‘-1]，避免了沖突鏈的交叉、加長，僅在鏈接區(qū)裝滿時再鏈接到Hash區(qū)。這種方法把大部分沖突鏈置于鏈接區(qū)，吸取了鏈接法的優(yōu)點，同時又有一定的限度，避免了鏈接區(qū)的空間分配難以控制的缺點。Fig.4.20是一個簡單實例的示意圖。第57頁/共91頁59第58頁/共91頁60調(diào)諧式Hash方法的性能與調(diào)諧因子和負載因子有關(guān)，在值確定時，可以求出一個最優(yōu)的值。相關(guān)的研究指出，當(dāng)取時，較好，這時的期望搜索代價為1.79次查找，而在一般情況下，取較好。4.6.4Hash算法的優(yōu)劣分析Hash方法獨特的按內(nèi)容尋址的檢索方式是一種高級的“聯(lián)想”式存儲與檢索技術(shù)。它的期望時間代價為O(1)階，與數(shù)據(jù)集規(guī)模無關(guān)。不足之處：1.按內(nèi)容尋址的方式?jīng)Q定了它是把數(shù)據(jù)“散列”（scattering）到Hash表中，因此它不適用于涉及數(shù)據(jù)內(nèi)容之間關(guān)系的查詢。例如，求最大、最小元，刪除最小元，后繼，前導(dǎo)，求關(guān)鍵字key值在某一范圍內(nèi)的一組數(shù)據(jù)等等。第59頁/共91頁612.

Hash算法的最壞情形時間代價為O(n)階，使其不能在諸如防空系統(tǒng)、空中交通調(diào)度系統(tǒng)等“緊急”系統(tǒng)中采用，因為一旦出現(xiàn)一次最壞情形，會造成重大事故。3.前文對Hash算法的性能分析過程中，所有的分析結(jié)果都是在“實際關(guān)鍵字集合S是全域U的一個隨機子集”等條件下得到的。如果全集U中的關(guān)鍵字不是等可能性地出現(xiàn)在Hash表中，這種情況在實際問題中是經(jīng)常遇到的，例如關(guān)鍵字為程序中的標(biāo)識符名，有些名稱如m、n、m1、m2、m3等等，出現(xiàn)的概率遠遠多于其它名稱，在這種情形下，期望性能可能變差。對此，也有一些方法予以解決，如泛Hash（UniversalHashing）方法。4.命題4.3、4.4指出Hash算法的性能與負載因子的值密切相關(guān)。在數(shù)據(jù)集不斷增加時，負載因子逐漸增大，并接近于1，會使系統(tǒng)性能明顯下降。第60頁/共91頁62例如或>0.95時，擴大Hash區(qū)，即所謂空間倍增（arraydoubling）技術(shù)，需要把數(shù)據(jù)集中的所有數(shù)據(jù)按照新的Hash函數(shù)重新轉(zhuǎn)存入新的Hash區(qū)，這一工作代價很大。為解決空間倍增所需的高代價問題，可采用線性擴張Hash算法?；舅枷胧侵付ㄒ粚ω撦d因子的上限和下限，在可能關(guān)鍵字集合S的大小n改變的過程中，一旦超過，存儲區(qū)擴充一個桶（可存放b條數(shù)據(jù)項），當(dāng)小于時，存儲區(qū)縮減一個桶。這樣就保證動態(tài)數(shù)據(jù)集上的操作總是在良好的性能下工作。*4.6.5Hash技術(shù)的幾種新發(fā)展

1.完備Hash函數(shù)（PerfectHashFunction）第61頁/共91頁63完備哈希函數(shù)（PHF）又稱無沖突哈希函數(shù)。即PHF的地址映射不產(chǎn)生沖突，一次計算即可找到目標(biāo)數(shù)據(jù)項。因此，用PHF實現(xiàn)的檢索算法的最好平均和最壞情形時間復(fù)雜度都為O(1)階。其定義可敘述為：對任一時間關(guān)鍵字集合，函數(shù)h：稱為S的完備哈希函數(shù)（PHF），如果對任意，必有。當(dāng)m=n時，h稱為集合S的最小完備哈希函數(shù)（MPHF）。給定n（n不太大）個關(guān)鍵字集合和Hash表長m，有幾種PHF的構(gòu)造技術(shù)：1）針對字符串關(guān)鍵字集合的啟發(fā)式算法假定集合中的關(guān)鍵字為字符串，設(shè)關(guān)鍵字k∈U為一個Σ={a,b,c,…,x,y,z}上的字符串，length(k)為字符串的長，F(xiàn)(k)，L(k)分別為k的首末字符。第62頁/共91頁64求形如h(k)=length(k)+Value(F(k))+Value(L(k))的Hash函數(shù)。為了使h(k)為完備Hash函數(shù)，須對于函數(shù)Value：Σ→Z的值進行適當(dāng)?shù)亩x，即要為Value(a)，Value(b)，…，Value(z)賦予適當(dāng)?shù)闹?，使得對于S中的所有關(guān)鍵字，h(k)∈[0…m-1]有不同的值。Sager提出的一種改進方法，是求形如：h(k)=(h0(k)+g(h1(k)+g(h2(k)))modn的最小完備Hash函數(shù)。這種方法首先選定適當(dāng)?shù)暮瘮?shù)h0(k)，h1(k)，h2(k)，然后根據(jù)h0，h1，h2來確定函數(shù)g。2）Hash索引表法（HIT法）

對于關(guān)鍵字集合S和Hash表地址集[0…m-1]，取t個Hash函數(shù)hj：S→[0…m-1](j=1…t)。按一定的算法計算出一個一維數(shù)組：array[0…m-1]of[1…t]，稱為HIT表。第63頁/共91頁65在h1，h2，…h(huán)t和HIT確定的條件下，定義完備Hash函數(shù)：h：S→[0…m-1]，使得對于關(guān)鍵字k∈S，h(k)=hj(k)，其中j∈{1,2,…,t}，滿足條件：HIT[hj(k)]=j。在已知t個Hash函數(shù)h1，h2，…h(huán)t和HIT表的條件下，用這個PHF把關(guān)鍵字k∈S插入到Hash表T[0…m-1]的算法為：voidwriteHIT(keyK){ intj=1; while((HIT[hj(k)]!=j)&&(j<=t)) j++; if(j<=t) T[hj(k)]=k; else cout<<"failure!";}第64頁/共91頁66如果h1，h2，…h(huán)t和HIT表選擇正確，“failure”的情況不會出現(xiàn)。相應(yīng)的檢索算法為：inth(keyk){ intj=1; while((HIT[hj(k)]!=j)&&(j<=t)) j++; if(j<=t) returnhj(k); else return(-1);}與第一種方法類似，PHF的構(gòu)造過程是：首先選擇t個Hash函數(shù)h1h2…h(huán)t，然后，確定HIT表HIT[0…m-1]∈{1,2,…,t}的m個值，使得所定義的函數(shù)h為PHF，即對任何x,y∈S，x≠y有h(x)≠h(y)。第65頁/共91頁67這個確定HIT表的過程類似于迷宮問題，八后問題，等組合問題，可以用回溯等搜索算法完成。如果滿足條件的HIT表不存在，可以在調(diào)整t值和t個Hash函數(shù)后重新構(gòu)造滿足條件的HIT表。3）Fredman構(gòu)造法Fredman通過構(gòu)造法證明了，對任意的關(guān)鍵字集合至多取m=3n（即），一定可以在形如的Hash函數(shù)中找到S的完備哈希函數(shù)。構(gòu)造方法：已知：實際關(guān)鍵字集合，且|U|=N為素數(shù)。①對此S，先構(gòu)造函數(shù)h'(x)=((kx)modN)modn。第66頁/共91頁68用枚舉法選擇k值，使得其中bi=|Si|，(i=0,1,…,n-1)，Si={x|x∈S,h'(x)=i}。Si是被h'映射為i的關(guān)鍵字集合。已經(jīng)證明，滿足條件的k值一定存在。②對此每個Si，(i=0,1,…,n-1)選擇適當(dāng)?shù)膋i，構(gòu)造函數(shù)hi(x)=((kix)modn)modCi。其中Ci=1+bi(bi-1)，使得為單一映射函數(shù)（無沖突）。由于這時的集合Si較小，Ci值也不大，因此ki一定存在。③取，定義函數(shù)使對于任意x∈Sh(x)=C0+C1+…+Ci-1+((kix)modN)modCi。其中i=h'(x)=((kx)modN)modn。第67頁/共91頁69不難證明，函數(shù)h(x)是S∈U的一個完備哈希函數(shù)。上述構(gòu)造過程實際上要計算2n+1個值：k，k0，k1，…，kn-1和C0，C1，…，Cn-1。時間代價估計為O(n·N)，空間代價為5n+C。4）利用中國余數(shù)定理構(gòu)造MPHF中國余數(shù)定理指出：對于任意的n個整數(shù)R1，R2，…，Rn，和n個互素整數(shù)M1，M2，…，Mn，總可以找到一個常數(shù)C，使得Ri=CmodMi

對i=1…n成立。為了對關(guān)鍵字集合S={k1,k2,…,kn}構(gòu)造MPHF，只須把地址空間[0…m-1]=[0…n-1](m=n)的每一地址0，1，2，…，n-1視為中國余數(shù)定理中的R1，R2，…，Rn。k1k2…kn與n個素數(shù)建立1－1對應(yīng)關(guān)系：P(ki)=Mii=1,2,…,n。第68頁/共91頁70于是構(gòu)造MPHF的任務(wù)歸結(jié)為找到中國余數(shù)定理中的常數(shù)C。即令h(ki)=CmodP(ki)i=1,2,…,n。這種方法的難點是當(dāng)n較大時，C值的計算代價很高，下面是一種實用的構(gòu)造方法，設(shè)關(guān)鍵字ki為字符串型。①對關(guān)鍵字集合S={k1,k2,…,kn}中的每一個ki選其中兩個（或三個…）字符ki1，ki2，使不同關(guān)鍵字ki，kj對應(yīng)的字符對{ki1,ki2}和{kj1,kj2}也不同。②按每個關(guān)鍵字ki的第一個字符ki1把集合S分為r組，使每組關(guān)鍵字對應(yīng)的字符對的第一個字符相同，不同組相異。這r個關(guān)鍵字組按字典順序記為G1,G2,…,Gr。若關(guān)鍵字ki∈Gj，則令為前j-1組的關(guān)鍵字總和。第69頁/共91頁71③把n個關(guān)鍵字對應(yīng)的n個字符對中的第二個字符k12，k22，…，kn2（它們中可能有相同的字符）按不同字符在其中出現(xiàn)的頻率由大到小分別對應(yīng)于最小的若干素數(shù)：2，3，5，7，…。例如，字符‘e’在其中出現(xiàn)頻率排在第三位，則令P(‘e’)=5。④對于關(guān)鍵字組Gj(j=1,2,…,r)，設(shè)其對應(yīng)的字符對中第一字符位u（相同），第二字符位v1，v2，…，vt，則依中國余數(shù)定理一定可找到一個常數(shù)Cj使1≡CjmodP(v1),2≡CjmodP(v2), …t≡CjmodP(vt)。其中t=|Gj|（在Gj中對應(yīng)的字符對中第二字符都是不同的）。第70頁/共91頁72⑤令函數(shù)C(u)=Cj，h(ki)=d(ki1)+C((ki1)modP(ki2))即為所求之最小完備Hash函數(shù)。2.泛哈希（UniversalHashing）技術(shù)集合稱為Hash函數(shù)的泛類。如果H滿足條件：對任意的x,y∈U，x≠y，有這時，把H稱為一個C級泛類。換言之，一個C級泛類H，對全域U中任二個不等元x，y，H中使它們發(fā)生沖突（即h(x)=h(y)）對Hash函數(shù)對個數(shù)不大于總數(shù)|H|的C/m。C值越小，泛類的性能越好。Carter給出了兩個泛類（記為H1和H2）：(1)第71頁/共91頁73Carter支持H1是級的。已經(jīng)證明，任何泛類的級C的下界是1-m/N。一般m遠小于N，因此接近于1。而泛類H1的級C=1，因此它幾乎是最優(yōu)的。(2)其中，hr(x)=xmodPr，gc,d(z)=((cz+d)modP2t)modm，Pr：為從小到大排列的第r個素數(shù)。對于泛哈什算法進行的復(fù)雜分析指出：采用C級泛類H時，其期望檢索代價應(yīng)為1+Cα（α=n/m為負載因子）；n次操作（包括查找，插入，刪除）序列的期望代價為(1+Cα/2)n。它們與用戶所取的關(guān)鍵字集合S的隨機性無關(guān)。3.可擴展哈希方法（ExtendibleHashing）

可擴展哈希技術(shù)主要針對動態(tài)HashFile。第72頁/共91頁74可擴展哈希算法采用一種可隨HashFile中記錄總數(shù)（實際關(guān)鍵字集合S的大?。┑淖兓饾u變化的動態(tài)HashFile，其基本方法是：設(shè)HashFile的原始區(qū)T由m個數(shù)據(jù)塊（block或bucket）組成，T[0…m-1]。每個數(shù)據(jù)塊（桶）T[i]可包含b個記錄。存儲區(qū)T可由一端擴展或收縮。存儲區(qū)的線性擴展由哈希文件的負載因子α值來控制，當(dāng)新的記錄插入，使得α值超過預(yù)先確定的某一上界αmax時，存儲區(qū)擴展一個數(shù)據(jù)塊（桶）。這一擴展，又使動態(tài)變化的α值降了下來。若干次插入后，使α值再次超過αmax，存儲區(qū)再擴展一個數(shù)據(jù)塊。原始區(qū)擴展m次后，容量擴大了一倍，形成了新的原始區(qū)，完成了一次Hash文件的倍增。如果繼續(xù)插入，又開始了新的擴展和倍增。動態(tài)Hash文件也有刪除操作，為負載因子α設(shè)一下界αmin，縮進與擴展操作相類似。第73頁/共91頁75與泛Hashing技術(shù)相類似，可擴展Hashing算法也采用一族Hash函數(shù)，以適應(yīng)HashFile動態(tài)變化的特點。下面是一種簡單的常用形式：①Hash函數(shù)族H由Hash函數(shù)序列h0，h1，…組成；②設(shè)U={0,1}q，T[0…m-1]中包含m=2p個數(shù)據(jù)項（p<q），則可令h0:{0,1}q→{0,1}p為一普通函數(shù)；③令hi:{0,1}q→{0,1}p+i(i=1,2,…)，且對任意關(guān)鍵字k∈U，hi(k)等可能的取值為hi-1(k)或hi-1(k)+2p+i-1。一個典型的實用選擇是用平方取中法構(gòu)造h0，h1，h2，…，即對任意的關(guān)鍵字k∈{0,1}q，取hi(k)=k2的二進制位行的中間p+i位構(gòu)成的二進制數(shù)（i=0,1,2…），顯然hi(k)∈{0,1}p+i。可擴展Hash算法的原始取T[0…m-1]由m個數(shù)據(jù)塊組成，每個數(shù)據(jù)塊可存儲b條記錄。當(dāng)完成一次Hash區(qū)的倍增時，空間擴大一倍，m*=2；。第74頁/共91頁76在算法運行過程中，在原始區(qū)之外，Hash區(qū)已經(jīng)擴展了l個數(shù)據(jù)塊（0≤l≤m）。這時，有相繼的兩個Hash函數(shù)hi，hi+1在工作。當(dāng)一個新的關(guān)鍵字k要進行檢索或插入時，系統(tǒng)根據(jù)擴展塊指針l和當(dāng)前Hash函數(shù)的序號i。計算h(k)的值，即關(guān)鍵字k的映射地址：inth(keyy){ if(hi(k)<l) returnhi+1(k); else returnhi(k);}第75頁/共91頁77從上面的程序可以看出，在運行的某一時刻，當(dāng)前Hash函數(shù)序列號為i，擴展塊指針為l（已擴展了l個block），Hash地址計算由函數(shù)hi，hi+1分別完成，前者負責(zé)T[l…m-1]區(qū)域的計算，而hi+1負責(zé)[0…m-1]和[m…m+l-1]兩段區(qū)域的地址計算。Hash區(qū)域的線性擴展，由負載因子α=n/((m+l)*b)計算，其中n為已插入到Hash文件中的記錄數(shù)。每插入一條新的記錄，n加1，α有所增加，一旦使得α>αmax，Hash區(qū)向右擴展一個數(shù)據(jù)塊，即令指針l加1（這時還應(yīng)把原來由hi映射到數(shù)據(jù)塊T[l]的記錄重新由hi+1映射到T[l]和T[m+l-1]兩個block中）。系統(tǒng)繼續(xù)運行，直到l增加到m，這時完成一次擴展，如果Hash文件繼續(xù)擴展，應(yīng)由hi+1，hi+2負責(zé)計算，即令序號i加1，同時原始區(qū)倍增m=2*m，l=0。對于刪除操作，可以類似地設(shè)置αmin，在n減少導(dǎo)致α<αmin時，縮小一個數(shù)據(jù)塊，與擴展類似。第76頁/共91頁78第77頁/共91頁79中序遍歷（Inorder_Tree_Walk）算法

voidInorder_Tree_Walk(TreeNode*x){if(x!=NULL){Inorder_Tree_Walk(x->left);cout<<x->key;Inorder_Tree_Walk(x->right);}}返回第78頁/共91頁80Tree_Search算法

TreeNode*Tree_Search(TreeNode*x,intk){if((x==NULL)||(k==x->key))returnx;if(k<x->key)returnTree_Search(x->left,k);elsereturnTree_Search(x->right,k);}

//該算法的非遞歸形式為：TreeNode*Tree_Search(TreeNode*x,intk){while((x!=NULL)&&(k!=x->key)){if(k<x->key)x=x->left;elsex=x->right;}returnx;}返回第79頁/共91頁81求最小元的算法Tree_Minimum(root)

TreeNode*Tree_Minimum(TreeNode*x){while(x->left!=NULL)x=x->left;returnx;}返回第80頁/共91頁82求最大元的算法Tree_Maximum(root)

TreeNode*Tree_Maximum(TreeNode*x){while(x->right!=NULL)x=x->right;returnx;}返回第81頁/共91頁83求后繼項的操作算法Successor(x)TreeNode*Tree_Successor(TreeNode*x){TreeNode*y;if(x->right!=NULL)returnTree_Minimum(x->right);y=x->p;while((y!=NULL)&&(x==y->right)){x=y;y=y->p;}returny;}返回第82頁/共91頁84插入操作算法Tree_Insert

voidTree_Insert(TreeNode*root,TreeNode*z){TreeNode*x,*y;y=NULL;x=root;while(x!=NULL){y=x;if(z->key<x->key)x=x->left;elsex=x->right;}z->p=y;if(y==NULL)root=z;elseif(z->key<y->key)y->