【正文】 長度 ASLunsucc為樹中所有外部結點上搜索概率 q[j]與到達外部結點所需關鍵碼比較次數(shù) c39。 do if to do if to q0 q1 p1 q2 p2 q3 p3 q0 q1 q2 q3 p1 p2 p3 (a) (b) 62 判定樹 do if to q0 q1 p1 q2 p2 q3 p3 do if to q0 q1 p1 q2 p2 q3 p3 (d) (c) do if to q0 q1 p1 q2 p2 q3 p3 (e) 63 ].[*][ i lipA S Lnis u c c ???1? 在判定樹中 ? ○ 表示 內部結點 ， 包含了關鍵碼集合中的某一個關鍵碼； ? □ 表示 外部結點 ， 代表各關鍵碼間隔中的不在關鍵碼集合中的關鍵碼 。已知關鍵碼集合 {a1, a2, a3} = {do, if, to}，對應搜索概率 p1, p2, p3, 在各搜索不成功間隔內搜索概率分別為 q0, q1, q2, q3。 ? 這樣的判定樹即為 擴充的二叉搜索樹 。 ? 為此，在二叉搜索樹中加入外結點，形成判定樹。 ? 如果輸入序列選得不好，會建立起一棵單支樹，使得二叉搜索樹的高度達到最大。 59 二叉搜索樹性能分析 ? 對于有 n 個關鍵碼的集合，其關鍵碼有 n! 種不同排列，可構成不同二叉搜索樹有 (棵 ) C n nn 21 1? {2, 1, 3} {1, 2, 3} {1, 3, 2} {2, 3, 1} {3, 1, 2} {3, 2, 1} 1 2 3 1 1 1 1 3 2 2 2 3 3 2 3 60 ? 同樣 3 個數(shù)據(jù) { 1, 2, 3 }，輸入順序不同，建立起來的二叉搜索樹的形態(tài)也不同。 }。 return true。 else ptr = ptrleft。 } else { //ptr指示關鍵碼為 x的結點有一個子女 58 temp = ptr。 ptrdata = tempdata。 ptrright != NULL) { //ptr指示關鍵碼為 x的結點 ， 它有兩個子女 temp = ptrright。 //在右子樹中執(zhí)行刪除 57 else if (ptrleft != NULL amp。 if (ptr != NULL) { if (x ptrdata) Remove (x, ptrleft)。 53 78 65 17 87 09 23 45 刪除 45 右子樹空 , 用左子女頂替 53 78 65 17 87 09 23 55 88 53 78 88 17 94 09 23 刪除 78 左子樹空 , 用右子女頂替 53 94 88 17 09 23 53 78 81 17 94 09 45 刪除 78 在右子樹上找中序下第一個結點填補 23 65 53 81 88 17 94 09 45 23 65 56 二叉搜索樹的刪除算法 template class E, class K bool BSTE, K::Remove (const K x, BstNodeE, K *amp。 54 ?被刪結點左子樹為空 ， 可以拿它的右子女結點 頂替它的位置 ， 再釋放它 。 ?刪除葉結點 ， 只需將其雙親結點指向它的指針清零 ， 再釋放它即可 。 53 二叉搜索樹的刪除算法 ? 在二叉搜索樹中刪除一個結點時 ， 必須將因刪除結點而斷開的二叉鏈表重新鏈接起來 ，同時確保二叉搜索樹的性質不會失去 。 cin x。 //置空樹 cin x。 root = NULL。 ? 利用二叉搜索樹的插入算法，可以很方便地建立二叉搜索樹。 //x已在樹中 ,不再插入 }。 //左子樹插入 else if (e1 ptrdata) Insert (e1, ptrright)。 } return true。 //創(chuàng)建新結點 if (ptr == NULL) { cerr Out of space endl。 ptr) { //私有函數(shù)：在以 ptr為根的二叉搜索樹中插入值為 //e1的結點。 49 二叉搜索樹的插入算法 template class E, class K bool BSTE, K::Insert (const Eamp。 ? 如果搜索成功，說明樹中已經有這個元素，不再插入； ? 如果搜索不成功，說明樹中原來沒有關鍵碼等于給定值的結點，把新元素加到搜索操作停止的地方。 47 二叉搜索樹的插入算法 ? 為了向二叉搜索樹中插入一個新元素，必須先檢查這個元素是否在樹中已經存在 。 ? 搜索成功，搜索指針將停留在樹上某個結點；搜索不成功，搜索指針將走到樹上某個結點的空子樹。 }。 46 else temp = tempright。 while (temp != NULL) { if (x == tempdata) return temp。 if (ptr == NULL) return NULL。 45 templateclass E, class K BSTNodeE, K* BSTE, K:: Search (const K x, BSTNodeE, K *ptr) { //非遞歸函數(shù)：作為對比，在當前以 ptr為根的二 //叉搜索樹中搜索含 x的結點。 else return ptr。 else if (x ptrdata) return Search(x, ptrleft)。若找到，則函數(shù)返回該結點的 //地址，否則函數(shù)返回 NULL值。 遞歸搜索根結點的右子樹 。 ? 如果 根指針為 NULL，則 搜索不成功 ；否則用給定值 x 與根結點的關鍵碼進行比較： ?若 給定值等于根結點關鍵碼 ，則 搜索成功 ，返回搜索成功信息并報告搜索到結點地址。它可以是一個遞歸的過程。 ? 二叉搜索樹的類定義用二叉鏈表作為它的存儲表示，許多操作的實現(xiàn)與二叉樹類似。 ptr)。 ptr)。 //遞歸：求最大 bool Insert (const Eamp。 41 BSTNodeE, K* Min (BSTNodeE, K* ptr)。 //遞歸：置空 void PrintTree (BSTNodeE, K *ptr) const。 void makeEmpty (BSTNodeE, K *amp。 //根指針 K RefValue。} 40 bool Remove (const K x) { return Remove(x, root)。 } //求最大 bool Insert (const Eamp。 } //輸出 E Min() { return Min(root)data。 root = NULL。 R)。 } BSTE, Kamp。 //構造函數(shù) ～ BST() {}。 template class E, class K class BST { //二叉搜索樹類定義 public: BST() { root = NULL。 x) //重載：判等于 { return == 。 x) //重載：判大于 { return 。 x) //重載：判小于 { return 。 } //修改 E getData() { return data。 right = R。 } //構造函數(shù) BSTNode (const E d, BSTNodeE, K *L = NULL, BSTNodeE, K *R = NULL) { data = d。 //左子女和右子女 37 BSTNode() { left = NULL。 ? 二叉搜索樹的類定義 include include template class E, class K struct BSTNode { //二叉樹結點類 E data。 35 35 15 45 50 40 25 10 20 30 二叉搜索樹例 ? 結點左子樹上所有關鍵碼小于結點關鍵碼； ? 右子樹上所有關鍵碼大于結點關鍵碼； ? 注意：若從根結點到某個葉結點有一條路徑，路徑左邊的結點的關鍵碼不一定小于路徑上的結點的關鍵碼。 ? 右子樹（如果非空）上所有結點的關鍵碼都大于根結點的關鍵碼。 ? 假定每個結點的搜索概率相等，即 pi = 1/n，則搜索成功的平均搜索長度為 34 二叉搜索樹 ( Binary Search Tree ) ? 定義 二叉搜索樹或者是一棵空樹，或者是具有下列性質的二叉樹： ? 每個結點都有一個作為搜索依據(jù)的關鍵碼 (key)，所有結點的關鍵碼互不相同。 第 1層結點有 2個 , 搜索第 1層結點要比較 2次 。 35 15 45 50 25 10 20 30 搜索 22 搜索 45 折半搜索性能分析 ? 若設 n = 2h1，則描述折半搜索的判定樹是高度為 h1 的滿二叉樹。 //搜索失敗 } 有序順序表的折半搜索的判定樹 ( 10, 20, 30, 40, 50, 60 ) 10 50 = = = = = = 30 20 40 60 ASLunsucc = (2*1+3*6)/7 = 20/7 ASLsucc = (1+2*2+ 3*3)/6 = 14/6 ? 搜索成功時檢測指針停留在樹中某個結點。 //左縮搜索區(qū)間 else return mid。 if ( Element[mid].key x ) low = mid + 1。 x ) const { //折半搜索的迭代算法 int high = CurrentSize1, low = 0, mid。 } return mid。 if ( Element[mid].key x ) mid = BinarySearch ( x, mid +1, high )。 x, const int low, const int high ) const { //折半搜索的遞歸算法 int mid = 1。 }。 搜索成功的例子 1 0 1 3 4 6 8 10 12 6 0 1 2 3 4 5 6 7 8 搜索 low mid high 6 6 8 10 12 5 6 7 8 low mid high 6 6 5 low mid high 6 搜索失敗的例子 1 0 1 3 4 6 8 10 12 5 0 1 2 3 4 5 6 7 8 搜索 low mid high 5 6 8 10 12 5 6 7 8 low mid high 6 5 5 low mid high 5 template class Type class orderedList :