【正文】 還要繼續(xù)檢查上層結(jié)點的平衡因子。 p 0 h h h1 p 1 h h1 刪除后不旋轉(zhuǎn) p 1 h h1 p 0 h1 h1 117 ? 結(jié)點 p 的 bf 不為 0，且較矮的子樹又被縮短。在每個結(jié)點上要做的操作取決于 shorter的值和結(jié)點的 bf，有時還要依賴子女的 bf。 ─ 因為結(jié)點 x最多有一個子女 ， 可以簡單地把 x的雙親中原來指向 x的指針改指到這個子女結(jié)點； ─ 如果結(jié)點 x沒有子女 ， x雙親原來指向 x的指針置為 NULL。 3. 結(jié)點 pr的平衡因子的絕對值 |bf| = 2。 ? 在插入新結(jié)點后，需從插入結(jié)點沿通向根的路徑向上回溯，如果發(fā)現(xiàn)有不平衡的結(jié)點，需從這個結(jié)點出發(fā)，使用平衡旋轉(zhuǎn)方法進行平衡化處理。 subLright = ptrleft。 103 A C E D B F G h h h1 h 0 0 1 h h h1 h 左單 旋轉(zhuǎn) A C E B F G D 0 2 2 template class E, class K void AVLTreeE, K:: RotateRL (AVLNodeE, K *amp。 if (ptrbf == 1) subRbf = 1。 AVLNodeE, K *subL = subRleft。 //ptr成為新根 ptrbf = subRbf = 0。 }。 93 右單旋轉(zhuǎn) 左單旋轉(zhuǎn) 左右雙旋轉(zhuǎn) 右左雙旋轉(zhuǎn) 左單旋轉(zhuǎn) (RotateLeft ) ? 在結(jié)點 A的右子女 的 右子樹 E中插入新結(jié)點，該子樹高度增 1導(dǎo)致結(jié)點 A的平衡因子變成 2，出現(xiàn)不平衡。 ? 平衡化旋轉(zhuǎn)有兩類： ? 單旋轉(zhuǎn) (左旋和右旋 ) ? 雙旋轉(zhuǎn) (左平衡和右平衡 ) ? 每插入一個新結(jié)點時 , AVL 樹中相關(guān)結(jié)點的平衡狀態(tài)會發(fā)生改變。 ptr)。 ptr, Eamp。 in, AVLTreeE, Kamp。 //高度 AVLNodeE, K* Search (K x, AVLNodeE, K *amp。 left = l。 ? AVL樹任一結(jié)點平衡因子只能取 1, 0, 1。 p[1] = , p[2] = , p[3] = q[0] = , q[1] = , q[2] = , q[3] = ? 分別計算各個可能的擴充二叉搜索樹的搜索性能，判斷哪些擴充二叉搜索樹的平均搜索長度最小。 圖 (d): ASLsucc = 1/3*2+1/3*3+1/3*1 = 6/3, ASLunsucc = 1/4*2+1/4*3*2+1/4*1 = 9/4。 ? 在每兩個外部結(jié)點間必存在一個內(nèi)部結(jié)點 。 ? 用樹的搜索效率來評價這些二叉搜索樹。 delete temp。amp。 ?被刪結(jié)點右子樹為空 ， 可以拿它的左子女結(jié)點頂替它的位置 ， 再釋放它 。 RefValue = value。 50 } else if (e1 ptrdata) Insert (e1, ptrleft)。 48 35 15 45 50 40 25 10 20 30 28 插入新結(jié)點 28 二叉搜索樹的插入 ? 每次結(jié)點的插入，都要從根結(jié)點出發(fā)搜索插入位置，然后把新結(jié)點作為葉結(jié)點插入。 } return NULL。 //搜索成功 }。 43 ? 若給定值小于根結(jié)點的關(guān)鍵碼 ， 則繼續(xù)遞歸搜索根結(jié)點的左子樹； ? 否則 。 //遞歸：插入 bool Remove (const K x, BSTNodeE, K*amp。 ptr)。 } //求最小 E Max() { return Max(root)data。 //析構(gòu)函數(shù) 39 bool Search (const K x) const //搜索 { return Search(x,root) != NULL。 } 38 bool operator (const Eamp。 right = NULL。 ? 左子樹（如果非空）上所有結(jié)點的關(guān)鍵碼都小于根結(jié)點的關(guān)鍵碼。 //搜索成功 } return 1。 else if ( Element[mid].key x ) mid = BinarySearch ( x, low, mid 1 )。 ? 如果搜索區(qū)間已縮小到一個對象 ， 仍未找到想要搜索的對象 ， 則搜索失敗 。 基于有序順序表的順序搜索算法 template class Type int searchListType :: Search ( const Typeamp。搜索成功的平均搜索程度為： ? 在搜索不成功情形， ASLunsucc = n+1。 cout L1。 //將 x設(shè)置為監(jiān)視哨 while (Element[i].key != x) i++。 ? 設(shè)若表中有 CurrentSize 個元素，則順序搜索從表的先端開始，順序用各元素的關(guān)鍵碼與給定值 x 進行比較 ? 若找到與其值相等的元素，則搜索成功，給出該元素在表中的位置。 //從 in輸入表的當(dāng)前長度 cout “輸入數(shù)組元素的值 : \n”。 //輸出表的所有表項到 out out “數(shù)組當(dāng)前長度 : ” endl。 template class E, class K ostreamamp。 Element[i] != x。 }。 //輸入 protected: dataNodeE, K *Element。 //刪除 friend ostreamamp。 return Element[i1].key。 //其他域（視問題而定） }。直到找到 k 在數(shù)組中的存放位置或可確定在數(shù)組中找不到 k 為止。稱為 關(guān)鍵碼 。1 第七章 搜索結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)電子教案 殷人昆 王 宏 2 ? 靜態(tài)搜索表 ? 二叉搜索樹 ? 最優(yōu)二叉搜索樹 ? AVL樹 ? 伸展樹 ? 紅黑樹 第七章 搜索結(jié)構(gòu) 3 搜索 (Search)的概念 靜態(tài)搜索表 ? 所謂 搜索 ，就是在數(shù)據(jù)集合中尋找滿足某種條件的數(shù)據(jù)對象。使用基于關(guān)鍵碼的搜索，搜索結(jié)果應(yīng)是唯一的。 靜態(tài)搜索表 6 數(shù)據(jù)表與搜索表的類定義 include include const int defaultSize = 100。 template class E, class K class dataList { //數(shù)據(jù)表類定義 public: 8 dataList (int sz = defaultSize) : ArraySize(sz), CuurentSize(0) { Element = new dataNodeE, K[sz]。 } virtual void setKey (K x, int i) { //修改第 i（ 1開始）元素值 assert (i 0 || i = CurrentSize)。 operator (ostreamamp。 //數(shù)據(jù)表存儲數(shù)組 int ArraySize, CurrentSize。 template class E, class K bool dataListE, K::Remove (K x, Eamp。 i++)。 operator (ostreamamp。 //輸出表的當(dāng)前長度到 out return out。 for (int i = 1。 ? 若整個表都已檢測完仍未找到關(guān)鍵碼與 x 相等的元素，則搜索失敗。 //從前向后順序搜索 return i+1。 //輸入 L1 cout “Search for a integer : ”。 .)()(1????????? nis u c cnnnninA S L 0 212111121 ? 采用遞歸方法搜索值為 x 的元素，每遞歸一層就向待查元素逼近一個位置，直到到達該元素。 x ) const { //順序搜索關(guān)鍵碼為 x的數(shù)據(jù)對象 for ( int i = 0。 搜索成功的例子 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 : public dataListType { //有序表的類定義 ,繼承了數(shù)據(jù)表 public: orderedList (int sz = 10) : dataListType (sz) { } ~orderedList ( ) { } int BinarySearch ( const Typeamp。 } return mid。 //搜索失敗 } 有序順序表的折半搜索的判定樹 ( 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 ? 搜索成功時檢測指針停留在樹中某個結(jié)點。 ? 右子樹（如果非空）上所有結(jié)點的關(guān)鍵碼都大于根結(jié)點的關(guān)鍵碼。 } //構(gòu)造函數(shù) BSTNode (const E d, BSTNodeE, K *L = NULL, BSTNodeE, K *R = NULL) { data = d。 x) //重載：判大于 { return 。 } BSTE, Kamp。 } //求最大 bool Insert (const Eamp。 //遞歸：置空 void PrintTree (BSTNodeE, K *ptr) const。 ptr)。 遞歸搜索根結(jié)點的右子樹 。 45 templateclass E, class K BSTNodeE, K* BSTE, K:: Search (const K x, BSTNodeE, K *ptr) { //非遞歸函數(shù)：作為對比，在當(dāng)前以 ptr為根的二 //叉搜索樹中搜索含 x的結(jié)點。 }。 49 二叉搜索樹的插入算法 template class E, class K bool BSTE, K::Insert (const Eamp。 //左子樹插入 else if (e1