【正文】 。 考察高為 h(0)的結(jié)點(diǎn) x， 由于 h0， x是 RB樹(shù)的內(nèi)部結(jié)點(diǎn) ，必有兩個(gè)子結(jié)點(diǎn) x x2， 其高為 h1， 且有 根據(jù)歸納假設(shè)，以 x x2為根的兩子樹(shù)分別至少有 個(gè)內(nèi)部結(jié)點(diǎn)， ∴ 以 x為根的子樹(shù)至少有 個(gè)內(nèi)部結(jié)點(diǎn)。 命題成立 。 定理 具有 n個(gè)內(nèi)部結(jié)點(diǎn)的 RB樹(shù)的樹(shù)高 h ≤ 2ln(n+1)。 一個(gè)在結(jié)構(gòu)上做了上述改變的二叉搜索樹(shù)稱(chēng)為一個(gè) RB樹(shù) 。 }kkth a ts u c hila l lfo rkkka n dji1:k{G jljilij ???????}kkth a ts u c hila l lfo rkkka n dji1:k{L jljilij ???????21 從 ， 對(duì)于 kj =17， Gj={21， 9}， Lj ={9。 上述情形是充分必要的，它可以敘述為： 命題 設(shè)二叉搜索樹(shù) T是依次把不同關(guān)鍵字 k1,k2,...,kn插入到一個(gè)原始為空的二叉搜索樹(shù)而得到的結(jié)果，則結(jié)點(diǎn) x（ xkey=ki）在 T中是結(jié)點(diǎn) y（ ykey=kj）的祖先的充要條件是： }kka n dil1:km a x {kor}kka n dil1:km i n {k jllijlli ????????19 在 ， kj=17。 2. 在 RBST中結(jié)點(diǎn) x為結(jié)點(diǎn) y的祖先的充要條件： 首先分析從根到樹(shù)上任一結(jié)點(diǎn) y（ ykey=kj,1j≤n）的路徑上的結(jié)點(diǎn)特征。這里的按隨機(jī)順序是指， n個(gè)不同關(guān)鍵字的 n!種不同排列的出現(xiàn)是等可能的。 過(guò)程如圖所示： 15 16 刪除操作算法 Tree_Delete 這個(gè)算法除了調(diào)用函數(shù) Tree_Successor(root,z)的時(shí)間代價(jià)為O(h)外 ， 其余各處的時(shí)間代價(jià)均為 O(1)階 。 因此有下面的結(jié)論： 定理 動(dòng)態(tài)數(shù)據(jù)集合的查詢(xún)操作 Search、 Minimum、Maximum、 Successor、 Predecessor可通過(guò)二叉搜索樹(shù)實(shí)現(xiàn) ，其算法可在 O(h)時(shí)間內(nèi)完成 ， 其中 h為二叉搜索樹(shù)的高 。 Tree_Search算法 11 求最小元 （ 或最大元 ） 的操作只需從根開(kāi)始沿著左指針 （ 或右指針 ） 一直搜索至某一結(jié)點(diǎn) x， 其 left或 right指針為 NULL，這時(shí)結(jié)點(diǎn) x的關(guān)鍵字 xkey為最小 （ 或最大 ） 。兩個(gè) BST(a)和 (b)有不同的樹(shù)高，前者比后者的查詢(xún)效率更高。 8 二叉搜索樹(shù) 二叉搜索樹(shù)又稱(chēng)為二元字典樹(shù)，是一種最常用的動(dòng)態(tài)數(shù)據(jù)集的數(shù)據(jù)結(jié)構(gòu)，可以用于實(shí)現(xiàn)字典和優(yōu)先隊(duì)列等 ADT。 搜索算法 （ 及相關(guān)操作算法 ） 的設(shè)計(jì)實(shí)際上是實(shí)現(xiàn)適合各種不同應(yīng)用需要的 ADT， 例如： 字典（ Dictionary）作為抽象數(shù)據(jù)類(lèi)型，可以分為兩類(lèi)： 若 x指向最后一個(gè)數(shù)據(jù)元素 ， 則返回 NULL。 ? Deletemin(S)： 刪除最小元 ， 一個(gè)修改操作 。 ? Minimum(S)： 求最小元，一個(gè)查詢(xún)操作。 6 ? Insert(S,x)： 插入 ， 一個(gè)修改操作 。 數(shù)據(jù)集合上的操作 （ operation） 可以分為兩類(lèi)： ?查詢(xún) （ queries） 操作： 對(duì)數(shù)據(jù)集不做任何變動(dòng) ， 僅僅返回有關(guān)集合的某些信息； ?修改 （ modifying operations） 操作： 要對(duì)數(shù)據(jù)集合的某些域進(jìn)行改動(dòng) 。 } 更為靈活的存儲(chǔ)形式是利用指針和鏈表（例如線性鏈表和樹(shù)結(jié)構(gòu)），這種存儲(chǔ)形式在搜索算法中經(jīng)常用到。 newElements = new Object(newSize) 。 Object[arraySize] elements。1 計(jì)算機(jī)算法 —— 設(shè)計(jì)與分析導(dǎo)論 南開(kāi)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)系 劉 璟 2 Chapter 4. 數(shù)據(jù)集合上的搜索(Searching)算法 ? 動(dòng)態(tài)數(shù)據(jù)集 (Dynamic Set)與抽象數(shù)據(jù)類(lèi)型 (ADT) ? 二叉搜索樹(shù) (Binary Search Trees) ? 隨機(jī)二叉搜索樹(shù) (Randomly Built Binary Search Tree) ? 紅黑樹(shù) (RedBlack Tree) ? 234樹(shù) ? Hashing技術(shù) 3 動(dòng)態(tài)數(shù)據(jù)集 (Dynamic Set)與抽象數(shù)據(jù)類(lèi)型 (ADT) 靜態(tài)數(shù)據(jù)集 （ Static Set）中的數(shù)據(jù)是固定不變的。 ... } //Object為數(shù)據(jù)元素的類(lèi)型， setSize為當(dāng)前集合中的元素個(gè)數(shù) 4 用數(shù)組表示集合操作方便 ， 但當(dāng)集合中的元素個(gè)數(shù)不斷增加時(shí) ， 數(shù)組的長(zhǎng)度必須擴(kuò)大 。 Transfer all elements from the to the newElement。 5 搜索問(wèn)題： 在集合中檢索出其關(guān)鍵字域的值等于給定值的數(shù)據(jù)元素 。 一些典型的操作： ? Search(S,k)： 搜索，一個(gè)查詢(xún)操作。 把由 x指向的數(shù)據(jù)元素加入到集合 S中 ， 一般假定在 x指向的數(shù)據(jù)元中 ， 與集合運(yùn)算相關(guān)的所有分量 （ 域 ） 都已經(jīng)初始化 。若集合 S中所有數(shù)據(jù)元素的關(guān)鍵字值為一全序集，則返回具有最小關(guān)鍵字值的數(shù)據(jù)元素的指針。 它相當(dāng)于Minimum(S)和 Delete(S,x)的聯(lián)合 ， 即： Delete(S,Minimum(S))。 ? Predecessor(S,x)： 求前導(dǎo)數(shù)據(jù)元 ， 一個(gè)查詢(xún)操作 。靜態(tài)字典：（靜態(tài)數(shù)據(jù)集 S， Search）； ? 二叉搜索樹(shù)（ Binary Search Trees） 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è)指針?lè)謩e指向該結(jié)點(diǎn)的左兒子、右兒子和父結(jié)點(diǎn)。 10 遍歷二叉搜索樹(shù)的所有結(jié)點(diǎn)可以采用中序遍歷 （ inorder tree walk） 算法 ， 即可將與二叉搜索樹(shù)樹(shù)結(jié)點(diǎn)相對(duì)應(yīng)的數(shù)據(jù)項(xiàng)按關(guān)鍵字從小到大排列出來(lái) 。 求最小元的算法 Tree_Minimum(root) 求最大元的算法 Tree_Maximum(root) 求數(shù)據(jù)項(xiàng)的后繼與前導(dǎo)項(xiàng)的操作要相對(duì)復(fù)雜 ， 如 ， 結(jié)點(diǎn) 15（ 指關(guān)鍵字為 15的結(jié)點(diǎn) )的后繼是結(jié)點(diǎn) 17， 它是結(jié)點(diǎn) 15的右子樹(shù)中的最小元 。 ? 插入與刪除操作 動(dòng)態(tài)數(shù)據(jù)集上的 Insert(S,x)、 Delete(S,x)操作與查詢(xún)操作不同 ，它們會(huì)引起二叉搜索樹(shù)本身的變化 。 Tree_Insert(root,z)的運(yùn)行是在從根到某一個(gè)葉結(jié)點(diǎn)的一條路徑上進(jìn)行的 ， 因此有下面的結(jié)論 。 定理 由 n個(gè)不同的關(guān)鍵字組成的隨機(jī)二叉搜索樹(shù)的平均樹(shù)高為 h=O(logn)。分析的結(jié)果是，在這條路上的每個(gè)結(jié)點(diǎn) x（ xkey= ki）都具有下列特征： 從圖 (a)中可以看到 ， 從根到結(jié)點(diǎn) 17的路徑上的 4個(gè)結(jié)點(diǎn)的關(guān)鍵字都符合上述條件 ， 而且 ， 從 (b)表中的關(guān)鍵字序列中可以看出 ， 關(guān)鍵字 17前面的 10個(gè)關(guān)鍵字中滿足命題 2 1 12全是結(jié)點(diǎn) 17的祖先 。 12}， 所以 kj的深度為 4。 23 24 RB樹(shù)滿足下面的性質(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)。 證明： 1. 首先用歸納法證明以 RB樹(shù)上任一結(jié)點(diǎn) x為根的子樹(shù)至少 包含 個(gè)內(nèi)部結(jié)點(diǎn)。 2176。 ∴ 歸納完成。 故有 ， 定理得證 。 對(duì)于結(jié)點(diǎn)間指針鏈接關(guān)系的修改歸結(jié)為 旋轉(zhuǎn) （ Rotation）操作，旋轉(zhuǎn)是調(diào)整樹(shù)的平衡狀態(tài)的基本手段。 Right_Rotation(root,x)的算法與 Left_Rotation(root,x)類(lèi)似 。 算法不存在與結(jié)點(diǎn)數(shù) n相關(guān)的操作，因此時(shí)間代價(jià)為 O(1)階。 對(duì)于空樹(shù)或插入后 xp為 black結(jié)點(diǎn)的情形，無(wú)需進(jìn)一步處理； 2176。 33 ? 關(guān)于 RedBlack樹(shù)的幾點(diǎn)討論 1. RB樹(shù)是一種二叉搜索樹(shù) ， 在其上進(jìn)行的查詢(xún)操作 Search、Minimum、 Maximum、 Successor、 Predecessor等與一般二叉搜索樹(shù)的查詢(xún)操作完全相同 ， 而且算法簡(jiǎn)明 ， 也即 RB樹(shù)具有一般二叉搜索樹(shù)的優(yōu)點(diǎn) 。 34 black結(jié)點(diǎn)的子結(jié)點(diǎn)有三種情形：有兩個(gè) （ 數(shù)據(jù) ） 子結(jié)點(diǎn)；左右子結(jié)點(diǎn)為 NULL；第三種情形只可能出現(xiàn)在樹(shù)的下層 ， 只有一個(gè)數(shù)據(jù)子結(jié)點(diǎn) ， 這時(shí)該子結(jié)點(diǎn)必為 red， 且子結(jié)點(diǎn)左右兒子為空 。 35 234樹(shù) ? 234樹(shù)及其實(shí)例 1. 234樹(shù)有三種不同的結(jié)點(diǎn)： 2結(jié)點(diǎn)、 3結(jié)點(diǎn)和 4結(jié)點(diǎn)。 ?3結(jié)點(diǎn)有兩個(gè)關(guān)鍵字域 key1和 key2，其中 key1key2，并增加一個(gè)指針域 p3。 2. 234樹(shù)的最主要的特征是其所有的葉結(jié)點(diǎn)都在同一深度。 234樹(shù)的搜索算法 ? 234樹(shù)的構(gòu)造過(guò)程 234樹(shù)的插入算法是保證樹(shù)的基本特征 （ 即所有葉結(jié)點(diǎn)在同一深度 ） 的關(guān)鍵 。 38 39 在插入算法中 ， 一旦產(chǎn)生了 4結(jié)點(diǎn)就要進(jìn)行分裂 ， 這時(shí)就會(huì)利用到父結(jié)點(diǎn)指針 p。 由定理 ， 234樹(shù)上的基本操作的代價(jià)在最壞情形下也是 O(logn)階的 。當(dāng)進(jìn)行下次插入或搜索操作時(shí)，每遇到一個(gè)4結(jié)點(diǎn)就進(jìn)行一次分裂，這樣可以減少一次插入操作的代價(jià)。 43 用上述變換將 234樹(shù)轉(zhuǎn)化為一個(gè)二叉搜索樹(shù) ， 不難發(fā)現(xiàn) ， 這是一棵 RB樹(shù) 。 的實(shí)例，其中 N=100，m=7， h(x)=xmod7。 = n/m 稱(chēng)為負(fù)載因子（ load factor） , 值是決定哈希算法性能的主要因素。 例如以姓名字符串作為關(guān)鍵字 ， |U|=N是一個(gè)極大的值 ，而 Hash表的長(zhǎng)度 m和實(shí)際關(guān)鍵字集合 S（ |S|=n） 與 N相比小得多 。 事實(shí)上 ， 無(wú)沖突的要求是極難達(dá)到的 。 因此 ， 在大多數(shù)情形下只能追求將沖突盡可能減少 。 因?yàn)檫@會(huì)使得 h(x)的取值只依賴(lài)于關(guān)鍵字的 2進(jìn)制值的最后幾位 ， 這不利于數(shù)據(jù)在 Hash表中的均勻分布 。 已有的研究指出取 最好 。 經(jīng)常采用的平方取中法的基本思想則是，首先計(jì)算關(guān)鍵字值的平方 x2，在平方值的二進(jìn)制序列中取中間的若干位， 例如： U=[0..999]， x=459， m=28， x2=4592=(210681)10=(110011011100000101)2 則 h(x)=(1101110000)2=880 由于在定義函數(shù) h(x)時(shí)，到底選取二進(jìn)制序列的哪些位帶有任意性，映射后的地址可能有較均勻的分布，使得沖突減少。這時(shí) Hash函數(shù)的自變量除了關(guān)鍵字 之外，還有一個(gè)查找序號(hào) i，最簡(jiǎn)單的映射方法稱(chēng)作線性查找 Hash函數(shù)： ， i=0,1,2,...。 采用線性開(kāi)地址方法 ， 函數(shù) h(x, i)把這 6個(gè)關(guān)鍵字依次插入到表中 。 。 為此可設(shè)計(jì)映射函數(shù)為： 其中取 m為一素?cái)?shù) ， m39。 ?由于影響問(wèn)題的因素有： Hash函數(shù)的選擇 、 沖突的處理策略 、關(guān)鍵字集合 S在全集 U中的分布情形和 Hash表的大小 ， 計(jì)算Hash函數(shù)的平均時(shí)間代價(jià)較難 ， 但最為重要 。 命題 在 uniform hashing的條件下 ， 對(duì)于開(kāi)地址 Hash表的成功搜索操作所需的期望查找 （ probes） 次數(shù)至多為 次 ， 其中 。 )1/(1 ?? 1m/n ????????1))1/(1l n (1 1m/n ???56 負(fù)載因子 的值對(duì)算法性能有影響 ， 在 接近于 1時(shí) ， 算法性能明顯降低 。