課件計(jì)算機(jī)算法設(shè)計(jì)與分析

計(jì)算機(jī)算法設(shè)計(jì)與分析計(jì)算機(jī)算法設(shè)計(jì)與分析Chapter4. 數(shù)據(jù)集合上的搜索(Searching)算法

4.1動(dòng)態(tài)數(shù)據(jù)集(DynamicSet)與抽象數(shù)據(jù)類型(ADT)4.2二叉搜索樹(BinarySearchTrees)4.3隨機(jī)二叉搜索樹(RandomlyBuiltBinarySearchTree)4.4紅黑樹(Red-BlackTree)4.5 2-3-4樹

4.6 Hashing技術(shù)Chapter4. 數(shù)據(jù)集合上的搜索(Searchin4.1動(dòng)態(tài)數(shù)據(jù)集(DynamicSet)與抽象數(shù)據(jù)類型(ADT)靜態(tài)數(shù)據(jù)集（StaticSet）中的數(shù)據(jù)是固定不變的。動(dòng)態(tài)數(shù)據(jù)集（DynamicSet）則是由不斷變動(dòng)的同類型數(shù)據(jù)元素組成的數(shù)據(jù)集合。動(dòng)態(tài)數(shù)據(jù)集（DynamicSet）可以表示為一個(gè)數(shù)據(jù)元素的數(shù)組：

classDynamicSet{intsetSize;Objectelements[setSize];...}//Object為數(shù)據(jù)元素的類型，setSize為當(dāng)前集合中的元素個(gè)數(shù)4.1動(dòng)態(tài)數(shù)據(jù)集(DynamicSet)與抽象數(shù)據(jù)類型用數(shù)組表示集合操作方便，但當(dāng)集合中的元素個(gè)數(shù)不斷增加時(shí)，數(shù)組的長(zhǎng)度必須擴(kuò)大。一般采用空間倍增（arraydoubling）技術(shù)，即另外申請(qǐng)一個(gè)加倍長(zhǎng)度的新數(shù)組，把集合中的數(shù)據(jù)傳送過來，取代原有的空間。其過程為：

arrayDouble(set){newSize=2*arraySize;newElements=newObject(newSize);Transferallelementsfromtheset.elementstothenewElement;set.elements=newElements;set.setSize=newSize;}更為靈活的存儲(chǔ)形式是利用指針和鏈表（例如線性鏈表和樹結(jié)構(gòu)），這種存儲(chǔ)形式在搜索算法中經(jīng)常用到。

用數(shù)組表示集合操作方便，但當(dāng)集合中的元素個(gè)數(shù)不斷增加時(shí)，數(shù)組搜索問題：在集合中檢索出其關(guān)鍵字域的值等于給定值的數(shù)據(jù)元素。已知：動(dòng)態(tài)數(shù)據(jù)集類型DynamicSet的一個(gè)實(shí)例set和值x。求：集合set中一個(gè)元素Objectelement，使element.key=x。數(shù)據(jù)集合上的操作（operation）可以分為兩類：.查詢（queries）操作：對(duì)數(shù)據(jù)集不做任何變動(dòng)，僅僅返回有關(guān)集合的某些信息；.修改（modifyingoperations）操作：要對(duì)數(shù)據(jù)集合的某些域進(jìn)行改動(dòng)。一些典型的操作：

.Search(S,k)：搜索，一個(gè)查詢操作。對(duì)于給定的數(shù)據(jù)集合S和一個(gè)關(guān)鍵字值k，返回S中一個(gè)元素（element）的指針x，使得x->key=k。當(dāng)S中沒有符合條件的元素時(shí)，返回的指針為空（NULL）。搜索問題：在集合中檢索出其關(guān)鍵字域的值等于給定值的數(shù)據(jù)元素。

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

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

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

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

.Deletemin(S)：刪除最小元，一個(gè)修改操作。它相當(dāng)于Minimum(S)和Delete(S,x)的聯(lián)合，即：Delete(S,Minimum(S))。.Insert(S,x)：插入，一個(gè)修改操作。把由x指向

.Successor(S,x)：求后繼數(shù)據(jù)元，一個(gè)查詢操作。若S中的數(shù)據(jù)元素按關(guān)鍵字值從小到大排列，x是指向S中某一數(shù)據(jù)元素的指針，則返回x所指向的數(shù)據(jù)元素的下一個(gè)數(shù)據(jù)元素的指針。若x指向最后一個(gè)數(shù)據(jù)元素，則返回NULL。

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

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

·動(dòng)態(tài)字典：（動(dòng)態(tài)數(shù)據(jù)集S，Search，Insert，Delete）。優(yōu)先隊(duì)列（PriorityQueue）：（動(dòng)態(tài)數(shù)據(jù)集S，Insert，Deletemin）。.Successor(S,x)：求后繼數(shù)據(jù)元，一個(gè)查詢操4.2二叉搜索樹二叉搜索樹又稱為二元字典樹，是一種最常用的動(dòng)態(tài)數(shù)據(jù)集的數(shù)據(jù)結(jié)構(gòu)，可以用于實(shí)現(xiàn)字典和優(yōu)先隊(duì)列等ADT。4.2.1二叉搜索樹（BinarySearchTrees）

BST的一個(gè)結(jié)點(diǎn)與一個(gè)數(shù)據(jù)項(xiàng)相對(duì)應(yīng)，除了數(shù)據(jù)項(xiàng)Object或數(shù)據(jù)項(xiàng)的指針之外，結(jié)點(diǎn)主要由關(guān)鍵字key域和指針域組成，即關(guān)鍵字key與指針left、right和p，三個(gè)指針分別指向該結(jié)點(diǎn)的左兒子、右兒子和父結(jié)點(diǎn)。

BST中結(jié)點(diǎn)的關(guān)鍵字值應(yīng)滿足BST性質(zhì)：即，設(shè)x是二叉搜索樹的一個(gè)結(jié)點(diǎn)，結(jié)點(diǎn)y位于結(jié)點(diǎn)x的子樹中，x、y的關(guān)鍵字值應(yīng)滿足以下關(guān)系：PKEYLeftRight4.2二叉搜索樹二叉搜索樹又稱為二元字典樹，是一種最常用如果y是x的左子樹中的一個(gè)結(jié)點(diǎn)，則y->key≤x->key；如果y是x的右子樹中的一個(gè)結(jié)點(diǎn)，則y->key>x->key。Fig.4.1給出了由6個(gè)結(jié)點(diǎn)（數(shù)據(jù)項(xiàng)）組成的兩個(gè)二叉搜索樹。兩個(gè)BST(a)和(b)有不同的樹高，前者比后者的查詢效率更高。如果y是x的左子樹中的一個(gè)結(jié)點(diǎn)，則y->key≤x->key遍歷二叉搜索樹的所有結(jié)點(diǎn)可以采用中序遍歷（inordertreewalk）算法，即可將與二叉搜索樹結(jié)點(diǎn)相對(duì)應(yīng)的數(shù)據(jù)項(xiàng)按關(guān)鍵字從小到大排列出來。中序遍歷（Inorder_Tree_Walk）算法4.2.2查詢（Querying）的實(shí)現(xiàn)對(duì)二叉搜索樹的查詢主要是Search、Minimum、Maximum、Successor、Predecessor等操作，這些操作都可在O(h)時(shí)間內(nèi)完成，其中h是二叉樹的高。如Fig.4.2所示，BST查詢操作為Tree_Search(root,k)，即搜索BST上關(guān)鍵字值為k的結(jié)點(diǎn)。

Tree_Search算法遍歷二叉搜索樹的所有結(jié)點(diǎn)可以采用中序遍歷（inordert求最小元（或最大元）的操作只需從根開始沿著左指針（或右指針）一直搜索至某一結(jié)點(diǎn)x，其left或right指針為NULL，這時(shí)結(jié)點(diǎn)x的關(guān)鍵字x->key為最小（或最大）。求最小元的算法Tree_Minimum(root)求最大元的算法Tree_Maximum(root)求數(shù)據(jù)項(xiàng)的后繼與前導(dǎo)項(xiàng)的操作要相對(duì)復(fù)雜，如Fig.4.2，結(jié)點(diǎn)15（指關(guān)鍵字為15的結(jié)點(diǎn))的后繼是結(jié)點(diǎn)17，它是結(jié)點(diǎn)15的右子樹中的最小元。然而對(duì)于沒有右子樹的結(jié)點(diǎn)，例如13、4和17，其后繼分別為15、6和18，顯然計(jì)算這三個(gè)結(jié)點(diǎn)的后繼時(shí)需要使用父結(jié)點(diǎn)指針x->p。求后繼項(xiàng)的操作算法Successor(x)15的前導(dǎo)是左子樹中的最大元17的前導(dǎo)是其第一個(gè)左祖先求最小元（或最大元）的操作只需從根開始沿著左指針（或右指針）Successor(x)操作根據(jù)條件x->right!=NULL決定兩種情形：第一種情況從結(jié)點(diǎn)x下行，直到葉結(jié)點(diǎn)，其路長(zhǎng)顯然不超過樹高h(yuǎn)；第二種情況從結(jié)點(diǎn)x上行，路長(zhǎng)同樣不超過h。因此有下面的結(jié)論：定理4.1

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

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

