【正文】 ptrdata) Insert (e1, ptrright)。 //置空樹 cin x。 54 ?被刪結(jié)點左子樹為空 ， 可以拿它的右子女結(jié)點 頂替它的位置 ， 再釋放它 。 ptrright != NULL) { //ptr指示關(guān)鍵碼為 x的結(jié)點 ， 它有兩個子女 temp = ptrright。 return true。 ? 為此，在二叉搜索樹中加入外結(jié)點，形成判定樹。 ? 一棵判定樹上的搜索成功的平均搜索長度ASLsucc可以定義為該樹所有內(nèi)部結(jié)點上的搜索概率 p[i]與搜索該結(jié)點時所需的關(guān)鍵碼比較次數(shù) c[i] (= l[i], 即結(jié)點所在層次 ) 乘積之和： 64 ? 設(shè)各關(guān)鍵碼的搜索概率相等： p[i] = 1/n ? 搜索不成功的平均搜索長度 ASLunsucc為樹中所有外部結(jié)點上搜索概率 q[j]與到達(dá)外部結(jié)點所需關(guān)鍵碼比較次數(shù) c39。 (1) 相等搜索概率的情形 66 圖 (e): ASLsucc = 1/3*1+1/3*3+1/3*2 = 6/3, ASLunsucc = 1/4*1+1/4*3*2+1/4*2 = 9/4。 (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+ *1 = 。 ? 如果一個結(jié)點的平衡因子的絕對值大于 1，則這棵二叉搜索樹就失去了平衡，不再是 AVL樹。 right = r。 par) const。 Tree)。 e1)。 //右單旋 void RotateLR (AVLNodeE, K*amp。因此 , 在插入一 個新結(jié)點后，需要 從插入位置沿通向根的路徑回溯 ， 檢查各結(jié)點的平衡因子 。為使樹恢復(fù)平衡，從 A沿插入路徑連續(xù)取 3個結(jié)點 A、 C和 E，以結(jié)點 C為旋轉(zhuǎn)軸，讓結(jié)點 A反時針旋轉(zhuǎn)。 ? 在結(jié)點 A的左子女 的 左子樹 D上插入新結(jié)點使其高度增 1導(dǎo)致結(jié)點 A的平衡因子增到 2，造成不平衡。 }。 ptr = subLright。 else subRbf = 0。 ptr) { AVLNodeE, K *subL = ptr。 ptrleft = subL。 106 ? 設(shè)新結(jié)點 p的平衡因子為 0，其父結(jié)點為 pr。 說明新結(jié)點在較高的子樹上插入，造成了不平衡，需要做平衡化旋轉(zhuǎn)。 ─ 將原來以結(jié)點 x為根的子樹的高度減 1。 ? 布爾變量 shorter的值初始化為 True。 則在結(jié)點 p 發(fā)生不平衡。 左單旋轉(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ù)平衡。 左單旋轉(zhuǎn) 1 h h1 p h q 1 1 h h h1 p h 0 q 119 b) 如果 q 的 bf 與 p 的 bf 相同，則執(zhí)行一個單旋轉(zhuǎn)來恢復(fù)平衡，結(jié)點 p 和 q 的 bf 均改為 0，同時置 shorter為 True。則 p 的 bf 改為 0，同時 shorter置為 True。 115 ? 用一個布爾變量 shorter（縮短） 來指明子樹高度是否被縮短。 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從樹中刪去 。但該子樹高度 1 0 插入后 pr p 107 增加，還需從結(jié)點 pr向根方向回溯，繼續(xù)考查結(jié)點 pr雙親 (pr = Parent(pr))的平衡狀態(tài)。 ? AVL樹的插入算法從一棵空樹開始，通過輸入一系列對象關(guān)鍵碼，逐步建立 AVL樹。 else subRbf = 1。 先右后左雙旋轉(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ù)樹的平衡。 ptrright = subR。 ptr) { AVLNodeE, K *subR = ptr。 //轉(zhuǎn)移 ptr右邊負(fù)載 ptrright = subR。 ptrbf = subLbf = 0。 雙旋轉(zhuǎn)分為先左后右和先右后左兩類。此時必須調(diào)整樹的結(jié)構(gòu)，使之平衡化。 //左單旋 void RotateR (AVLNodeE, K*amp。 90 bool Insert (AVLNodeE, K*amp。 operator (istreamamp。 } //構(gòu)造函數(shù)：構(gòu)造非空 AVL樹 89 int Height() const。 } AVL樹的類定義 88 AVLNode (E d, AVLNodeE, K *l = NULL, AVLNodeE, K *r = NULL) { data = d。 86 結(jié)點的平衡因子 bf (balance factor) ? 每個結(jié)點附加一個數(shù)字，給出該結(jié)點右子樹的高度減去左子樹的高度所得的高度差，這個數(shù)字即為結(jié)點的平衡因子 bf。 ? 因此，最優(yōu)二叉搜索樹的搜索成功的平均搜索長度和搜索不成功的平均搜索長度分別為 : ? ?? ?.?????112l o g2nniu n s u c c iA S L? ?? ?.????nis u c c iA S L12 1l o g68 ? 設(shè)二叉搜索樹中所有內(nèi)、外部結(jié)點的搜索概率互不相等。 圖 (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。 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? 在判定樹中 ? ○ 表示 內(nèi)部結(jié)點 ， 包含了關(guān)鍵碼集合中的某一個關(guān)鍵碼； ? □ 表示 外部結(jié)點 ， 代表各關(guān)鍵碼間隔中的不在關(guān)鍵碼集合中的關(guān)鍵碼 。 ? 如果輸入序列選得不好，會建立起一棵單支樹，使得二叉搜索樹的高度達(dá)到最大。 else ptr = ptrleft。 //在右子樹中執(zhí)行刪除 57 else if (ptrleft != NULL amp。 ?刪除葉結(jié)點 ， 只需將其雙親結(jié)點指向它的指針清零 ， 再釋放它即可 。 root = NULL。 } return true。 ? 如果搜索成功，說明樹中已經(jīng)有這個元素，不再插入； ? 如果搜索不成功，說明樹中原來沒有關(guān)鍵碼等于給定值的結(jié)點，把新元素加到搜索操作停止的地方。 46 else temp = tempright。 else return ptr。 ? 如果 根指針為 NULL，則 搜索不成功 ；否則用給定值 x 與根結(jié)點的關(guān)鍵碼進(jìn)行比較： ?若 給定值等于根結(jié)點關(guān)鍵碼 ，則 搜索成功 ，返回搜索成功信息并報告搜索到結(jié)點地址。 ptr)。 void makeEmpty (BSTNodeE, K *amp。 } //輸出 E Min() { return Min(root)data。 //構(gòu)造函數(shù) ～ BST() {}。 x) //重載：判小于 { return 。 //左子女和右子女 37 BSTNode() { left = NULL。 ? 假定每個結(jié)點的搜索概率相等，即 pi = 1/n，則搜索成功的平均搜索長度為 34 二叉搜索樹 ( Binary Search Tree ) ? 定義 二叉搜索樹或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹： ? 每個結(jié)點都有一個作為搜索依據(jù)的關(guān)鍵碼 (key)，所有結(jié)點的關(guān)鍵碼互不相同。 //左縮搜索區(qū)間 else return mid。 if ( Element[mid].key x ) mid = BinarySearch ( x, mid +1, high )。 ? 折半搜索時 , 先求位于搜索區(qū)間正中的對象的下標(biāo)mid， 用其關(guān)鍵碼與給定值 x比較 : ? Element[mid].key == x， 搜索成功 ； ? Element[mid].key x， 把搜索區(qū)間縮小 到表的 前半部分 ， 繼續(xù)折半搜索 ； ? Element[mid].key x， 把搜索區(qū)間縮小 到表的 后半部分 ， 繼續(xù)折半搜索 。 //遞歸搜索 }。 ? 在等概率情形， pi = 1/n, i = 1, 2, ? , n。 cin L1。 int i = 0。 15 ? 順序搜索主要用于在線性表中搜索。 in 。 out endl。 }。amp。 return true。 InList)。 e1)。 } //求表的長度 virtual K getKey (int i) const { //提取第 i（ 1開始）元素值 9 assert (i 0 || i = CurrentSize)。 //關(guān)鍵碼域 E other。搜索算法根據(jù)給定值 k，在數(shù)組中進(jìn)行搜索。 ? 在每個對象中有若干屬性，其中有一個屬性，其值可唯一地標(biāo)識這個對象。 ? 搜索的結(jié)果通常有兩種可能： ?搜索成功 ，即找到滿足條件的數(shù)據(jù)對象。 但在實際應(yīng)用時，搜索條件是多方面的，可以使用基于屬性的搜索方法，但搜索結(jié)果可能不唯一。 template