前缀树/字典树的介绍及其简单应用

介绍

前缀树是什么呢，先看一段维基百科上对它的定义：

在计算机科学中，trie，又称前缀树或字典树，是一种有序树，用于保存关联数组，其中的键通常是字符串。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。一般情况下，不是所有的节点都有对应的值，只有叶子节点和部分内部节点所对应的键才有相关的值。

要理解它首先要知道我们用这个东西的目的是什么，我举一个最直观的例子，比如要查询某个单词，很多搜索框都有搜索提示。你想查询“Hello”这个单词，当你输入“Hel”甚至输入“H”时可能提示框就已经出现了“Hello”这个单词。前缀树最常用的应用就在这里，即通过某一前缀去查到该前缀底下对应的有什么单词。有的人可能会问“那我直接把所有单词存在一个数组或者List，遍历一遍不是也能查到吗！”，确实，但你不觉得这样在查找某个单词的时候其实花了很多时间访问到了很多无用数据吗，十分的浪费时间。使用前缀树可以将查找某个单词的时间复杂度降到 O(logn)。

简单来说，首先它是一棵树，其次树中的每个结点都是当前的前缀，这样便于我们用更少的时间去查找某个元素。我再画一张图加深一下理解，为了图的简洁，假设当前单词库里就三个单词，“hi”、“me”和“min”。