【正文】 class E, class K int dataListE, K::SeqSearch (const K x) const { Element[CurrentSize].key = x。 19 ? 設(shè)數(shù)據(jù)表中有 n 個元素，搜索第 i 個元素的概率為 pi，搜索到第 i 個元素所需比較次數(shù)為 ci，則搜索成功的平均搜索長度 : ? 在順序搜索并設(shè)置“監(jiān)視哨”情形： ci = i +1, i = 0, 1, ? , n1，因此 ?????????1010niiniiis u c c pcpA S L ) 1 ( .)(110??? ??ipA S Lniis u c c順序搜索的平均搜索長度 20 ? 一般表中各個元素的搜索概率不同，如果按搜索概率的高低排列表中的元素，從有序順序表的情況可知，能夠得到高的平均搜索長度。 //順序搜索失敗 , 返回失敗信息 } ? 有序順序表的順序搜索 ( 10, 20, 30, 40, 50, 60 ) 10 50 60 = = = = = = 20 30 40 ? ?27161 50??? ??is u c c iA S L? ?7276171 50?????????????iun s uc ciA S L基于有序順序表的折半搜索 ? 設(shè) n個對象 存放在一個有序順序表中 ， 并按其關(guān)鍵碼從小到大排好了序 。 //右縮搜索區(qū) else if ( Element[mid].key x ) high = mid 1。 //數(shù)據(jù)域 BSTNodeE, K *left, *right。 } //構(gòu)造函數(shù) BST(K value)。 //輸入停止標(biāo)志 BSTNodeE, K * //遞歸：搜索 Search (const K x, BSTNodeE, K *ptr)。 ? 假設(shè)想要在二叉搜索樹中搜索關(guān)鍵碼為 x 的元素，搜索過程從根結(jié)點開始。 if (x tempdata) temp = templeft。 exit(1)。 ? 為保證在刪除后樹的搜索性能不至于降低 ，還需要防止重新鏈接后樹的高度增加 。 if (ptrleft == NULL) ptr = ptrright?？赡艿亩嫠阉鳂淙缦滤?。則有 n 個內(nèi)部結(jié)點的擴(kuò)充二叉搜索樹的內(nèi)部路徑長度 I 至少等于序列 67 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, … 的前 n 項的和。 bf = 0。 } //刪除 friend istreamamp。 ptr)。 ? 如果這三個結(jié)點處于一條折線上，則采用雙旋轉(zhuǎn)進(jìn)行平衡化 。 subRleft = ptrright。 subRleft = ptrright。 if (ptrbf = 0) subRbf = 0。 說明插入前 pr的平衡因子是 0，插入新結(jié)點后，以 pr為根的子樹不需平衡化旋轉(zhuǎn)。 ? 必須沿結(jié)點 x 通向根的路徑反向追蹤高度的變化對路徑上各個結(jié)點的影響。 無需檢查上層結(jié)點的平衡因子。需要進(jìn)行平衡化旋轉(zhuǎn)來恢復(fù)平衡。 114 2. 如果 被刪結(jié)點 x 有兩個子女 : ─ 搜索 x 在中序次序下的 直接前驅(qū) y (同樣可以找直接后繼 )。插入新結(jié)點后 pr的平衡因子值有三種情況： 1. 結(jié)點 pr的平衡因子為 0。 104 AVLNodeE, K *subR = subLright。 subLright = ptrleft。為使樹恢復(fù)平衡，從 A沿插入路徑 右單旋轉(zhuǎn) (RotateRight ) 96 ? 插入路徑連續(xù)取 3 個結(jié)點 A、 B和 D，以結(jié)點 B為旋轉(zhuǎn)軸，將結(jié)點 A順時針旋轉(zhuǎn)。 92 ? 如果在某一結(jié)點發(fā)現(xiàn)高度不平衡，停止回溯。 bool Remove (AVLNodeE, K*amp。 //搜索 bool Insert (Eamp。 ? 如果一棵有 n 個結(jié)點的二叉搜索樹是高度平 87 衡的，其高度可保持在 O(log2n)，平均搜索長度也可保持在 O(log2n)。 ? 圖 (b)的情形所得的平均搜索長度最小。外結(jié)點表示失敗結(jié)點，內(nèi)結(jié)點表示搜索樹中已有的數(shù)據(jù)。 //到右子樹搜尋中序下第一個結(jié)點 while (templeft != NULL) temp = templeft。 //輸入數(shù)據(jù) while ( != RefValue) { //RefValue是一個輸入結(jié)束標(biāo)志 Insert (x, root)。 e1, BSTNodeE, K *amp。若找到，則函數(shù)返 //回該結(jié)點的地址，否則函數(shù)返回 NULL值。 //遞歸：刪除 }。 e1) //插入新元素 { return Insert(e1, root)。 } bool operator == (const Eamp。 ? 左子樹和右子樹也是二叉搜索樹。 } templateclass Type int orderedList Type:: BinarySearch ( const Type amp。 i CurrentSize。 cin Target。給出失敗信息。 }。 //在表中順序?qū)ふ? 12 if (i == CurrentSize) return false。 //數(shù)組最大長度和當(dāng)前長度 }。 Element[i1].key = x。 template class E, class K class dataList。 ? 搜索的結(jié)果通常有兩種可能： ?搜索成功 ，即找到滿足條件的數(shù)據(jù)對象。搜索算法根據(jù)給定值 k，在數(shù)組中進(jìn)行搜索。 } //求表的長度 virtual K getKey (int i) const { //提取第 i（ 1開始）元素值 9 assert (i 0 || i = CurrentSize)。 InList)。amp。 out endl。 15 ? 順序搜索主要用于在線性表中搜索。 cin L1。 //遞歸搜索 }。 if ( Element[mid].key x ) mid = BinarySearch ( x, mid +1, high )。 ? 假定每個結(jié)點的搜索概率相等，即 pi = 1/n，則搜索成功的平均搜索長度為 34 二叉搜索樹 ( Binary Search Tree ) ? 定義 二叉搜索樹或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹： ? 每個結(jié)點都有一個作為搜索依據(jù)的關(guān)鍵碼 (key)，所有結(jié)點的關(guān)鍵碼互不相同。 x) //重載：判小于 { return 。 } //輸出 E Min() { return Min(root)data。 ptr)。 else return ptr。 ? 如果搜索成功，說明樹中已經(jīng)有這個元素，不再插入； ? 如果搜索不成功，說明樹中原來沒有關(guān)鍵碼等于給定值的結(jié)點，把新元素加到搜索操作停止的地方。 root = NULL。 //在右子樹中執(zhí)行刪除 57 else if (ptrleft != NULL amp。 ? 如果輸入序列選得不好，會建立起一棵單支樹，使得二叉搜索樹的高度達(dá)到最大。 圖 (c): ASLsucc = 1/3*1+1/3*2+1/3*3 = 6/3, ASLunsucc = 1/4*1+1/4*2+1/4*3*2 = 9/4。 86 結(jié)點的平衡因子 bf (balance factor) ? 每個結(jié)點附加一個數(shù)字，給出該結(jié)點右子樹的高度減去左子樹的高度所得的高度差，這個數(shù)字即為結(jié)點的平衡因子 bf。 } //構(gòu)造函數(shù)：構(gòu)造非空 AVL樹 89 int Height() const。 90 bool Insert (AVLNodeE, K*amp。此時必須調(diào)整樹的結(jié)構(gòu)，使之平衡化。 ptrbf = subLbf = 0。 ptr) { AVLNodeE, K *subR = ptr。 先右后左雙旋轉(zhuǎn) (RotationRightLeft) 102 插入 h h h1 h1 A C E D B F G 1 0 0 右單旋轉(zhuǎn) A C E B F G D h h h h1 1 0 2 ? 再以結(jié)點 D為旋轉(zhuǎn)軸，將結(jié)點 A反時針旋轉(zhuǎn)， 恢復(fù)樹的平衡。 ? AVL樹的插入算法從一棵空樹開始，通過輸入一系列對象關(guān)鍵碼，逐步建立 AVL樹。 16 0 16 3 1 0 左右雙旋 7 3 16 0 0 0 7 3 11 0 1 1 16 右單旋 3 7 16 9 0 0 0 1 11 16 3 7 0 1 2 7 3 16 11 9 0 1 2 2 3 7 11 26 9 16 0 1 1 2 111 右左雙旋 0 左單旋 18 16 0 0 7 3 26 11 9 0 0 0 3 16 0 9 1 7 11 26 18 3 1 1 7 16 14 26 9 1 11 2 7 3 9 0 18 26 11 1 16 1 112 15 18 2 3 18 16 2 左右雙旋 7 3 0 0 0 11 7 14 9 1 16 15 0 1 11 26 26 14 1 2 9 從空樹開始的建樹過程 113 AVL樹的刪除 1. 如果 被刪結(jié)點 x最多只有一個子女 ， 可做簡單刪除 : ─ 將 結(jié)點 x從樹中刪去 。則 p 的 bf 改為 0，同時 shorter置為 True。 左單旋轉(zhuǎn) 0 h1 h1 p h q 0 1 h h1 h1 p h 1 q 120 c) 如果 p 與 q 的 bf 相反，則執(zhí)行一個雙旋轉(zhuǎn)來恢復(fù)平衡。 ? 布爾變量 shorter的值初始化為 True。 說明新結(jié)點在較高的子樹上插入，造成了不平衡，需要做平衡化旋轉(zhuǎn)。 ptrleft = subL。 else subRbf = 0。 }。為使樹恢復(fù)平衡，從 A沿插入路徑連續(xù)取 3個結(jié)點 A、 C和 E，以結(jié)點 C為旋轉(zhuǎn)軸，讓結(jié)點 A反時針旋轉(zhuǎn)。 //右單旋 void RotateLR (AVLNodeE, K*amp。 Tree)。 right = r。 (2) 不相等搜索概率的情形 69 do if to do if to q0= q1= p1= q2= p2= q3= p3= q0= q1= q2= q3= p1= p2= p3= (a) (b) 圖 (a): ASLsucc = *3+*2+*1 = ， ASLunsucc = *3+*3+*2+