---
tags: 研究所
---
# 2017q3 Homework2 (prefix-search)
contributed by < `twngbm` >

### Ternary search tree 介紹
* 三元搜尋樹是一種字典樹（trie），以下將講解何為字典樹。
#### Trie
* Trie 樹是一種利用字串特性來實現的資料結構，英文的每一個單字，有可能會有同樣的前綴，例如apple 和 append 的共同前綴就是 app ，我們可以利用此一特行，來節省儲存空間和加速搜尋時間，也因為此依特性 trie 特別適用於處理大量字串的資料結構時。
* 以下範例示範建構依 Trie 樹，並在樹中插入子節點
:::info
首先創造一根節點，根節點必為空
:::

@

:::info
我們試著插入單字and
1. 首先我們先把and拆分成 a, n ,d
2. 因為前綴a為第一次出現，因此我們在根節點底下創造一新子節點，節點值為a
3. 接下來從這個節點（a）出發，我們剩下 n, d
4. n也是第一次出現，因此我們在a節點下創造一新的n節點，d節點依此累推
:::

      @
     /
    a
   /
  n
 /
d

:::info
再來我們試著插入單字 at
1. 單字拆解成 a,t，從根節點出發
2. a節點以存在，因此不再創造新的節點
3. a節點以下t 節點不存在，因此創造一新的節點t
:::

      @
     /
    a
   / \
  n   t
 /
d

>中英文間請以空白隔開[name=課程助教][color=red]
:::info
以下示範插入and,at,be,bear，分別對應的value值為0，1，2，3
1. 當我執行 get(be) 時，會 return 2
2. 當我執行 get(bea) 時，會 return NULL，因為搜尋的末節點並不存在 value 值
3. 當我執行get(beat)時，也會return NULL，因為bea節點後並沒有t的節點位置
:::

      @
     / \
    a   b 
   / \   \
  n   t   e 2
 /    1    \
d           a
0            \
              r
              3

從以上的結構，我們可以發現以下幾點事情。
:::warning
1. 如果是針對英文單字的資料結構來做 trie 的話，這個trie 樹將會是一個26 叉樹，因為每一個節點會包含可能的26個英文單字。
2. 每個節點創造時，都必須同時創造26個值為NULL的子節點。
3. Trie 的優點為查詢且運作速度快，而且可以很輕易的做到前綴搜尋的動作，但是缺點就像上面所說的，其必須消耗大量的記憶體來儲存非常多的指標，每一個節點都必須建立26個指標，而且有些可能還是NULL。
:::
#### Ternary search tree
* 我們可以從上面的例子發現，當元素的數量越大，trie所需的記憶體空間就會急遽上升，光是英文大寫字母的trie，每一個節點就會需要26個pointer，如果加上小寫數字和常用符號，trie的結構會變得非常大而不切實際。

* 因此我們介紹一種簡化版的trie ，Ternary search tree(TST)，這種樹的每個節點最多只會有3個子節點，分別是小於，等於，大於。
* 以下範例示範ternary search tree

:::info
首先我們插入一值good，value=0，我們先拆分成g，o，o，d
基本概念跟trie一樣，但是這邊我們將 g 放入根節點
:::

g
|
o
|
o
|
d

:::info
接著我們嘗試插入單字got
1. 我們先比對g，發現根節點和got的第一個字母相同（g=g）
2. 因此pointer往下，來到o節點，發現o節點和got的第二個字母相同（o=o）
3. 因此pointer再往下，來到o節點，發現o節點和got的第三個字母不同，而且 **t>o**
4. 因此o節點 **右子樹** 成為t，到這邊我成功將got放入原本的TST中，如下圖
:::

g
|
o
|
o—
| |
d t

:::info
接著我們嘗試插入單字goal
1. 我們先比對g，發現根節點和goal的第一個字母相同（g=g）
2. 因此pointer往下，來到o節點，發現o節點和got的第二個字母相同（o=o）
3. 因此pointer再往下，來到o節點，發現o節點和goal的第三個字母不同，而且 **a<o**
4. 因此o節點 **左子樹** 成為a，到這邊我成功將goal放入原本的TST中，如下圖
:::

  g
  |
  o
  |
 —o—
| | |
a d t
|
t

:::info

| Key | Value |
| ------ | ------|
| sur | 0 |
| by | 4 |
| shore | 7 |
| the | 8 |
| she | 10 |
| sells | 11 |
| are | 12 |
| surely | 13 |
| sea | 14 |
| shells | 15 |

以下圖片示範TST
:::
資料來源：http://algs4.cs.princeton.edu/lectures/52Tries.pdf ,p24
我們可以從TST結構中，發現以下幾點事情
:::warning
1. 解決trie中，pointer大量佔用記憶體的情況，因為TST中，每個節點最多只會有3個child
2. 但是換取空間的同時，犧牲了些許時間，例如上途中尋找are的過程，a就必須經過兩次比較（a<s和a<b），但再trie中只需要一次比較
3. 在上面建構的過程中，我們可以發現字串的插入順序會影響TST的整體結構，假設我們第一個插入的字串為abandon，那麼我們可以預期的事，未來所有插入的字串都會在根節點的右子樹底下，如此一來對於查詢的時間成本會增加許多。
4. 對應上述問的的解決方法，我們可以先將預插入的數據做排序，從中間值開始插入，並不斷左右折半插入，如此依來我們就可以產生一個平衡的TST
:::

### 原始程式碼分析
* make完後，執行程式，不難發現d的用途是刪除某一子節點
* a的用途是新增一子節點

:::success
source code 的繁體中文翻譯為「原始程式碼」，有時會簡稱「源碼」(但不是「原」碼)

:notes: jserv

已修正
by :twngbm
:::
- 參考[tina0405](https://hackmd.io/JwDhDMAYHYGMBYC0sDMliPgNgIa0QEbgBMKiWkWF4KWArBQIxA==#)的修改方式
* 首先發現所有FIXME的地方，都是以CPY來傳入參數，但是我們希望以REF的方式去實作

- tst_ins_del(&root, &p, INS, CPY)
+ tst_ins_del(&root, &p, INS, REF)

改完後直接執行可以發現，S模式下，輸入的搜尋字串會一直重複。
進入函數tst_ins_del去觀察

 if (*p++ == 0) {
            const char *eqdata = strdup(*s);
            if (cpy) { /* allocate storage for 's' */
                if (!eqdata)
                    return NULL;
                curr->eqkid = (tst_node *) eqdata;
                return (void *) eqdata;
            } else { /* save pointer to 's' (allocated elsewhere) */
                curr->eqkid = (tst_node *) *s;
                return (void *) *s;
            }
        }

發現傳入的REF=0，會進入281行執行，但是傳入的*s是單一個空間，因此會產生同一個空間一直重複的問題。

#### MakeFile 修改與argc,argv的用法

#### 修改方法1-增加array
* 新增一新的二元array，來儲存所有產生的節點資訊
* 採用較小的dataset（3000筆）來實驗

char tree[9000][WRDMAX];
while ((rtn = fscanf(fp, "%s", count)) != EOF) {
        char *p = tree[count++];

傳入array後發現可以正確執行。

### Reference

* http://algs4.cs.princeton.edu/lectures/52Tries.pdf (搭配以下影片)
* https://www.youtube.com/watch?v=LelV-kkYMIg
* http://www.cnblogs.com/huangxincheng/archive/2012/11/25/2788268.html