由n個(gè)不同的關(guān)鍵字組成的隨機(jī)二叉搜索樹的平均樹高為h=O(logn)。該定理的證明基本思路與步驟：1.有關(guān)概率分布的假設(shè)：假定關(guān)鍵字輸入序列k1,k2,...,kn為n個(gè)不同值的一種排列，設(shè)各種不同排序?yàn)榈瓤赡艿?，因此這一特定排序出現(xiàn)的可能性為1/n!。4.3隨機(jī)二叉搜索樹隨機(jī)二叉搜索樹（RandomlyB假定：對(duì)任一j值（1≤j≤n），kj取n個(gè)關(guān)鍵字其中任意一個(gè)的概率為1/n，也是等可能的。2.在RBST中結(jié)點(diǎn)x為結(jié)點(diǎn)y的祖先的充要條件：首先分析從根到樹上任一結(jié)點(diǎn)y（y->key=kj,1<j≤n）的路徑上的結(jié)點(diǎn)特征。分析的結(jié)果是，在這條路上的每個(gè)結(jié)點(diǎn)x（x->key=ki）都具有下列特征：

·其對(duì)應(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插入到一個(gè)原始為空的二叉搜索樹而得到的結(jié)果，則結(jié)點(diǎn)x（x->key=ki）在T中是結(jié)點(diǎn)y(y->key=kj)的祖先的充要條件是：假定：對(duì)任一j值（1≤j≤n），kj取n個(gè)關(guān)鍵字其中任意一個(gè)在Fig.4.5中，kj=17。從圖(a)中可以看到，從根到結(jié)點(diǎn)17的路徑上的4個(gè)結(jié)點(diǎn)的關(guān)鍵字都符合上述條件，而且，從(b)表中的關(guān)鍵字序列中可以看出，關(guān)鍵字17前面的10個(gè)關(guān)鍵字中滿足命題4.1條件的關(guān)鍵字21、19、9、12全是結(jié)點(diǎn)17的祖先。在Fig.4.5中，kj=17。從圖(a)中可以看到，從根到命題4.1證明證明：分為兩種情況，1）證明Ki是從1（根）至i中值大于kj的結(jié)點(diǎn)中值最小者（命題前部）設(shè)k’為從1（根）至ki中路徑上的點(diǎn)，且k’>kj，則為證明上述命題，只需證明k’>ki。為證明這一點(diǎn)，采用反證法，設(shè)k’<ki。由于k’,ki,kj在一個(gè)路徑上，則由于k’<ki，則ki，kj一定在k’的右子樹中，因此一定有k’<kj成立，這與k’>kj矛盾。2)同理可證命題右部.命題4.1證明證明：分為兩種情況，3.求RBST中任一結(jié)點(diǎn)的深度d(kj,T)：從命題4.1立即可以計(jì)算出T中任一（與關(guān)鍵字kj對(duì)應(yīng)的）結(jié)點(diǎn)的深度d(kj,T)恰恰等于滿足命題4.1條件的（祖先）結(jié)點(diǎn)的個(gè)數(shù)，即：命題4.2

在上述的隨機(jī)二叉搜索樹T中，對(duì)于給定的關(guān)鍵字kj(1≤j≤n)，令即kl是所有的先于ki輸入并大于kj的值；令即kl是所有的先于ki輸入并小于kj的值。則從根到y(tǒng)（y->key=kj）的路徑上，結(jié)點(diǎn)的關(guān)鍵字集合恰為Gj∪Lj，且d(kj,T)=|Gj|+|Lj|。3.求RBST中任一結(jié)點(diǎn)的深度d(kj,T)：從Fig4.5的實(shí)例中可以看到，對(duì)于kj=17，Gj={21，9}，Lj={9。12}，所以kj的深度為4。從Fig4.5的實(shí)例中可以看到，對(duì)于kj=17，Gj={2定理:對(duì)于n≥1,插入n個(gè)隨機(jī)元素到初始為空的二叉搜索樹,需要的期望比較次數(shù)為:證明:

由序列a1,a2,…,an創(chuàng)建一棵二叉查找樹時(shí),令T(n)為序列元素之間需要的比較次數(shù)。T(0)=0，令b1,b2,…,bn為已按升序排好的序列。如果a1,a2,…,an是隨機(jī)的，則對(duì)于某元素ai,任意j(1≤j≤n),ai等可能地為bj，(ai)bj為最終樹的根，則b1,b2,…,bj-1位于bj的左子樹(j-1個(gè)元素)，bj+1,…,bn位于右子樹((n-j)個(gè)元素。)aib1,…,bj-1bj+1,…,bn定理:對(duì)于n≥1,插入n個(gè)隨機(jī)元素到初始為空的二叉搜索樹,需b1,…,bj-1插入到最終樹中，每個(gè)都一定與根比較一次，然后就是插入到左子樹中(與ai插入到整棵樹中過程相同，即遞歸實(shí)現(xiàn))，對(duì)于j-1個(gè)結(jié)點(diǎn)，共需要j-1+T(j-1)次比較；同理bj+1,…,bn插入到右子樹中的比較次數(shù)為：n-j+T(n-j)，即將ai插入最終n個(gè)結(jié)點(diǎn)的搜索樹中且ai為bj(根)的比較次數(shù)為上述兩部分之和，即n-1+T(j-1)+T(n-j)。由于j等可能地取1,2,…,n中的任意值，所以：也即：由此可得：T(n)≤cnlogn該定理:建一棵n個(gè)結(jié)點(diǎn)的二叉搜索樹的期望比較次數(shù)為O(nlogn)b1,…,bj-1插入到最終樹中，每個(gè)都一定與根比較一次，然由于插入n個(gè)結(jié)點(diǎn)的總時(shí)間代價(jià)為:O(nlogn),因此對(duì)于樹中的某一個(gè)結(jié)點(diǎn)而言,找到該結(jié)點(diǎn)的總比較次數(shù)為T(n)/n,即為O(logn)平衡二叉樹的樹高為)(logn)由于插入n個(gè)結(jié)點(diǎn)的總時(shí)間代價(jià)為:O(nlogn),因此對(duì)于4.4紅黑樹（Red-BlackTree）4.4.1Red-Black樹的性質(zhì)

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

