# 2017q3 Homework2 (prefix-search)
contributed by < `vasv75182366` >

###### tags: `sysprog2017`

> 動作太慢了，趕快跟上
> [name="jserv"][color=red]

## 簡介
在字串的集合內要收尋字串時，除了本次作業提到的 Ternary search tree(TST)，可以使用 Hash Table 、 Binary search tree(BST) 或者是 Trie tree 。
* Hash Table 隨著資料數量的大小需要調整 Hash Table size ，若是調整 Hash Table size 則整個表需要重建不利增長和收縮，並且根據 Hash function 的選擇和資料的不同 Hash collisions 的機會也會增加。
* BST (binary search tree) 雖然較穩定但效能太差。
* Trie tree 雖然查詢速度較快但是需要的空間較大，以英文字母查詢來說每個節點需要有26個節點指標，若是考慮中文甚至多國語言則不切實際。

本次作業的 TST 結合 Trie 以及 BST 的優點用較少的儲存空間達到快速查詢。

## 學習 Ternary search tree
### Ternary search tree

每個 Node 包含：
* 三個 Node 指標
* 一個字元
* 一個 Value

其中三個 Node 指標分別指向三個子樹：
* low (left)
* equal (middle)
* high (right)

typedef struct tst_node {
    char key;               /* char key for node (null for node with string) */
    unsigned refcnt;        /* refcnt tracks occurrence of word (for delete) */
    struct tst_node *lokid; /* ternary low child pointer */
    struct tst_node *eqkid; /* ternary equal child pointer */
    struct tst_node *hikid; /* ternary high child pointer */
} tst_node;

### 閱讀程式碼

---

## 修改程式碼

Reference
* [Igor Ostrovsky Blogging](http://igoro.com/archive/efficient-auto-complete-with-a-ternary-search-tree/)