Trie（前缀树）和ternary trie和binary search tree

1 什么是trie

trie是一棵多叉树，假如存放的是由26个字母（不区分大小写）构成的字符串的话，那么就是一棵26叉树。

trie树是一棵前缀树，因为每个结点只保存字符串中的一个字符，整个字符串保存在路径中。

trie树的根结点里面不保存任何字符，因为根结点是下面所有路径的前缀，如果固定为一个字符的话，那么该trie树只能保存以该字符为前缀的字符串了。

trie树的每个结点要保存两类数据，一个是字符（root结点不保存），一个是到该字符所有后缀的结点的指针，比如26个字母的话，就是到该字符所有可能后缀的数组，一个保存26个指针的数组。

如果字符串不是很充分的话，trie树会浪费空间，因为会存在很多的null指针。

2 什么是binary search tree

和trie将key存放在树的路径中不同的是，binary search tree将key存放在每个结点中

binary search tree的左子树中所有的结点的值小于该结点的值，所有的右子树中的所有结点的值大于该结点的值。

所以，在binary search tree中查找时，每次比较之后，如果小于该结点的值的话，就往其左子树中继续找，如果大于该结点的值的话，就往其右子树中继续找。

因为涉及到一个平衡的问题，所以还有红黑树和avl树，它们都是自平衡的binary search tree。

3 什么是ternary trie

ternary trie是trie和binary search tree的杂交体。

ternary trie也是将key保存在路径中，但是和trie不同的是，key的整个字符串不是保存在连续的路径中。每个结点只保存一个前缀字符。

ternary trie的每个结点都保存三个指针，一个是字符等于该结点处保存的字符的子树的指针，一个是字符小于该结点处保存的字符的子树的指针，还有一个是字符大于该结点处保存的字符的子树的指针。

由于一个结点只保存一个前缀字符，所以，很可能该前缀字符并不是我们当前要找的字符，那么就要继续找子树，直到找到了当前字符为止，因此保存key字符串的路径可能不是连续的，是断开的。因此，ternary trie也不需要像trie那样root结点不能用。

4 怎样创建trie

见分析。

5 怎样创建binary search trie

见分析。

6 怎样创建ternary trie

见分析。

巴特西