---
tags: 資料結構
---
# 資料結構 第十章 搜尋結構

## 一、最佳二元搜尋樹
### (一)用意:
在資料相同下，不同的二搜尋元樹會有不同的形態，(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圖

### (三)加入外部節點討論
#### 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 (成本=比較次數*機率)
成功搜尋節點的總成本 = 搜尋每個節點成本*機率的總和

#### 2、Q~i~ = 搜尋失敗的機率
(root level為1)
失敗節點比較次數 level-1 (成本=比較次數*機率)
搜尋失敗的總成本= 每個失敗節點成本*機率的總和

#### 3、二元搜尋樹總成本
失敗機率+成功機率=100%

總成本=成功搜尋成本+失敗搜尋成本

#### 4、a~1~<a~2~<...<a~n~ N個內部節點
#### 5、E~0~,E~1~,...,E~n~ N個外部節點
#### 6、T~ij~ =a~i+1~,a~i+2~,...,a~j~內部節點建立最佳二元搜尋樹
#### 7、T~0n~:最終的最佳二元搜尋樹
#### 8、T~ii~:為一個空樹(只有一個失敗節點)
#### 9、C~ij~:最佳二元搜尋樹的總成本
#### 10、R~ij~:T~ij~的樹根
#### 11、W~ij~:T~ij~的加權總合

### (五)C~ij~公視推導
#### 1、令a~k~為root那C~ij~ 等於 左子樹成本+右子樹成本+(左子樹權重+右子樹權重)，因為左右子樹成本若加上a~k~那所有點的level皆會增加1
#### 2、W~ij~=T~ij~的加權總合，C~ij~挑選完root分成左右子樹，從全部的組合中挑出成本最小的樹
### (六)推倒表格及畫圖
## 二、AVL樹
### (一)用途
月份插入的順序不同，會產生以下兩種極端的例子(高度最小及最大)，為了讓搜尋更有效，控制樹的高度平衡，才不會有斜曲樹出現。
### (二)定義
若為空樹則為高度平衡樹，若非空則左右子樹必須滿足
1、左右子樹皆為高度平衡樹
2、|左子樹高度-右子樹高度|≦ 1
### (三)平衡因子(balance factor)
若為高度平衡樹
左子樹高度-右子樹高度 只會= -1 ,0 ,1
### (四)調整(旋轉)
#### 1、當平衡因子達到+2 or -2 時，表示此樹不為高度平衡樹，故須調整成高度平衡，利用旋轉資料來調整樹的高度分別為LL、RR、LR、RL旋轉
#### 2、圖示:

每次插入時都保持為高度平衡樹，最後插入調整完結果
### (五)重新調整平衡圖示:
### (六)時間複雜度

## 三、2-3樹
每個內部節點都有 2-3 degree
(2-node表示degree為2的點)
(3-node表示degree為3的點)
### (一)定義
#### 1、說明
若為空樹為2-3樹，若不為空樹則須滿足
(1)每一個內部節點的degree為2或3
2-node節點內有一筆資料
3-node節點內有二筆資料
(2)若為2-node，那左子點的鍵值<中子點的鍵值
(3)若為3-node，那左子點的鍵值<中子點的鍵值<右子點的鍵值
(4)所有外部節點屬於同一個level
(5)root最少需要2個子點最多3個
#### 2、圖示
### (二)搜尋
從root搜尋比較鍵值1、鍵值2看大小決定前往左子點or中子點or右子點，與二元搜尋樹相似故時間複雜度為O(logn)
### (三)插入
#### 1、插入
以上圖插入70與30為例
##### (1)圖(a)
插入葉子後並無溢位
##### (2)圖(b)
插入葉子後產生(4-node)節點內有三筆資料，需做調整，調整則為將3筆資料大小位於中間鍵值向父點移動，其餘兩鍵值分別變成左右子點，若此時父點一樣溢位則再執行一次(如下圖再插入60)。

### (四)刪除
#### 1、刪除葉節點內的值
#### 2、若葉節點刪除後為空時
使用兄弟(找左子點最大or右子點最小來)替換root鍵值，再從root被替換的鍵值下放至葉子

## 四、2-3-4樹
2-3樹的進階
每個內部節點都有 2-4 degree
(2-node表示degree為2的點)
(3-node表示degree為3的點)
(4-node表示degree為4的點)
### (一)定義
#### 1、說明
若為空樹為2-3-4樹，若不為空樹則須滿足
(1)每一個內部節點的degree為2或3或4
2-node節點內有一筆資料
3-node節點內有二筆資料
4-node節點內有三筆資料
(2)若為2-node，那左子點的鍵值<樹根鍵值<中子點的鍵值
(3)若為3-node，那左子點的鍵值<樹根左鍵值<中子點的鍵值<樹根右鍵值<右子點的鍵值
(4)若為4-node，那左子點鍵值<樹根左鍵值<左中子點的鍵值<樹根中鍵值<右中子點的鍵值<樹根右鍵值<右子點的鍵值
(5)所有外部節點屬於同一個level
(6)root最少需要2個子點最多m個
#### 2、圖示
### (二)插入
搜尋由上到下若遇到4-node需要做調整至最後，插入至葉節點，插入後就不需要做調整，
#### 1、遇到4-node情形有3種情況
#### (1)4-node為2-3-4樹的root

#### (2)4-node的父點為2-node

#### (3)4-node的父點為3-node

### (三)刪除
#### 1、步驟
##### (1)定義
節點有 2-3-4 degree (鍵值1-2-3)
m = 分支度
樹葉分支度最小值 = ⌈m/2⌉ = 2
樹葉最少鍵值數量為 1
(degree 2 = 鍵值最少為1)
p為q之父點
##### (2)刪除考量的狀況
###### a、當p為葉子確保葉子鍵值至少為1(2-node、degree為2)，若p為為Root刪除後為空樹
###### b、q不是(2-node)刪除後q仍至少有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、圖示
## 五、紅黑樹
### (一)定義
#### 1、為2-3-4樹的變形(轉換如下圖)
3-node(轉換不唯一)
#### 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 (變色) 祖點變紅，父點與父點兄弟改成黑色

#### (2)旋轉調整
LLb,LRb,RRb,RLr (旋轉) 依大小旋轉後，父點更改為黑色，2個子點更改成紅色。

#### (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、刪除節點的父點

### (二)調整範例

## 八、數字(數位;位元)搜尋樹
### (一)位元樹搜尋
位元搜尋樹，每個節點都有一個鍵值，高度每增加一層(則由左至右每層固定一個bit討論)，往左為0往右為1。

>參考資料 https://opendatastructures.org/ods-cpp/13_1_digital_search_tree.html

### (二)binary trie(二元字典樹)
筆者自己翻譯(透過每次的True(1) or False(0) )來決定最後搜尋鍵值，結構類似二元樹及賀夫曼樹，透過分支搜勳到最後(葉節點or外部節點)得到鍵值。

### (三)Patricia (壓縮二元字典樹)
將無外部鍵值的節點省略已達到降低樹高

#### 1、Patricia圖形製作
(1)消除節點上的元素
(2)將資料儲存至分支上
(3)因壓縮每條路徑分支比節點數-1故選出一個頭節點(所有點都是頭節點的左子樹)
#### 2、插入

## 九、字典樹
### (一)定義圖示:(level 4)
### (二)搜尋:
如上圖搜尋字串，用字母向下搜尋至找到字串資料(像查字典一樣)
時間複雜度：O(字串所在level(高度))
### (三)抽樣:
利用取部分來降低樹高level
#### 1、從字尾部開始:(level 2)
#### 2、挑選皆不同的位元:(level 1)

---


---
### (四)插入
### (五)刪除
如上圖若要刪除"bobwhite"只要將第二個陣列索引 O 鏈結改成NULL即可

> 參考資料:Fundamentals of Data Structures in C by Ellis Horowitz, Sartaj Sahni, Susan Anderson-Freed