【正文】 1 計算機算法 —— 設計與分析導論 南開大學 計算機科學與技術系 劉 璟 2 Chapter 4. 數據集合上的搜索(Searching)算法 ? 動態(tài)數據集 (Dynamic Set)與抽象數據類型 (ADT) ? 二叉搜索樹 (Binary Search Trees) ? 隨機二叉搜索樹 (Randomly Built Binary Search Tree) ? 紅黑樹 (RedBlack Tree) ? 234樹 ? Hashing技術 3 動態(tài)數據集 (Dynamic Set)與抽象數據類型 (ADT) 靜態(tài)數據集 （ Static Set）中的數據是固定不變的。 動態(tài)數據集 （ Dynamic Set）則是由不斷變動的同類型數據元素組成的數據集合。 動態(tài)數據集（ Dynamic Set）可以表示為一個數據元素的數組： class DynamicSet { int setSize。 Object[arraySize] elements。 ... } //Object為數據元素的類型， setSize為當前集合中的元素個數 4 用數組表示集合操作方便 ， 但當集合中的元素個數不斷增加時 ， 數組的長度必須擴大 。 一般采用空間倍增 （ array doubling） 技術 ， 即另外申請一個加倍長度的新數組 ， 把集合中的數據傳送過來 ， 取代原有的空間 。 其過程為： arrayDouble(set) { newSize = 2*arraySize 。 newElements = new Object(newSize) 。 Transfer all elements from the to the newElement。 = newElements 。 = newSize 。 } 更為靈活的存儲形式是利用指針和鏈表（例如線性鏈表和樹結構），這種存儲形式在搜索算法中經常用到。 5 搜索問題： 在集合中檢索出其關鍵字域的值等于給定值的數據元素 。 已知： 動態(tài)數據集類型 DynamicSet的一個實例 set和值 x。 求： 集合 set中一個元素 Object element， 使 = x。 數據集合上的操作 （ operation） 可以分為兩類： ?查詢 （ queries） 操作： 對數據集不做任何變動 ， 僅僅返回有關集合的某些信息； ?修改 （ modifying operations） 操作： 要對數據集合的某些域進行改動 。 一些典型的操作： ? Search(S,k)： 搜索，一個查詢操作。對于給定的數據集合 S和一個關鍵字值 k，返回 S中一個元素（ element）的指針 x，使得 xkey=k。當 S中沒有符合條件的元素時，返回的指針為空（ NULL）。 6 ? Insert(S,x)： 插入 ， 一個修改操作 。 把由 x指向的數據元素加入到集合 S中 ， 一般假定在 x指向的數據元中 ， 與集合運算相關的所有分量 （ 域 ） 都已經初始化 。 ? Delete(S,x)： 刪除，一個修改操作。給定指向集合 S中一個元素的指針 x，將此元素從 S中刪除。 ? Minimum(S)： 求最小元，一個查詢操作。若集合 S中所有數據元素的關鍵字值為一全序集，則返回具有最小關鍵字值的數據元素的指針。 ? Maximum(S)： 求最大元 ， 一個查詢操作 。 返回具有最大關鍵字值的數據元素的指針 。 ? Deletemin(S)： 刪除最小元 ， 一個修改操作 。 它相當于Minimum(S)和 Delete(S,x)的聯合 ， 即： Delete(S,Minimum(S))。 7 ? Successor(S,x)： 求后繼數據元 ， 一個查詢操作 。 若 S中的數據元素按關鍵字值從小到大排列 ， x是指向 S中某一數據元素的指針 ， 則返回 x所指向的數據元素的下一個數據元素的指針 。若 x指向最后一個數據元素 ， 則返回 NULL。 ? Predecessor(S,x)： 求前導數據元 ， 一個查詢操作 。 返回 x所指向的數據元素的前一個數據元素的指針 。 若 x指向第一個數據元素 ， 則返回 NULL。 搜索算法 （ 及相關操作算法 ） 的設計實際上是實現適合各種不同應用需要的 ADT， 例如： 字典（ Dictionary）作為抽象數據類型，可以分為兩類： 靜態(tài)字典：（靜態(tài)數據集 S， Search）； 動態(tài)字典：（動態(tài)數據集 S， Search， Insert， Delete）。 優(yōu)先隊列 （ Priority Queue）：（動態(tài)數據集 S， Insert，Deletemin）。 8 二叉搜索樹 二叉搜索樹又稱為二元字典樹，是一種最常用的動態(tài)數據集的數據結構，可以用于實現字典和優(yōu)先隊列等 ADT。 ? 二叉搜索樹（ Binary Search Trees） BST的一個結點與一個數據項相對應，除了數據項 Object或數據項的指針之外，結點主要由關鍵字 key域和指針域組成，即關鍵字 key與指針 left、 right和 p，三個指針分別指向該結點的左兒子、右兒子和父結點。 BST中結點的關鍵字值應滿足 BST性質： 即，設 x是二叉搜索樹的一個結點，結點 y位于結點 x的子樹中，x、 y的關鍵字值應滿足以下關系： 9 如果 y是 x的左子樹中的一個結點，則 ykey≤xkey； 如果 y是 x的右子樹中的一個結點，則 ykeyxkey。 6個結點（數據項）組成的兩個二叉搜索樹。兩個 BST(a)和 (b)有不同的樹高，前者比后者的查詢效率更高。 10 遍歷二叉搜索樹的所有結點可以采用中序遍歷 （ inorder tree walk） 算法 ， 即可將與二叉搜索樹樹結點相對應的數據項按關鍵字從小到大排列出來 。 中序遍歷 （ Inorder_Tree_Walk） 算法 ? 查詢（ Querying）的實現 對二叉搜索樹的查詢主要是 Search、 Minimum、 Maximum、Successor、 Predecessor等操作 ， 這些操作都可在 O(h)時間內完成 ， 其中 h是二叉樹的高 。 如 ， BST查詢操作為 Tree_Search(root,k)，即搜索 BST上關鍵字值為 k的結點。 Tree_Search算法 11 求最小元 （ 或最大元 ） 的操作只需從根開始沿著左指針 （ 或右指針 ） 一直搜索至某一結點 x， 其 left或 right指針為 NULL，這時結點 x的關鍵字 xkey為最小 （ 或最大 ） 。 求最小元的算法 Tree_Minimum(root) 求最大元的算法 Tree_Maximum(root) 求數據項的后繼與前導項的操作要相對復雜 ， 如 ， 結點 15（ 指關鍵字為 15的結點 )的后繼是結點 17， 它是結點 15的右子樹中的最小元 。 然而對于沒有右子樹的結點 ， 例如 1 4和 17， 其后繼分別為 1 6和 18， 顯然計算這三個結點的后繼時需要使用父結點指針 xp。 求后繼項的操作算法 Successor(x) 12 Successor(x)操作根據條件 xright!=NULL決定兩種情形：第一種情況從結點 x下行 ， 直到葉結點 ， 其路長顯然不超過樹高h；第二種情況從結點 x上行 ， 路長同樣不超過 h。 因此有下面的結論： 定理 動態(tài)數據集合的查詢操作 Search、 Minimum、Maximum、 Successor、 Predecessor可通過二叉搜索樹實現 ，其算法可在 O(h)時間內完成 ， 其中 h為二叉搜索樹的高 。 ? 插入與刪除操作 動態(tài)數據集上的 Insert(S,x)、 Delete(S,x)操作與查詢操作不同 ，它們會引起二叉搜索樹本身的變化 。 插入操作算法 Tree_Insert 13 14（ 關鍵字值為 14） 作為新結點插入到二叉搜索樹的過程 。 14 從二叉搜索樹中刪除一個結點的算法比較復雜 ， 假定待刪除結點指針 z不為 NULL， 有三種情形： （ 1） 結點 z沒有子結點，可直接刪除； （ 2） 結點 z只有一個子結點，可使 z的父結點 zp直接指向 z的子結點 zleft或 zright； （ 3） 結點 z有兩個子結點，則 z的后繼結點 y必然在 z的右子樹中，且 y無左子結點，按步驟（ 1）或（ 2）刪除結點 y，用 y的數據取代 z的數據。 過程如圖所示： 15 16 刪除操作算法 Tree_Delete 這個算法除了調用函數 Tree_Successor(root,z)的時間代價為O(h)外 ， 其余各處的時間代價均為 O(1)階 。 Tree_Insert(root,z)的運行是在從根到某一個葉結點的一條路徑上進行的 ， 因此有下面的結論 。 定理 動態(tài)數據集的 Insert(S,x)、 Delete(S,x)操作可通過二叉搜索樹實現 ， 其算法可在 O(h)時間內完成 ， 其中 h為二叉搜索樹的高 。 17 隨機二叉搜索樹 隨機二叉搜索樹（ Randomly Built Binary Search Tree）： 一個由 n個結點（具有 n個不同的關鍵字）按隨機順序，經過 n次 Tree_Insert操作插入到一個原始空樹而得到的二叉搜索樹，稱為隨機二叉搜索樹（ RBST）。這里的按隨機順序是指， n個不同關鍵字的 n!種不同排列的出現是等可能的。 定理 由 n個不同的關鍵字組成的隨機二叉搜索樹的平均樹高為 h=O(logn)。 該定理的證明基本思路與步驟： 1. 有關概率分布的假設： 假定關鍵字輸入序列 k1,k2,...,kn為 n個不同值的一種排列，設各種不同排序為等可能的，因此這一特定排序出現的可能性為1/n!。 18 假定：對任一 j值 （ 1≤j≤n） ， kj取 n個關鍵字其中任意一個的概率為 1/n， 也是等可能的 。 2. 在 RBST中結點 x為結點 y的祖先的充要條件： 首先分析從根到樹上任一結點 y（ ykey=kj,1j≤n）的路徑上的結點特征。分析的結果是，在這條路上的每個結點 x（ xkey= ki）都具有下列特征： 其對應的關鍵字 ki在輸入關鍵字序列中位于 kj之前，即 1≤ij≤n； k i值必為兩種情形之一： ① ki是 k1,k2,..., ki中大于 kj的若干值中的最小者； ② ki是 k1,k2,..., ki中小于 kj的若干值中的最大者。 上述情形是充分必要的，它可以敘述為： 命題 設二叉搜索樹 T是依次把不同關鍵字 k1,k2,...,kn插入到一個原始為空的二叉搜索樹而得到的結果，則結點 x（ xkey=ki）在 T中是結點 y（ ykey=kj）的祖先的充要條件是： }kka n dil1:km a x {kor}kka n dil1:km i n {k jllijlli ????????19 在 ， kj=17。 從圖 (a)中可以看到 ， 從根到結點 17的路徑上的 4個結點的關鍵字都符合上述條件 ， 而且 ， 從 (b)表中的關鍵字序列中可以看出 ， 關鍵字 17前面的 10個關鍵字中滿足命題 2 1 12全是結點 17的祖先 。 20 3. 求 RBST中任一結點的深度 d(kj,T)： 從命題 T中任一 （ 與關鍵字 kj對應的 ） 結點的深度 d(kj,T)恰恰等于滿足命題 （ 祖先 ） 結點的個數 ， 即： 命題 在上述的隨機二叉搜索樹 T中 ， 對于給定的關鍵字 kj (1≤j≤n)， 令 即 kl是所有的先于 ki輸入并大于 kj的值； 令 即 kl是所有的先于 ki輸入并小于 kj的值 。 則從根到 y（ ykey=kj） 的路徑上 ， 結點的關鍵字集合恰為Gj∪ Lj， 且 d(kj,T)=|Gj|+|Lj|。 }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 從 ， 對于 kj =17， Gj={21， 9}， Lj ={9。 12}， 所以 kj的深度為 4。 22 紅黑樹（ RedBlack Tree） ? RedBlack樹的性質 RedBlack(RB)樹是一種二叉搜索樹，它的每個結點有五個域：color