具有n個(gè)內(nèi)部結(jié)點(diǎn)的RB樹的樹高h(yuǎn)≤2log(n+1)。證明：1.首先用歸納法證明以RB樹上任一結(jié)點(diǎn)x為根的子樹至少包含個(gè)內(nèi)部結(jié)點(diǎn)。RB樹滿足下面的性質(zhì)：1°遞歸基礎(chǔ)：對(duì)于高度為0的結(jié)點(diǎn)x，即x為葉結(jié)點(diǎn)（NULL），以其為根的子樹有0個(gè)內(nèi)部結(jié)點(diǎn)，即至少有個(gè)內(nèi)部結(jié)點(diǎn)。命題成立。2°設(shè)對(duì)于高度為h-1的結(jié)點(diǎn)命題成立。3°考察高為h(>0)的結(jié)點(diǎn)x，由于h>0，x是RB樹的內(nèi)部結(jié)點(diǎn)，必有兩個(gè)子結(jié)點(diǎn)x1、x2，其高為h-1，且有根據(jù)歸納假設(shè)，以x1、x2為根的兩子樹分別至少有個(gè)內(nèi)部結(jié)點(diǎn)，∴以x為根的子樹至少有(兩個(gè)子樹結(jié)點(diǎn)數(shù)之和再加1,即)

個(gè)內(nèi)部結(jié)點(diǎn)。1°遞歸基礎(chǔ)：對(duì)于高度為0的結(jié)點(diǎn)x，即x為葉結(jié)點(diǎn)（NULL）2.證明對(duì)于RB樹的根r，設(shè)其高為h，bh(r)≥h/2。這一點(diǎn)由性質(zhì)3，即從根到葉的任一條路上，red結(jié)點(diǎn)數(shù)不超過一半即可證明。3.由上面兩個(gè)命題可知：高為h的RB樹，其內(nèi)部結(jié)點(diǎn)數(shù)n至少為，即。故有，定理得證。

定理4.4說明，動(dòng)態(tài)數(shù)據(jù)集上的基本操作在RB樹上的執(zhí)行代價(jià)為O(h)=O(logn)階。換句話說，用RB樹的形式實(shí)現(xiàn)動(dòng)態(tài)數(shù)據(jù)集，在任何時(shí)刻，樹高h(yuǎn)總能保持在O(logn)階。查找、求最大、最小、求前導(dǎo)、后繼、插入、刪除2.證明對(duì)于RB樹的根r，設(shè)其高為h，bh(r)≥h/2。4.4.2Red-Black樹的插入與刪除算法

在插入或刪除結(jié)點(diǎn)時(shí)，為了使樹重新具有Red-Black性質(zhì)，除了要改變結(jié)點(diǎn)間的指針鏈接關(guān)系外，還要對(duì)某些結(jié)點(diǎn)的著色進(jìn)行調(diào)整。對(duì)于結(jié)點(diǎn)間指針鏈接關(guān)系的修改歸結(jié)為旋轉(zhuǎn)（Rotation）操作，旋轉(zhuǎn)是調(diào)整樹的平衡狀態(tài)的基本手段。Rotation操作對(duì)二叉搜索樹上的某一局部進(jìn)行調(diào)整，通過交換一對(duì)父子結(jié)點(diǎn)的父子關(guān)系，在保持樹結(jié)點(diǎn)間的有序關(guān)系的條件下（即保持其中序遍歷的結(jié)果為單調(diào)序列），改變?cè)撟訕涞钠胶鉅顟B(tài)。4.4.2Red-Black樹的插入與刪除算法Rotation操作分為左旋（Left-Rotation）和右旋(Right-Rotation)，如Fig.4.7所示。Rotation操作分為左旋（Left-Rotation）和左旋算法Left_Rotation(root,x)Fig.4.8給出一次左旋轉(zhuǎn)的實(shí)例的圖示。Right_Rotation(root,x)的算法與Left_Rotation(root,x)類似。左旋算法Left_Rotation(root,x)這個(gè)算法主要完成兩件事：1°把結(jié)點(diǎn)x與其右子結(jié)點(diǎn)y的父子關(guān)系進(jìn)行調(diào)整，即把x->p—x—y的父子關(guān)系改變?yōu)閤->p—y—x的順序；2°把y的左子樹變?yōu)閤的右子樹。(右旋轉(zhuǎn))1.把結(jié)點(diǎn)x與其左子結(jié)點(diǎn)y的父子關(guān)系進(jìn)行調(diào)整即把x->p—x—y的父子關(guān)系改變?yōu)閤->p—y—x的順序2.把y的右子樹變?yōu)閤的左子樹算法不存在與結(jié)點(diǎn)數(shù)n相關(guān)的操作，因此時(shí)間代價(jià)為O(1)階。RB樹的插入操作：1）調(diào)用Tree_Insert(root,x)函數(shù)完成二叉搜索樹的插入操作2）調(diào)用Tree_Rotation(root.x)函數(shù)，并對(duì)結(jié)點(diǎn)的著色進(jìn)行調(diào)整，使之恢復(fù)為一個(gè)RB樹。插入操作算法RB_Insert(root,x)這個(gè)算法主要完成兩件事：Fig.4.9給出了一個(gè)簡(jiǎn)單的實(shí)例，作為RB_Insert()算法運(yùn)行的示意圖。Fig.4.9給出了一個(gè)簡(jiǎn)單的實(shí)例，作為RB_Insert(從算法RB_Insert()的執(zhí)行過程可以看出：0°(原RB樹中不存在連續(xù)兩層結(jié)點(diǎn),其顏色均為紅(R),若某結(jié)點(diǎn)為R,則其父結(jié)點(diǎn)一定為B)1°對(duì)于空樹或插入后x->p為black結(jié)點(diǎn)的情形，無需進(jìn)一步處理；(插入時(shí)從最底層插入,所以從插點(diǎn)的x以下均為違規(guī))2°x->p為red結(jié)點(diǎn)時(shí)，按x的父結(jié)點(diǎn)x->p是其父結(jié)點(diǎn)x->p->p的左、右子結(jié)點(diǎn)兩種情況（對(duì)稱）處理。若為左，則y指向x->p的右兄弟（否則y指向左兄弟）3°這時(shí)y的顏色分為兩種情況，如果y->c=R，則按case1處理，即調(diào)整x->p、y及其父x->p->p的顏色，并將x指向x->p->p進(jìn)行新一輪向上調(diào)整。4°如果y->c=B,則若x為x->p的右子，則按case2處理，即以x->p為x進(jìn)行左旋，同時(shí)變?yōu)閏ase3,再進(jìn)行case3處理5°否則（即，x為x->p左子）即為case3,(首先按case1處理，對(duì)以x->p->p為根的子樹進(jìn)行調(diào)整，然后向上擴(kuò)展，分別按case2、case3處理。)case1:(x為紅,x->p為紅,x->p的兄弟為紅)

否則(x->p的兄弟為B)case2(x為右孩子),變?yōu)閏ase3case3(x為左孩子)RB樹的Delete算法與RB_Insert()算法的思路是一致的，首先按二叉搜索樹的刪除方法刪去需要?jiǎng)h除的結(jié)點(diǎn)。在刪除過程中會(huì)出現(xiàn)三種情形，在第二、三種情形中，若被摘除（spliced-out）結(jié)點(diǎn)是black結(jié)點(diǎn)，這時(shí)Red-Black性質(zhì)4可能被破壞，就需要對(duì)RB樹進(jìn)行恢復(fù)，恢復(fù)方法與插入操作后的修復(fù)類似。xy從算法RB_Insert()的執(zhí)行過程可以看出：xy4.4.3關(guān)于Red-Black樹的幾點(diǎn)討論

