字典树 Trie

数据结构 · 把字符摊在边上的前缀树

什么是字典树

前面的树（BST）每个节点存一个值、靠比较大小找路；哈希表把整个键散列成一个桶号。字典树（Trie，又叫前缀树）换了个思路——字符在边上，从根到某个节点的一条路径，正好拼出一个字符串。一个词不是存在某一个节点里，而是摊成一条路径。

这里固定放了 6 个词 [cat, car, card, cup, do, dog]。注意 cat/car/card/cup 都共用开头的 c→a…（共享前缀），既省地方又快。查找一个词只看它有多长（O(L)，L 是词长），跟一共存了多少词无关。点「查找」「前缀」试试。

查找有三种结局：走着走着没有往下的边了 → 不存在；走到了、但这个节点不是单词结尾 → 「只是前缀、不算一个词」（比如 ca）；走到底且是结尾 → 这是一个词。「前缀 ≠ 单词」是字典树的关键——所以每个单词的结尾节点要特别标记（带深绿环的那些）。

它真正的看家本领是前缀查询：走到前缀节点，把下面整棵子树点亮，就是所有以它开头的词——这就是自动补全。哈希表把键打散、根本没有「前缀」这个概念，做不到这件事。这也正是字典树值得单独成为一种结构、而不是树或哈希表的「子类」的原因。

字典树在哪里用

和它对比着记：BST 是「值在节点、比较大小」，哈希表 是「整键散列、无前缀」，字典树 是「字符在边、前缀共享」——三者各擅其长。