一道有趣的面试：Trie 树及其改进

0x00 导言

Trie 树是一种常见的数据结构，用以解决在给定单词在字典中是否存在的问题，而且支持动态的增删词典内容，常见的实现结构如下：

struct node{
    bool is_word ;
    struct node * [26];
};

对于任意词典，查找给定单词的效率为O(1)，比hash还要快。hash虽然也是O(1)，但是hash不能保证没有冲突，即使预先设计了一个良好的 hash 算法，动态修改词典内容也会导致冲突问题。

0x01 一种改进思路

但是 Trie 本身也有不足的地方：

1. 内存占用较多，每个节点都会开辟26个指针；
2. 另外Trie 是一颗前缀树，一颗 Trie 树通常会包含很多浪费的尾链，读者可以想象下垂柳的结构。

这里分享一种笔者曾经用过的改进方法