1.RB樹是一種二叉搜索樹，在其上進(jìn)行的查詢操作Search、Minimum、Maximum、Successor、Predecessor等與一般二叉搜索樹的查詢操作完全相同，而且算法簡(jiǎn)明，也即RB樹具有一般二叉搜索樹的優(yōu)點(diǎn)。2.如定理4.4所指出的，RB樹是平衡樹，在其上進(jìn)行的所有操作的時(shí)間代價(jià)都是O(logn)階的，RB樹的樹高h(yuǎn)總是保持在一個(gè)很小的范圍，即h≤2ln(n-1)。3.RB樹與一般平衡樹的平衡機(jī)制不同，雖然它不需要計(jì)算平衡因子，但Red-Black性質(zhì)（特別是性質(zhì)4）保證了整棵樹的平衡性，即絕大多數(shù)內(nèi)部結(jié)點(diǎn)有兩個(gè)子結(jié)點(diǎn)。事實(shí)上，red結(jié)點(diǎn)不可能僅有一個(gè)black子結(jié)點(diǎn)，而只可能為以下兩種情形之一：有兩個(gè)black（數(shù)據(jù)）子結(jié)點(diǎn)；或左、右子結(jié)點(diǎn)均為NULL。4.4.3關(guān)于Red-Black樹的幾點(diǎn)討論black結(jié)點(diǎn)的子結(jié)點(diǎn)有三種情形：有兩個(gè)（數(shù)據(jù)）子結(jié)點(diǎn)；左右子結(jié)點(diǎn)為NULL；第三種情形只可能出現(xiàn)在樹的下層，只有一個(gè)數(shù)據(jù)子結(jié)點(diǎn)，這時(shí)該子結(jié)點(diǎn)必為red，且子結(jié)點(diǎn)左右兒子為空。如Fig.4.10所示。（以上情況均與性質(zhì)4有關(guān)，即任一結(jié)點(diǎn)到結(jié)點(diǎn)的黑高相同)RB樹幾乎是一個(gè)2-樹，不可能出現(xiàn)單鏈的情形，從而保證了整棵樹的平衡性。black結(jié)點(diǎn)的子結(jié)點(diǎn)有三種情形：有兩個(gè)（數(shù)據(jù)）子結(jié)點(diǎn)；左右建RB樹例202019插入20,19,18,17,16201918case320191820191817case12019181720191817Root->c=B2019171618case3181920222019171818192220其他case1建RB樹例202019插入20,19,18,17,162014.另一種非二叉的平衡搜索樹——2-3-4樹，很容易轉(zhuǎn)變?yōu)镽ed-Black樹。4.另一種非二叉的平衡搜索樹——2-3-4樹，很容易轉(zhuǎn)變?yōu)?.52-3-4樹4.5.12-3-4樹及其實(shí)例

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

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

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

x->key>key2轉(zhuǎn)向p3。4.52-3-4樹4.5.12-3-4樹及其實(shí)例4-結(jié)點(diǎn)與3-結(jié)點(diǎn)類似，增加了key3域和p4指針。在2-3-4樹種，4-結(jié)點(diǎn)是一種臨時(shí)結(jié)點(diǎn)，在插入和刪除過程中可能產(chǎn)生4-結(jié)點(diǎn)，但該結(jié)點(diǎn)可隨時(shí)由三個(gè)2-結(jié)點(diǎn)取代。(key1<key2<key3,根據(jù)key與三者的關(guān)系分別轉(zhuǎn)向相應(yīng)子樹)(由于4-結(jié)點(diǎn)是臨時(shí)的,所以實(shí)為一棵3-序B樹,否則為一棵4-序B樹)2.2-3-4樹的最主要的特征是其所有的葉結(jié)點(diǎn)都在同一深度。如Fig.4.11所示：假定動(dòng)態(tài)數(shù)據(jù)集的關(guān)鍵字值域?yàn)橛⒄Z字母集合，即從小到大為A,B,C,D,E,...,X,Y,Z。圖中的結(jié)點(diǎn)I是根，是一個(gè)2-結(jié)點(diǎn)，其左子樹中的關(guān)鍵字值均小于I，右子樹中的關(guān)鍵字值均大于I，該樹T中只有2-結(jié)點(diǎn)和3-結(jié)點(diǎn)。4-結(jié)點(diǎn)與3-結(jié)點(diǎn)類似，增加了key3域和p4指針。在2-34.5.22-3-4樹上的查詢操作算法

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

2-3-4樹的插入算法是保證樹的基本特征（即所有葉結(jié)點(diǎn)在同一深度）的關(guān)鍵。在插入時(shí)，2-結(jié)點(diǎn)可以變?yōu)?-結(jié)點(diǎn)，3-結(jié)點(diǎn)可以變?yōu)?-結(jié)點(diǎn)，當(dāng)出現(xiàn)4-結(jié)點(diǎn)時(shí)，自動(dòng)分裂為三個(gè)2-結(jié)點(diǎn)，并且把中間的2-結(jié)點(diǎn)插入到上一層的父結(jié)點(diǎn)中。在一般二叉搜索樹中，每插入一個(gè)結(jié)點(diǎn)是在最下層添加一個(gè)葉結(jié)點(diǎn)，而2-3-4樹是在整體擴(kuò)大的情況下進(jìn)行向上擴(kuò)展。(但開始時(shí)也是從最底層的內(nèi)部結(jié)點(diǎn)開始,如下圖中(4)插入R)每當(dāng)樹增加一層時(shí)，即是把根結(jié)點(diǎn)上升一層，于是樹中所有結(jié)點(diǎn)的深度同時(shí)加1。4.5.22-3-4樹上的查詢操作算法課件】計(jì)算機(jī)算法設(shè)計(jì)與分析-[105頁]在插入算法中，一旦產(chǎn)生了4-結(jié)點(diǎn)就要進(jìn)行分裂，這時(shí)就會(huì)利用到父結(jié)點(diǎn)指針p。在4-結(jié)點(diǎn)分裂時(shí)，存在三種情形：(1)4-結(jié)點(diǎn)是2-3-4樹的根，這時(shí)，中間的2-結(jié)點(diǎn)作為新的根，樹增加一層；(2)4-結(jié)點(diǎn)的父結(jié)點(diǎn)是一個(gè)2-結(jié)點(diǎn)，只需把4-結(jié)點(diǎn)中的中間關(guān)鍵字插入到2-結(jié)點(diǎn)，該2-結(jié)點(diǎn)變?yōu)?-結(jié)點(diǎn)；(3)4-結(jié)點(diǎn)的父結(jié)點(diǎn)是一個(gè)3-結(jié)點(diǎn)，把4-結(jié)點(diǎn)的中間關(guān)鍵字插入到這個(gè)3-結(jié)點(diǎn)中，該3-結(jié)點(diǎn)又變成一個(gè)新的4-結(jié)點(diǎn)，于是繼續(xù)向上分裂。假設(shè)插入時(shí)樹高為h，插入過程在最壞情形下是從根到葉、再從葉到根，至多進(jìn)行2h次處理，因此插入算法的時(shí)間代價(jià)仍是O(h)階的。在插入算法中，一旦產(chǎn)生了4-結(jié)點(diǎn)就要進(jìn)行分裂，這時(shí)就會(huì)利用到4.5.42-3-4樹的性能分析

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

