【正文】 后該結點將不滿足 B_樹的定義，此時若該結點的左（或右）兄弟結點中關鍵字個數 n大于 m/2+1， 則把該結點的左（或右）兄弟結點中最大（或最?。┑年P鍵字上移到雙親結點中，同時把雙親結點中大于（或小于）上移關鍵字的關鍵字下移到要刪除關鍵字的結點中，這樣刪去關鍵字后該結點以及它的左（或右）兄弟結點都仍舊滿足 B_樹的定義。 c 39。 b 110 116 132 189 200 (d)插入結點 195后結點分裂的過程 39。 （ 2） 判斷該結點是否還有空位置 ， 即判斷該結點是否滿足 nm1， 若該結點滿足 nm1， 說明該結點還有空位置 ， 直接把關鍵字；若該結點有 n=m1， 說明該結點已沒有空位置 ， 要插入就要分裂該結點 。 （ 2） 若 keyK1則沿著指針 P0所指的子樹繼續(xù)查找 。 B_樹中所有結點的孩子結點的最大值稱為 B_樹的階 ， 一棵 m階的 B_樹或者是一棵空樹，或者是滿足下列要求的 m叉樹： (1)樹中每個結點至多有 m個孩子結點。 在一般情況下，二叉排序樹的平均查找長度為 O(log2n)。 else printf(\n數據元素不存在 ！ )。root, test[i])。 BiTreeNode *root = NULL。 printf(%d , root)。 struct node *rightChild。 typedef struct { KeyType key。 (3)要刪除結點 只有右孩子結點 ， 刪除該結點且使被刪除結點的雙親結點指向被刪除結點的右孩子結點 。 return 1。 prightChild = NULL。 else current = currentleftChild。 current = *root。 else p = pleftChild。 381 12 410 9 40 394 540 35 190 146 476 760 445 600 800 下圖所示就是一棵二叉排序樹 二、二叉排序樹的查找算法 int Search(BiTreeNode *root, DataType item) { BiTreeNode *p。 二叉排序樹中結點的結構體定義如下： typedef struct node { DataType data。 相關術語 假設索引表的長度為 m， 主表中每個子表的長度為 s， 并假設在索引表上和在主表上均采用順序查找算法 ， 則索引順序表上查找算法的 平均查找長度 為： 122 12 1 ??????? smsmA S L算法分析 動態(tài)查找表 動態(tài)查找表主要有 二叉樹結構 和 樹結構 兩種類型。 完全索引表 :和主表項完全相同，但只包含索引關鍵字和該數據元素在主表中位置信息的索引表 二級索引表 :當主表中的數據元素個數非常龐大時，按照建立索引表的同樣方法對索引表再建立的索引表。 //查找失敗 } 算法分析 查找成功時的平均查找長度 ASL成功 為： 查找失敗時的平均查找長度 ASL失敗 為 nnnninCPA S Lnikiiii 221 11 lo g1)1(lo g112 ??????? ? ?? ??成功)1(lo g)1(lo g1 221 1????? ? ?? ?nnnCPA S Lniniii失敗 當順序表中的數據元素個數非常大時，采用 在順序表上建立索引表 的辦法提高查找速度。 //確定查找區(qū)間中心下標 if(a[mid].key == key) return mid。反之，如果 key大，則縮小至后半部內查找。 if(a[i].key == key) return i。 查找函數設計如下： int SeqSearch(DataType a[], int n, KeyType key) //在 a[0]a[n1]中順序查找關鍵碼為 key的數據元素 //查找成功時返回該元素的下標序號；失敗時返回 1 { int i = 0。 主關鍵字 :能夠惟一區(qū)分各個不同數據元素的關鍵字 次關鍵字 :通常不能惟一區(qū)分各個不同數據元素的關鍵字 查找成功 :在數據元素集合中找到了要查找的數據元素 查找不成功 :在數據元素集合中沒有找到要查找的數據元素 靜態(tài)查找 :只查找，不改變數據元素集合內的數據元素 動態(tài)查找 :既查找，又改變（增減）集合內的數據元素 靜態(tài)查找表 :靜態(tài)查找時構造的存儲結構 動態(tài)查找表 :動態(tài)查找時構造的存儲結構 平均查找長度 :查找過程所需進行的關鍵字比較次數的平均值 ,是衡量查找算法效率的最主要標準 ,其數學定義為： ?? ??niii CPA S L1其中， Pi是要查找數據元素出現的概率， Ci是查找相應數據元素的比較次數。也稱作 檢索 。 靜態(tài)查找表 靜態(tài)查找表主要有三種結構： 順序表 有序順序表 索引順序表 在順序表上查找的 基本思想是： 從順序表的一端開始，用給定數據元素的關鍵字逐個和順序表中各數據元素的關鍵字比較，若在順序表中查找到要查找的數據元素，則查找成功，函數返回該數據元素在順序表中的位置；否則查找失敗，函數返回 1。 a[i].key != key) i++。 一 、 順序查找 有序順序表上的順序查找算法和順序表上的查找算法方法類同 二、二分查找（ 又稱 折半查找） 算法的基本思想： 先給數據排序 （例如按升序排好），形成 有序表， 然后再將 key與 正中 元素相比，若 key小，則縮小至前半部內查找；再取其 中值 比較，每次縮小 1/2的范圍，直到查找成功或失敗為止。 while(low = high) { mid = (low + high)/2。 } return 1。 8 14 6 9 10 22 34 18 19 31 40 38 54 66 46 71 78 68 80 85 14 0 0 34 5 1 66 10 2 85 15 3 key link 下標 索引表 0 1 2 3 4