【正文】 擴(kuò)充的二叉搜索樹稱作最優(yōu)二叉搜索樹。[j])乘積之和： ? 設(shè)外部結(jié)點(diǎn)搜索概率相等： q[j] = 1/(n+1)： .][???nis u c c i lnA S L11????nju n s u c c jljqA S L0).1][39。 ? 這樣的判定樹即為 擴(kuò)充的二叉搜索樹 。 }。 ptrdata = tempdata。 53 78 65 17 87 09 23 45 刪除 45 右子樹空 , 用左子女頂替 53 78 65 17 87 09 23 44 88 53 78 88 17 94 09 23 刪除 78 左子樹空 , 用右子女頂替 53 94 88 17 09 23 53 78 81 17 94 09 45 刪除 78 在右子樹上找中序下第一個(gè)結(jié)點(diǎn)填補(bǔ) 23 65 53 81 88 17 94 09 45 23 65 45 二叉搜索樹的刪除算法 template class E, class K bool BSTE, K::Remove (const K x, BstNodeE, K *amp。 cin x。 //x已在樹中 ,不再插入 }。 ptr) { //私有函數(shù)：在以 ptr為根的二叉搜索樹中插入值為 //e1的結(jié)點(diǎn)。 ? 搜索成功，搜索指針將停留在樹上某個(gè)結(jié)點(diǎn)；搜索不成功，搜索指針將走到樹上某個(gè)結(jié)點(diǎn)的空子樹。 if (ptr == NULL) return NULL。若找到，則函數(shù)返回該結(jié)點(diǎn)的 //地址，否則函數(shù)返回 NULL值。 ? 二叉搜索樹的類定義用二叉鏈表作為它的存儲(chǔ)表示，許多操作的實(shí)現(xiàn)與二叉樹類似。 30 BSTNodeE, K* Min (BSTNodeE, K* ptr)。} 29 bool Remove (const K x) { return Remove(x, root)。 R)。 x) //重載：判等于 { return == 。 right = R。 24 35 15 45 50 40 25 10 20 30 二叉搜索樹例 ? 結(jié)點(diǎn)左子樹上所有關(guān)鍵碼小于結(jié)點(diǎn)關(guān)鍵碼； ? 右子樹上所有關(guān)鍵碼大于結(jié)點(diǎn)關(guān)鍵碼； ? 注意：若從根結(jié)點(diǎn)到某個(gè)葉結(jié)點(diǎn)有一條路徑，路徑左邊的結(jié)點(diǎn)的關(guān)鍵碼不一定小于路徑上的結(jié)點(diǎn)的關(guān)鍵碼。參數(shù) loc 是在 //表中開始搜索位置 if (loc CurrentSize) return 0。 //搜索成功 else cout “ 沒(méi)有找到待查元素 \n”。 main () { 18 dataListint L1 (Size)。 ? 設(shè)在 數(shù)據(jù)表 dataList 中順序搜索關(guān)鍵碼與 給定值 x 相等的數(shù)據(jù)元素，要求數(shù)據(jù)元素在表中從下標(biāo) 0 開始存放 , 下標(biāo)為 CurrentSize 的元素作為控制搜索過(guò)程自動(dòng)結(jié)束的“監(jiān)視哨”使用。 in [i1]。 operator (istreamamp。 數(shù)據(jù)表類的友元函數(shù) 13 for (int i = 1。 //找到 ,保存被刪元素的值 Element[i] = Element[CurrentSize1]。 if (CurrentSize == 0) return false。 e1) { //在 dataList的尾部插入新元素 , 若插入失敗函數(shù)返 //回 false, 否則返回 true. 11 if (CurrentSize == ArraySize) return false。 //輸出 10 friend istreamamp。 //搜索 virtual bool Insert (Eamp。 R)。 //聲明其友元類為 dataList public: 7 dataNode (const K x) : key(x) { } //構(gòu)造函數(shù) K getKey() const { return key。 ? 靜態(tài)環(huán)境 ，搜索結(jié)構(gòu)在插入和刪除等操作的前后不發(fā)生改變。 ?搜索不成功 ，或搜索失敗。作為結(jié)果，應(yīng)報(bào)告一些信息 , 如失敗標(biāo)志、位置等。 ? 靜態(tài)搜索表 5 ? 動(dòng)態(tài)環(huán)境 ，為保持較高的搜索效率 , 搜索結(jié)構(gòu)在執(zhí)行插入和刪除等操作的前后將自動(dòng)進(jìn)行調(diào)整，結(jié)構(gòu)可能發(fā)生變化。 } //讀取關(guān)鍵碼 void setKey (K x) { key = x。 //復(fù)制構(gòu)造函數(shù) virtual ～ dataList() { delete []Element。 e1)。 operator (istreamamp。 Element[CurrentSize] = e1。 for (int i == 0。 //填補(bǔ) CurrentSize。 i = 。 in, dataListE, Kamp。 } return in。 ? 若搜索成功，則函數(shù)返回該元素在表中序號(hào) Location（比下標(biāo)大 1） , 若搜索失敗，則函數(shù)返回 CurrentSize+1。 //定義 int型搜索表 L1 int Target。 //搜索不成功 }。 //搜索失敗 else if (Element[loc1].key == x) return loc。 25 ? 如果對(duì)一棵二叉搜索樹進(jìn)行中序遍歷，可以按從小到大的順序，將各結(jié)點(diǎn)關(guān)鍵碼排列起來(lái)，所以也稱二叉搜索樹為二叉排序樹。} //構(gòu)造函數(shù) ～ BSTNode() {} //析構(gòu)函數(shù) void setData (E d) { data = d。 } }。 //重載：賦值 void makeEmpty() //置空 { makeEmpty (root)。} //刪除含 x的結(jié)點(diǎn) private: BSTNodeE, K *root。 //遞歸：求最小 BSTNodeE, K* Max (BSTNodeE, K* ptr)。 31 二叉搜索樹的搜索算法 ? 在二叉搜索樹上進(jìn)行搜索，是一個(gè) 從根結(jié)點(diǎn)開始 ， 沿某一個(gè)分支逐層向下 進(jìn)行比較判等的過(guò)程。 if (ptr == NULL) return NULL。 BSTNodeE, K* temp = ptr。 ? 設(shè)樹的高度為 h，最多比較次數(shù)不超過(guò) h。若在樹中已有含 e1的結(jié)點(diǎn)則不插入 if (ptr == NULL) { //新結(jié)點(diǎn)作為葉結(jié)點(diǎn)插入 ptr = new BstNodeE, K(e1)。 ? 注意參數(shù)表中引用型指針參數(shù) ptr的使用。 //插入，再輸入數(shù)據(jù) } }。 ptr) { //在以 ptr 為根的二叉搜索樹中刪除含 x 的結(jié)點(diǎn) BstNodeE, K *temp。 //用該結(jié)點(diǎn)數(shù)據(jù)代替根結(jié)點(diǎn)數(shù)據(jù) Remove (ptrdata, ptrright)。 ? 注意在刪除算法參數(shù)表引用型指針參數(shù)的使用。 50 ? 舉例說(shuō)明。 (*][?????nju n s u c c jl39。 ? 在 相等搜索概率 的情形下，所有內(nèi)部、外部結(jié)點(diǎn)的搜索概率都相等，視它們的權(quán)值都為 1。 do if to q0= q1= p1= q2= p2= q3= p3= (e) 圖 (e) : ASLsucc = *1+ *3+*2 = 。 AVLNode() { left = NULL。 template class E, class K class AVLTree : public BSTE, K { //平衡的二叉搜索樹 （ AVL） 類定義 public: AVLTree() { root = NULL。 } //插入 bool Remove (K x, Eamp。 out, const AVLTreeE, Kamp。 e1)。 ptr)。 ? 如果這三個(gè)結(jié)點(diǎn)處于一條直線上，則采用單旋轉(zhuǎn)進(jìn)行平衡化 。 ptr = subLright。 ptr) { B A C E D h h h1 h 2 1 1 h 插入 h h h1 h1 A B D C E 1 0 0 h h h1 B C E A D 1 0 0 86 先左后右雙旋轉(zhuǎn) (RotationLeftRight) //左子樹比右子樹高 , 旋轉(zhuǎn)后新根在 ptr AVLNodeE, K *subR = ptr。 88 ? 再以結(jié)點(diǎn) E為旋轉(zhuǎn)軸 ， 將結(jié)點(diǎn) A順時(shí)針旋轉(zhuǎn) 。 if (ptrbf = 0) subLbf = 0。 ? 在結(jié)點(diǎn) A的右子女的左子樹中插入新結(jié)點(diǎn)，該子樹高度增 1。 subRleft = ptrright。 ptrbf = 0。子樹的高度不變。 左單旋轉(zhuǎn) 插入后 2 q 1 pr p 0 pr 0 p pr=q 右左雙旋轉(zhuǎn) 插入后 2 q 1 pr p 0 pr 0 q pr=p 98 ? 若結(jié)點(diǎn) pr的 bf = 2，說(shuō)明左子樹高，結(jié)合其左子女 q 的 bf分別處理： ─ 若 q的 bf為 1，執(zhí)行右單旋轉(zhuǎn)； ─ 若 q的 bf為 1，執(zhí)行先左后右雙旋轉(zhuǎn)。 把結(jié)點(diǎn) y 當(dāng)作被刪結(jié)點(diǎn) x。 ? 當(dāng)前結(jié)點(diǎn) p 的 bf為 0。 ─ 旋轉(zhuǎn)的方向取決于是結(jié)點(diǎn) p 的哪一棵子樹被縮短。 0 h1 h1 h1 h1 0 0 p q r 右左雙旋轉(zhuǎn) 高度減 1 1 h h1 p 1 q h1 或 h2 h1 或 h2 h1 r 110 A B C D E F G H I J K L M N O P Q R S T 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 樹的初始狀態(tài) 舉例 111 刪除結(jié)點(diǎn) P 尋找結(jié)點(diǎn) P的中序直接前驅(qū) O, 用 O頂替 P, 刪除 O。 ? 有 n 個(gè)結(jié)點(diǎn)的 AVL樹的高度不超過(guò) *log2(n+2) ? 在 AVL樹刪除一個(gè)結(jié)點(diǎn)并做平衡化旋轉(zhuǎn)所需時(shí)間為 O(log2n)。 ? 伸展樹提出了一組改進(jìn)二叉搜索樹性能的一組規(guī)則，每當(dāng)執(zhí)行搜索、插入、刪除等操作時(shí)，就要依據(jù)這些規(guī)則調(diào)整二叉搜索樹，從而保證操作的時(shí)間代價(jià)。 120 2. 同構(gòu)形狀（ homogeneous configuration） 。 p g ? ? ? s ? p g ? ? ? s ? s g ? ? ? p ? 左單旋轉(zhuǎn) 右單旋轉(zhuǎn) 123 將剛訪問(wèn)的結(jié)點(diǎn) s上移到樹根部的算法 splaying (g, p, s) { //g 是 p 的父結(jié)點(diǎn)， p 是 s 的父結(jié)點(diǎn) //算法將 s移到根結(jié)點(diǎn)位置 while (s 不是樹的根結(jié)點(diǎn) ) if (s 的父結(jié)點(diǎn)是根結(jié)點(diǎn) ) 進(jìn)行單旋轉(zhuǎn) , 將 s 調(diào)整為根結(jié)點(diǎn) else if (s 與它的前驅(qū) p, g 是同構(gòu)形狀 ) 進(jìn)行一字形雙旋轉(zhuǎn)，將 s 上移 else //s 與它的前驅(qū) p, g 是異構(gòu)形狀 進(jìn)行之字形雙旋轉(zhuǎn)，將 s 上移 }。而 一字形旋轉(zhuǎn) 一般不會(huì)降低樹結(jié)構(gòu)的高度，它只是把剛訪問(wèn)的結(jié)點(diǎn)向根結(jié)點(diǎn)上移。或者結(jié)點(diǎn) s 是其父結(jié)點(diǎn) p 的右子女，結(jié)點(diǎn) p 又是其父結(jié)點(diǎn) g 的右子女 (＼ )。 119 ? 就像 AVL