1.2-3-4樹實(shí)際上是一種2-3樹(即為3-序B樹)，4-結(jié)點(diǎn)是臨時(shí)結(jié)點(diǎn)，不會(huì)占用較多空間，可以分配臨時(shí)性的工作單元存放4-結(jié)點(diǎn)。4.5.42-3-4樹的性能分析2.可以采用同一種數(shù)據(jù)類型來表示2-結(jié)點(diǎn)和3-結(jié)點(diǎn)（按3-結(jié)點(diǎn)來設(shè)計(jì)），只在type域用不同的標(biāo)記來區(qū)分結(jié)點(diǎn)類型即可。3.為了減少插入算法的代價(jià)，還有一種把分裂4-結(jié)點(diǎn)的工作分?jǐn)偟讲煌牟僮髦腥サ姆桨?，即每次生?-結(jié)點(diǎn)時(shí)進(jìn)行一次分裂，如果其父結(jié)點(diǎn)又變?yōu)?-結(jié)點(diǎn)，則不在這一次插入操作中繼續(xù)分裂。當(dāng)進(jìn)行下次插入或搜索操作時(shí)，每遇到一個(gè)4-結(jié)點(diǎn)就進(jìn)行一次分裂，這樣可以減少一次插入操作的代價(jià)。4.與插入算法相比，刪除操作Delete算法是一個(gè)逆過程。插入操作中，關(guān)鍵字要按規(guī)則逐層向上插入，而刪除操作應(yīng)在刪除其關(guān)鍵字后按一定規(guī)則逐層向下壓，2.可以采用同一種數(shù)據(jù)類型來表示2-結(jié)點(diǎn)和3-結(jié)點(diǎn)（按3-5.2-3-4樹獲得平衡性的方法很巧妙，但缺點(diǎn)是結(jié)點(diǎn)類型較為復(fù)雜，可以通過一種簡(jiǎn)單的變換把2-3-4樹轉(zhuǎn)化為二叉搜索樹。方法是把2-3-4樹中的3-結(jié)點(diǎn)（或4-結(jié)點(diǎn)）用一個(gè)2-結(jié)點(diǎn)結(jié)構(gòu)來取代，取代的方法如Fig.4.13所示。5.2-3-4樹獲得平衡性的方法很巧妙，但缺點(diǎn)是結(jié)點(diǎn)類型較用上述變換將Fig.4.11中的2-3-4樹轉(zhuǎn)化為一個(gè)二叉搜索樹，不難發(fā)現(xiàn)，這是一棵RB樹。從中也可以看出RB樹與2-3-4樹的內(nèi)在聯(lián)系。用上述變換將Fig.4.11中的2-3-4樹轉(zhuǎn)化為一個(gè)二叉搜4.6Hashing技術(shù)4.6.1Hash算法的基本思想與一般模型

Hash方法的基本思想是，首先產(chǎn)生從可能的關(guān)鍵字集合（又稱全域）U=[0..N-1]到存儲(chǔ)空間（Hash表）地址集合T=[0..m-1]的一個(gè)映射函數(shù)：h:U[0..m-1]。于是，要存儲(chǔ)或檢索關(guān)鍵字為x∈U的數(shù)據(jù)項(xiàng)只需計(jì)算函數(shù)h(x)，直接得到該數(shù)據(jù)項(xiàng)應(yīng)在的地址。Fig.4.15中給出了一個(gè)簡(jiǎn)單的實(shí)例，其中N=100，m=7，h(x)=xmod7。4.6Hashing技術(shù)4.6.1Hash算法的然而對(duì)不同的關(guān)鍵字x,y∈U，h(x)=h(y)的情況可能出現(xiàn)，這種情形稱為沖突（collision）。由于一般的|U|遠(yuǎn)遠(yuǎn)大于m，沖突難以避免，因此Hash技術(shù)研究的基本問題是：(1)設(shè)計(jì)一個(gè)好的Hash函數(shù)，計(jì)算簡(jiǎn)單，而又使數(shù)據(jù)項(xiàng)分布均勻以減少?zèng)_突；(2)設(shè)計(jì)解決沖突的策略和算法。集合為實(shí)際存于Hash表中的關(guān)鍵字集合，|S|=n≤N。

=n/m稱為負(fù)載因子（loadfactor）,值是決定哈希算法性能的主要因素。(值小于1,越小越浪費(fèi)空間,越接近1性能越下降)Hash算法的“散列”存儲(chǔ)方式，使得它不能支持Minimum、Maximum、Successor、Predecessor這類的操作，而對(duì)于Search、Insert、Delete操作不但可以支持而且有較高的性能。然而對(duì)不同的關(guān)鍵字x,y∈U，h(x)=h(y)的情況可能出從抽象數(shù)據(jù)類型（ADT）的觀點(diǎn)來說，Hash算法用于實(shí)現(xiàn)字典（Dictionary）類型，實(shí)際關(guān)鍵字集合S為固定不變時(shí)，稱為靜態(tài)字典，只支持Search操作，S為可變時(shí)，即動(dòng)態(tài)數(shù)據(jù)集，稱為動(dòng)態(tài)字典，動(dòng)態(tài)字典支持搜索、插入和刪除操作。4.6.2Hash函數(shù)的設(shè)計(jì)

Hash函數(shù)的設(shè)計(jì)一般應(yīng)能兼顧計(jì)算簡(jiǎn)單和分布均勻，在大多數(shù)應(yīng)用問題中，可能的關(guān)鍵字集合U往往遠(yuǎn)遠(yuǎn)大于地址空間的規(guī)模。例如以姓名字符串作為關(guān)鍵字，|U|=N是一個(gè)極大的值，而Hash表的長(zhǎng)度m和實(shí)際關(guān)鍵字集合S（|S|=n）與N相比小得多。因此，分布均勻的要求就是要對(duì)于使盡量小，|.|集合的勢(shì)(求集合元素的個(gè)數(shù))其中h-1(i)為被h映射至地址i的關(guān)鍵字全體。從抽象數(shù)據(jù)類型（ADT）的觀點(diǎn)來說，Hash算法用于實(shí)現(xiàn)字典當(dāng)且僅當(dāng)時(shí)達(dá)到最小值，意味著將無任何沖突產(chǎn)生。無沖突的Hash函數(shù)稱為完備Hash函數(shù)（PerfectHashFunction），簡(jiǎn)稱PHF。事實(shí)上，無沖突的要求是極難達(dá)到的?！吧浙Ｕ摗敝赋?，在23個(gè)人中，有兩個(gè)人的生日在同一天的概率為0.51，即當(dāng)|S|=n=23，m=365時(shí)，發(fā)生沖突的概率已經(jīng)在50%以上。而當(dāng)n=50時(shí)，發(fā)生沖突的概率已達(dá)0.97。在D.Knuth所舉的實(shí)例中指出，當(dāng)n=31，m=41時(shí)，無沖突的映射函數(shù)只占全部可能映射函數(shù)的1/107。因此，在大多數(shù)情形下只能追求將沖突盡可能減少。常用的Hash函數(shù)設(shè)計(jì)方法：1.除式法（Divisionmethod）令h(x)取用m除x的余數(shù)，即h(x)=xmodm。當(dāng)且僅當(dāng)這種Hash函數(shù)計(jì)算速度最快。在設(shè)計(jì)時(shí)，m取值不要習(xí)慣性地取為2的n次冪。因?yàn)檫@會(huì)使得h(x)的取值只依賴于關(guān)鍵字的2進(jìn)制值的最后幾位，這不利于數(shù)據(jù)在Hash表中的均勻分布。一般情況下m值最好取為不與某個(gè)2n值相近的素?cái)?shù)。2.乘式法（Multiplicationmethod）可方便地取m=2p，映射函數(shù)可表示為：其中a為常數(shù)0<a<1，表示取乘積的分?jǐn)?shù)部分，即。常數(shù)a的選取會(huì)影響到Hash函數(shù)的性能，如何選取a的值與關(guān)鍵字值的特征有關(guān)。已有的研究指出取最好。此時(shí)，Hash函數(shù)表示為：例如，取m=1024，當(dāng)x=42237時(shí)，

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

