# 2017q3 Homework2 (prefix-search)

contributed by < `BreezeDa` >

## trie
Ternary search tree (TST) 是 trie 的一種實現，所以這邊先記錄一下 trie

被稱作 radix tree 或 prefix tree，是一種 search tree，這種 tree，可用於字串搜尋。
主要是將字串中的每個字母最為 node 往下生長。

如圖 ( 來源 [Tries](http://algs4.cs.princeton.edu/lectures/52Tries.pdf) )

## Ternary search tree (TST)
樹的結構，每個 node 有三個 children，通常稱為 equal kid, lo kid and hi kid，也就是 middle child、lower child、higher child。

其建立方法，若字母小於該 node，便放到左子樹，相等便放到中子樹，大於則放到右子樹。

## Reference

[1] [Tries](http://algs4.cs.princeton.edu/lectures/52Tries.pdf)