--- # System prepended metadata title: 資料結構 第十章 搜尋結構 tags: [資料結構] --- --- tags: 資料結構 --- ![](https://i.imgur.com/GHlVjVM.jpg) # 資料結構 第十章 搜尋結構 ## 一、最佳二元搜尋樹 ### (一)用意: 在資料相同下，不同的二搜尋元樹會有不同的形態，(1/(n+1))*C(2n,n)種，為了搜尋效益討論如何取出最佳的搜尋二元樹。 ### (二)圖示: 若以比較次數來判斷 a圖成本=((1*1)+(2*2)+(3*1)+(4*1))/5 = 2.4 b圖成本=((1*1)+(2*2)+(3*2))/5 = 2.2 b圖二元樹成本將優於a圖 ![](https://i.imgur.com/mvVQLzx.jpg) ### (三)加入外部節點討論 ![](https://i.imgur.com/HZMdQ80.jpg) #### 1、內部路徑長度(I) 以a圖為例: I = 0+1+1+2+3 = 7 (for+do+while+noid+if) #### 2、外部路徑長度(E) 以a圖為例: E = 2+2+4+4+3+2 =17 #### 3、E = I + 2n ### (四)名詞定義: #### 1、P~i~ = 成功搜尋二元樹機率 (root level為1) 成功搜尋節點的比較次數 level (成本=比較次數*機率) 成功搜尋節點的總成本 = 搜尋每個節點成本*機率的總和 ![](https://i.imgur.com/ZmphoGq.jpg) #### 2、Q~i~ = 搜尋失敗的機率 (root level為1) 失敗節點比較次數 level-1 (成本=比較次數*機率) 搜尋失敗的總成本= 每個失敗節點成本*機率的總和 ![](https://i.imgur.com/v9HI0OH.jpg) #### 3、二元搜尋樹總成本 失敗機率+成功機率=100% ![](https://i.imgur.com/O1iCRXv.jpg) 總成本=成功搜尋成本+失敗搜尋成本 ![](https://i.imgur.com/DEBClEc.jpg) #### 4、a~1~最小鍵值)故不需調整 ###### c、若q(p左子)為(2-node)若r(p右子)也為(2-node)則將p(2-node)qr合成(4-node) ###### d、同上若p(3-node or 4-node)則從p分點至q ###### e、若q(p左子)為(2-node)若r(p右子)為(3-node or 4-node)則以r節點鍵值補至樹根p，再由樹根補給q。 #### 2、圖示 ![](https://i.imgur.com/jsrT3dC.jpg) ## 五、紅黑樹 ### (一)定義 #### 1、為2-3-4樹的變形(轉換如下圖) 3-node(轉換不唯一) ![](https://i.imgur.com/QtRmn32.jpg) #### 2、紅黑樹性質(以節點為顏色) ##### (1)為二元搜尋樹 ##### (2)從樹根至外部節點具有相同數量的黑色節點 ##### (3)從樹根至外部節點沒有具2個或多個連續紅色節點 #### 3、圖示(以鏈結為顏色) 虛線-紅色 實線-黑色 ##### (1)為二元搜尋樹 ##### (2)外部節點rank為0 ##### (3)每個外部節點的父點(內部節點)rank為1 ##### (4)x的父點p的rank = rank(x)≦rank(p(x))≦rank(x)+1 ##### (5)x的祖父點gp的rank = rank(x) < rank(gp(x)). rank = 從外部節點至該點所需要的距離 同rank為紅色link ### (二)搜尋 搜尋方式與二元搜尋樹相等 ### (三)插入 使用二元搜尋樹方式插入紅色節點鍵值，若有連續2個紅點則做調整。 ### 1、調整 LLb,LLr、LRb,LRr、RRb,RRr、RLb,RLr 共有8種 (左點至父點分支 父點至x點分之 x父點的兄弟) #### (1)變色調整 LLr,LRr,RRr,RLr (變色) 祖點變紅，父點與父點兄弟改成黑色 ![](https://i.imgur.com/uaVrLA2.jpg) #### (2)旋轉調整 LLb,LRb,RRb,RLr (旋轉) 依大小旋轉後，父點更改為黑色，2個子點更改成紅色。 ![](https://i.imgur.com/Y30P50Q.jpg) #### (3)樹根為黑色 一路調整至樹根，若樹根為紅色節點則直接更改成黑色，則調整完畢。 >資料結構16-2(國立中山大學楊昌彪教授，有中文字幕) - Red-Black Trees > ### (四)刪除 紅色節點可以直接刪除 刪除為黑色節點則先旋轉or變色再刪除 ## 六、B樹 ### (一)m-way搜尋樹定義 空樹為m-分支搜尋樹，若不為空樹則m-分支搜尋數須滿足以下條件: (1)所有節點分支度　≦　ｍ　(最多有m個兒子) (2)一個節點最多可儲存m-1筆資料 (3)最左子點<第1鍵值<第二左子點<第2鍵值<...<第m-1鍵值<最右子點 (4)所有子樹皆為m-way搜尋樹 ### (二)定義 B樹為m-way搜尋數的一種，空樹亦是，若非空則滿足 (1)樹根至少需要2個子點 (2)除了樹根與失敗節點，其餘節點鍵值數量至少需要⌈m/2⌉-1，至少需要⌈m/2⌉個子點 (3) ### (三)插入 與2-3樹的規則一樣，插入後至節點鍵值已滿做分裂 ### (四)刪除 與2-3樹的規則一樣，刪除後節點鍵值須保持⌈m/2⌉-1個。 case1:若不足向左右兄弟節點借(Ex:左子鍵值給樹根，樹根鍵值補至不足的子點) case2:若不足左右兄弟節點也不足的情況下，則一邊做合併。 ## 七、斜張樹 雖然高度平衡樹最差O(logn)，則斜張樹則是平均分攤為O(logn)，每次運算完透過調整旋轉節點至樹根，來降低時間複雜度。 ### (一)調整的節點選擇 #### 1、成功搜尋的節點 #### 2、失敗搜尋最後比較的節點 #### 2、新插入的節點 #### 3、刪除節點的父點 ### (二)調整範例 ![](https://i.imgur.com/Zw2h7Nn.jpg) ![](https://i.imgur.com/cSP1H2N.jpg) ## 八、數字(數位;位元)搜尋樹 ### (一)位元樹搜尋 位元搜尋樹，每個節點都有一個鍵值，高度每增加一層(則由左至右每層固定一個bit討論)，往左為0往右為1。 ![](https://i.imgur.com/4An37xk.jpg) ![](https://i.imgur.com/dzhqdHZ.jpg) ![](https://i.imgur.com/DSLWsy4.jpg) >參考資料 https://opendatastructures.org/ods-cpp/13_1_digital_search_tree.html ### (二)binary trie(二元字典樹) 筆者自己翻譯(透過每次的True(1) or False(0) )來決定最後搜尋鍵值，結構類似二元樹及賀夫曼樹，透過分支搜勳到最後(葉節點or外部節點)得到鍵值。 ![](https://i.imgur.com/IvR6ms7.jpg) ### (三)Patricia (壓縮二元字典樹) 將無外部鍵值的節點省略已達到降低樹高 ![](https://i.imgur.com/F32Yuad.jpg) #### 1、Patricia圖形製作 (1)消除節點上的元素 (2)將資料儲存至分支上 (3)因壓縮每條路徑分支比節點數-1故選出一個頭節點(所有點都是頭節點的左子樹) ![](https://i.imgur.com/5prIO2x.jpg) #### 2、插入 ![](https://i.imgur.com/LqLHHAI.jpg) ## 九、字典樹 ### (一)定義圖示:(level 4) ![](https://i.imgur.com/Wgdqsl4.jpg) ### (二)搜尋: 如上圖搜尋字串，用字母向下搜尋至找到字串資料(像查字典一樣) 時間複雜度：O(字串所在level(高度)) ### (三)抽樣: 利用取部分來降低樹高level #### 1、從字尾部開始:(level 2) ![](https://i.imgur.com/PdFMgKF.jpg) #### 2、挑選皆不同的位元:(level 1) ![](https://i.imgur.com/vj6Jy5g.jpg) --- ![](https://i.imgur.com/WgpVgFp.jpg) --- ### (四)插入 ![](https://i.imgur.com/kIHEptp.jpg) ### (五)刪除 如上圖若要刪除"bobwhite"只要將第二個陣列索引 O 鏈結改成NULL即可 > 參考資料:Fundamentals of Data Structures in C by Ellis Horowitz, Sartaj Sahni, Susan Anderson-Freed