即關(guān)鍵字x=42237映射到Hash表T[0...1023]中的位置是T[477]。這種Hash函數(shù)計(jì)算速度最快。在設(shè)計(jì)時(shí)，m取值不要習(xí)慣性地取3.位選取法（Hash-bitExtraction）和平方取中法（Mid-square）基本思想是：把地址空間T的大小m取作m=2p，p為某整數(shù)，例如m=216，即T[0..65535]。無論關(guān)鍵字x為數(shù)字或字符串，都一定可以轉(zhuǎn)變?yōu)橐粋€(gè)較長(zhǎng)的二進(jìn)制串，那么h(x)的值就可以取與關(guān)鍵字對(duì)應(yīng)的二進(jìn)制串中指定的16位所形成的二進(jìn)制數(shù)。經(jīng)常采用的平方取中法的基本思想則是，首先計(jì)算關(guān)鍵字值的平方x2，在平方值的二進(jìn)制序列中取中間的若干位，例如：U=[0..999]，x=459，m=210，

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

則h(x)=(1101110000)2=880由于在定義函數(shù)h(x)時(shí)，到底選取二進(jìn)制序列的哪些位帶有任意性，映射后的地址可能有較均勻的分布，使得沖突減少。3.位選取法（Hash-bitExtraction）和平4.6.3解決沖突的策略

不同策略之間的主要區(qū)別是：(1)沖突項(xiàng)存到何處：一種方法是把它們?nèi)源娴紿ash表中；另一種方法則是另開辟溢出區(qū)（或鏈區(qū)）存放溢出數(shù)據(jù)。(2)如何從地址h(x)找到?jīng)_突項(xiàng)的存儲(chǔ)位置：一種方法是仍用計(jì)算的方式一次次地計(jì)算沖突項(xiàng)的地址；另一種方法就是用指針形成鏈表。1.開地址法（Openaddressing）開地址法是一種單區(qū)法，不需要額外的存儲(chǔ)空間，沖突項(xiàng)放在Hash表T[0..m-1]的其它空位，數(shù)據(jù)元素存儲(chǔ)位置的確定也通過Hash函數(shù)計(jì)算。這時(shí)Hash函數(shù)的自變量除了關(guān)鍵字之外，還有一個(gè)查找序號(hào)i，最簡(jiǎn)單的映射方法稱作線性查找Hash函數(shù)：,i=0,1,2,...。4.6.3解決沖突的策略例如：設(shè)h‘(x)=(5x)mod8，關(guān)鍵字為6個(gè)年代：1055、1492、1776、1812、1918、1945。直接存入Hash表會(huì)產(chǎn)生一次沖突：x=1492、x=1812都映射到地址4，如Fig.4.16所示。采用線性開地址方法，函數(shù)h(x,i)把這6個(gè)關(guān)鍵字依次插入到表中。每次插入過程中，剛開始時(shí)i的取值為0，若T[h(x,0)]為空則進(jìn)行插入，若T[h(x,0)]已被占用，i值加1，繼續(xù)檢查T[h(x,1)]是否也被占用，如此重復(fù)直到完成。Hash表的插入算法Hash_Insert例如：設(shè)h‘(x)=(5x)mod8，關(guān)鍵字為6個(gè)年代：10該實(shí)例中，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é)果。該實(shí)例中，Hash_Insert(T,x)的執(zhí)行過程為：線性開地址法的搜索算法Hash_Search另一種更一般的開地址函數(shù)稱為二次Hashing函數(shù)（DoubleHashing），其映射函數(shù)表示為：這種Hash函數(shù)緩解了由于順序查找空位造成的Hash表的局部擁擠現(xiàn)象，適當(dāng)選擇h2(x)，可以使查找序列也具有隨機(jī)性，有利于提高查找算法的性能。例如：在插入關(guān)鍵字=1613的過程中，當(dāng)?shù)刂穐(x,i)已被其它關(guān)鍵字占用時(shí)，查找空位的下標(biāo)序列為：1、9、4、12、7、2、10、5、0、8、3、11、6…，顯然折衷方案有利于關(guān)鍵字在Hash表中的均勻分布。不過在選擇h1(x)和h2(x)時(shí)必須使上述的查找空位的下標(biāo)序列遍歷整個(gè)Hash表。為此可設(shè)計(jì)映射函數(shù)為：

其中取m為一素?cái)?shù)，m'為略小于m的整數(shù)。再重復(fù)1、9、4、12線性開地址法的搜索算法Hash_Search再重復(fù)1、9、開地址Hashing算法的分析分兩種情形：當(dāng)動(dòng)態(tài)數(shù)據(jù)集的所有數(shù)據(jù)的關(guān)鍵字都被映射到同一地址時(shí)，最壞情形發(fā)生，這時(shí)的時(shí)間代價(jià)顯然是O(n)階的。由于影響問題的因素有：Hash函數(shù)的選擇、沖突的處理策略、關(guān)鍵字集合S在全集U中的分布情形和Hash表的大小，計(jì)算Hash函數(shù)的平均時(shí)間代價(jià)較難，但最為重要。均勻Hashing（uniformhashing）為了對(duì)開地址Hash算法的搜索與插入時(shí)間代價(jià)進(jìn)行統(tǒng)一概率分析，首先要假定它是一種均等狀態(tài)。即假定：每個(gè)關(guān)鍵字有相同的機(jī)會(huì)被映射到Hash表的不同位置；每個(gè)關(guān)鍵字的查找下標(biāo)序列，應(yīng)等可能的作為0,1,...,m-1的一個(gè)排列。開地址Hashing算法的分析命題4.3在uniformhashing的條件下，對(duì)于開地址Hash表的不成功搜索（或插入）操作所需的期望查找（probes）次數(shù)至多為次，其中。命題4.4在uniformhashing的條件下，對(duì)于開地址Hash表的成功搜索操作所需的期望查找（probes）次數(shù)至多為次，其中。對(duì)于Hash表的不成功搜索，指搜索的關(guān)鍵字x不在表中，因此查找的代價(jià)應(yīng)與插入一個(gè)新數(shù)據(jù)項(xiàng)的代價(jià)相同。命題說明：利用Hash技術(shù)實(shí)現(xiàn)的字典抽象數(shù)據(jù)類型（ADT），其搜索和插入代價(jià)與數(shù)據(jù)項(xiàng)數(shù)n無關(guān)，也就是說時(shí)間代價(jià)是O(1)階的。這說明了對(duì)于大數(shù)據(jù)集合的組織與檢索，Hash技術(shù)的效率優(yōu)于平衡樹。命題4.3在uniformhashing的條件下，對(duì)于負(fù)載因子的值對(duì)算法性能有影響，在接近于1時(shí)，算法性能明顯降低。很小會(huì)浪費(fèi)存儲(chǔ)空間，接近于1則算法性能降低，所以應(yīng)取適當(dāng)?shù)闹?。開地址法有增加沖突鏈長(zhǎ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)象擴(kuò)大了因沖突造成的負(fù)面影響。而鏈接法避免了這種缺陷。負(fù)載因子的值對(duì)算法性能有影響，2.鏈接法（Chainedhashing）又稱閉地址法。它打破了數(shù)據(jù)項(xiàng)存于Hash表T[0..m-1]之內(nèi)的限制。實(shí)際上它是一個(gè)雙區(qū)法，即沖突項(xiàng)不存于表內(nèi)。這時(shí)的T是一個(gè)由m個(gè)鏈表組成的數(shù)組，T[i](i=0,1,...,m-1)表示映射到地址i的關(guān)鍵字序列，也可以把T[i]作為這個(gè)鏈表的首項(xiàng)（或頭指針）。2.鏈接法（Chainedhashing）在這種情況下，表長(zhǎng)m可以小于數(shù)據(jù)集S的大小n，負(fù)載因子n/m實(shí)際為平均表長(zhǎng)，也就是不成功搜索和插入操作的期望代價(jià)。而成功搜索的期望代價(jià)，大致為負(fù)載因子的一半。除了每個(gè)數(shù)據(jù)項(xiàng)必須增加一個(gè)指針域之外，Hash表本身可能包含較多的冗余信息，m值取得越小，負(fù)載因子越大，直接影響搜索的性能。3.單區(qū)鏈接法它是對(duì)開地址法的改進(jìn)。全部數(shù)據(jù)項(xiàng)置于Hash表中，但搜索中的查找序列不是通過計(jì)算而是通過指針鏈接。例如把關(guān)鍵字序列17、52、9、41、15、13、11按Hash函數(shù)h(x)=xmod7依單區(qū)鏈接法插入。Fig.4.19是插入的結(jié)果。在這種情況下，表長(zhǎng)m可以小于數(shù)據(jù)集S的大小n，負(fù)載因子n/m這種方法用指針操作代替二次Hashing函數(shù)的計(jì)算，性能有所提高。但與開地址法一樣，單區(qū)法因地址的互相占用，使映射到不同地址的沖突鏈合并到一起，往往使沖突鏈長(zhǎng)大大增加，使搜索效率降低。4.調(diào)諧式（Tuning）鏈接法其基本思想是把Hash表分為兩個(gè)區(qū)：T:[0..m’-1]為整個(gè)存儲(chǔ)區(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ā)生沖突，首先把沖突項(xiàng)存于鏈接區(qū)T[m..m‘-1]，避免了沖突鏈的交叉、加長(zhǎng)，僅在鏈接區(qū)裝滿時(shí)再鏈接到Hash區(qū)。這種方法把大部分沖突鏈置于鏈接區(qū)，吸取了鏈接法的優(yōu)點(diǎn)，同時(shí)又有一定的限度，避免了鏈接區(qū)的空間分配難以控制的缺點(diǎn)。Fig.4.20是一個(gè)簡(jiǎn)單實(shí)例的示意圖。(發(fā)生沖突時(shí)按單區(qū)鏈接法)這種方法用指針操作代替二次Hashing函數(shù)的計(jì)算，性能有所課件】計(jì)算機(jī)算法設(shè)計(jì)與分析-[105頁]調(diào)諧式Hash方法的性能與調(diào)諧因子和負(fù)載因子有關(guān)，在值確定時(shí)，可以求出一個(gè)最優(yōu)的值。相關(guān)的研究指出，當(dāng)取時(shí)，較好，這時(shí)的期望搜索代價(jià)為1.79次查找，而在一般情況下，取較好。4.6.4Hash算法的優(yōu)劣分析Hash方法獨(dú)特的按內(nèi)容尋址的檢索方式是一種高級(jí)的“聯(lián)想”式存儲(chǔ)與檢索技術(shù)。它的期望時(shí)間代價(jià)為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ù)等等。調(diào)諧式Hash方法的性能與調(diào)諧因子2.

Hash算法的最壞情形時(shí)間代價(jià)為O(n)階，使其不能在諸如防空系統(tǒng)、空中交通調(diào)度系統(tǒng)等“緊急”系統(tǒng)中采用，因?yàn)橐坏┏霈F(xiàn)一次最壞情形，會(huì)造成重大事故。3.前文對(duì)Hash算法的性能分析過程中，所有的分析結(jié)果都是在“實(shí)際關(guān)鍵字集合S是全域U的一個(gè)隨機(jī)子集”等條件下得到的。如果全集U中的關(guān)鍵字不是等可能性地出現(xiàn)在Hash表中，這種情況在實(shí)際問題中是經(jīng)常遇到的，例如關(guān)鍵字為程序中的標(biāo)識(shí)符名，有些名稱如m、n、m1、m2、m3等等，出現(xiàn)的概率遠(yuǎn)遠(yuǎn)多于其它名稱，在這種情形下，期望性能可能變差。對(duì)此，也有一些方法予以解決，如泛Hash（UniversalHashing）方法。4.命題4.3、4.4指出Hash算法的性能與負(fù)載因子的值密切相關(guān)。在數(shù)據(jù)集不斷增加時(shí)，負(fù)載因子逐漸增大，并接近于1，會(huì)使系統(tǒng)性能明顯下降。2.Hash算法的最壞情形時(shí)間代價(jià)為O(n)階，使其不能在例如或>0.95時(shí)，擴(kuò)大Hash區(qū)，即所謂空間倍增（arraydoubling）技術(shù)，需要把數(shù)據(jù)集中的所有數(shù)據(jù)按照新的Hash函數(shù)重新轉(zhuǎn)存入新的Hash區(qū)，這一工作代價(jià)很大。為解決空間倍增所需的高代價(jià)問題，可采用線性擴(kuò)張Hash算法?；舅枷胧侵付ㄒ粚?duì)負(fù)載因子的上限和下限，在可能關(guān)鍵字集合S的大小n改變的過程中，一旦超過，存儲(chǔ)區(qū)擴(kuò)充一個(gè)桶（可存放b條數(shù)據(jù)項(xiàng)），當(dāng)小于時(shí)，存儲(chǔ)區(qū)縮減一個(gè)桶。這樣就保證動(dòng)態(tài)數(shù)據(jù)集上的操作總是在良好的性能下工作。*4.6.5Hash技術(shù)的幾種新發(fā)展(選講)完備Hash函數(shù)（PerfectHashFunction）(引文1,引文2)(ZbigniewJ.Czech,Anoptimalalgorithmforgeneratingminimalperfecthashfunctions,InformationProcessingLetters,43(5):257-264,1992)例如完備哈希函數(shù)（PHF）又稱無沖突哈希函數(shù)。即PHF的地址映射不產(chǎn)生沖突，一次計(jì)算即可找到目標(biāo)數(shù)據(jù)項(xiàng)。因此，用PHF實(shí)現(xiàn)的檢索算法的最好、平均和最壞情形時(shí)間復(fù)雜度都為O(1)階。其定義可敘述為：對(duì)任一實(shí)際關(guān)鍵字集合，函數(shù)h：稱為S的完備哈希函數(shù)（PHF），如果對(duì)任意，必有。當(dāng)m=n時(shí)，h稱為集合S的最小完備哈希函數(shù)（MPHF）。給定n（n不太大）個(gè)關(guān)鍵字集合和Hash表長(zhǎng)m，有幾種PHF的構(gòu)造技術(shù)：1）針對(duì)字符串關(guān)鍵字集合的啟發(fā)式算法假定集合中的關(guān)鍵字為字符串，設(shè)關(guān)鍵字k∈U為一個(gè)Σ={a,b,c,…,x,y,z}上的字符串，length(k)為字符串的長(zhǎng)，F(xiàn)(k)，L(k)分別為k的首末字符。完備哈希函數(shù)（PHF）又稱無沖突哈希函數(shù)。即PHF的地址映射求形如h(k)=length(k)+Value(F(k))+Value(L(k))的Hash函數(shù)。為了使h(k)為完備Hash函數(shù)，須對(duì)于函數(shù)Value：Σ→Z的值進(jìn)行適當(dāng)?shù)亩x，即要為Value(a)，Value(b)，…，Value(z)賦予適當(dāng)?shù)闹?，使得?duì)于S中的所有關(guān)鍵字，h(k)∈[0…m-1]有不同的值。Sager提出的一種改進(jìn)方法，是求形如：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法）

對(duì)于關(guān)鍵字集合S和Hash表地址集[0…m-1]，取t個(gè)Hash函數(shù)hj：S→[0…m-1](j=1…t)。按一定的算法計(jì)算出一個(gè)一維數(shù)組：array[0…m-1]∈[1…t]，稱為HIT表。求形如h(k)=length(k)+Value(F(k))+在h1，h2，…h(huán)t和HIT確定的條件下，定義完備Hash函數(shù)：h：S→[0…m-1]，使得對(duì)于關(guān)鍵字k∈S，h(k)=hj(k)，其中j∈{1,2,…,t}，滿足條件：HIT[hj(k)]=j。ProceduretoConstructHIT:t個(gè)hash函數(shù)beginKEYSET:={K1K2…Kn};setHIT()=0;//清HITforj=1tosbeginforallelementsinKEYSETdoHIT(d):=jifHIT(d)=0andhj(Kr)=d且不存在Kr’hj(Kr’)=d;KEYSET=KEYSET-{Kr|滿足上述條件的Kr},endend在h1，h2，…h(huán)t和HIT確定的條件下，定義完備Hash函在構(gòu)造HIT時(shí)，取第一個(gè)h1(),由于除k2與k8對(duì)應(yīng)的h1()無重復(fù)外，其他取值均有重復(fù)。因此HIT表中5，9元素均為1，即HIT(5)=1,HIT(9)=1；取h2()時(shí)（此時(shí)，k2,k8可略），首先h2(k1)=5,而HIT(5)已經(jīng)為1，所以略過，除k4外，其他關(guān)鍵字對(duì)應(yīng)的h2()值有重復(fù)，所以只將k4對(duì)應(yīng)的HIT表項(xiàng)HIT(2)賦值為2，即HIT(2)=2；同理，在取h3()時(shí)（此時(shí)，k2,k4,k8可略），首先，由于HIT中的5，2，9項(xiàng)均已賦值，所以k3,k5,k7略過，對(duì)于k1,k6,將HIT表中相應(yīng)項(xiàng)賦值，即HIT(4)=3,HIT(7)=3。在構(gòu)造HIT時(shí)，取第一個(gè)h1(),在已知t個(gè)Hash函數(shù)h1，h2，…h(huán)t和HIT表的條件下，用這個(gè)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!";}如果h1，h2，…h(huán)t和HIT表選擇正確，“failure”的情況不會(huì)出現(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個(gè)Hash函數(shù)h1h2…h(huán)t，然后，確定HIT表HIT[0…m-1]∈{1,2,…,t}的m個(gè)值，使得所定義的函數(shù)h為PHF，即對(duì)任何x,y∈S，x≠y有h(x)≠h(y)。在已知t個(gè)Hash函數(shù)h1，h2，…h(huán)t和HIT表的條件下，這個(gè)確定HIT表的過程類似于迷宮問題，八后問題，等組合問題，可以用回溯等搜索算法完成。如果滿足條件的HIT表不存在，可以在調(diào)整t值和t個(gè)Hash函數(shù)后重新構(gòu)造滿足條件的HIT表。(t越大，性能越不好)3）Fredman構(gòu)造法Fredman通過構(gòu)造法證明了，對(duì)任意的關(guān)鍵字集合至多取m=3n（即），一定可以在形如的Hash函數(shù)中找到S的完備哈希函數(shù)。構(gòu)造方法：已知：實(shí)際關(guān)鍵字集合，且|U|=N為素?cái)?shù)。①對(duì)此S，先構(gòu)造函數(shù)h'(x)=((kx)modN)modn。這個(gè)確定HIT表的過程類似于迷宮問題，八后問題，等組合問題，用枚舉法選擇k值，使得其中bi=|Si|，(i=0,1,…,n-1)，Si={x|x∈S,h'(x)=i}。Si是被h'映射為i的關(guān)鍵字集合。已經(jīng)證明，滿足條件的k值一定存在。②對(duì)此每個(gè)Si，(i=0,1,…,n-1)選擇適當(dāng)?shù)膋i，構(gòu)造函數(shù)hi(x)=((kix)modN)modCi。其中Ci=1+bi(bi-1)，使得為單一映射函數(shù)（無沖突）。由于這時(shí)的集合Si較小，Ci值也不大，因此ki一定存在。③取，定義函數(shù)使對(duì)于任意x∈Sh(x)=C0+C1+…+Ci-1+((kix)modN)modCi。其中i=h‘(x)=((kx)modN)modn。----x為第i組用枚舉法選擇k值，使得原文如下：1.選擇合適的k,利用hash函數(shù)h‘(x)=((kx)modN)modn將關(guān)鍵字集合分為n塊，即S1,S2,…,Sn,使得，其中bi=|Si|。

2.在hash表T中,T[0]存放k值，T[1],T[2],…,T[n]分別存放n塊的hash表指針。3.依次為塊Si分配(bi)2+2個(gè)單元（i=1,2,…,n），其中第1個(gè)單元地址即為存放在T[i]中的指針。4.塊Si對(duì)應(yīng)的前兩個(gè)單元分別存放ki,bi。5.對(duì)于塊Si中的關(guān)鍵字x,利用hash函數(shù)hi(x)=((kix)modN)modCi

進(jìn)行存?。ㄆ渲蠧i=(bi)2）原文如下：舉例:N=31,n=6,S={2,4,5,15,18,30},(K取1比下面取2更好)27101622T(0)T(1)T(2)T(3)T(4)T(5)T(6)114T(7)T(8)T(9)C2K2152T(10)T(11)T(12)T(13)T(14)T(15)C4K4231830T(16)T(17)T(18)T(19)T(20)T(21)C5K51115T(22)T(23)T(24)C6K6每一組多用2個(gè)單元存放C與K存放每組的指針K2舉例:N=31,n=6,S={2,4,5,15,18,30不難證明，函數(shù)h(x)是S∈U的一個(gè)完備哈希函數(shù)。上述構(gòu)造過程實(shí)際上要計(jì)算2n+1個(gè)值：k，k0，k1，…，kn-1和C0，C1，…，Cn-1。時(shí)間代價(jià)估計(jì)為O(n·N)，空間代價(jià)為5n+C。4）利用中國(guó)余數(shù)定理構(gòu)造MPHF中國(guó)余數(shù)定理指出：對(duì)于任意的n個(gè)整數(shù)R1，R2，…，Rn，和n個(gè)互素整數(shù)M1，M2，…，Mn，總可以找到一個(gè)常數(shù)C，使得Ri=CmodMi

對(duì)i=1…n成立。為了對(duì)關(guān)鍵字集合S={k1,k2,…,kn}構(gòu)造MPHF，只須把地址空間[0…m-1]=[0…n-1](m=n)的每一地址0，1，2，…，n-1視為中國(guó)余數(shù)定理中的R1，R2，…，Rn。k1k2…kn與n個(gè)素?cái)?shù)建立1－1對(duì)應(yīng)關(guān)系：P(ki)=Mii=1,2,…,n。不難證明，函數(shù)h(x)是S∈U的一個(gè)完備哈希函數(shù)。于是構(gòu)造MPHF的任務(wù)歸結(jié)為找到中國(guó)余數(shù)定理中的常數(shù)C。即令h(ki)=CmodP(ki)i=1,2,…,n。這種方法的難點(diǎn)是當(dāng)n較大時(shí)，C值的計(jì)算代價(jià)很高，下面是一種實(shí)用的構(gòu)造方法，設(shè)關(guān)鍵字ki為字符