前缀树的设计与实现

🚀 优质资源分享 🚀

前缀树的设计与实现

作者：Grey

原文地址：

博客园：前缀树的设计与实现

CSDN：前缀树的设计与实现

前缀树即字典树，可以利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较。

我们使用搜索引擎的时候，输入 test，后面会自动显示一堆前缀是 test 的东西。这就利用了前缀树结构来实现。

比如我们有一堆字符串

["Trie","apple", "insert","apple", "search", "app","search", "startsWith", "insert", "search"]

问题1.查询字符串列表里面是否有以app，apx为前缀的字符串。

问题2.查询字符串列表里面有没有insert和serac这两个字符串。

我们可以把字符串列表构造成一棵前缀树，如下图

头节点是空串，路径表示字符，节点表示一个字符串的前缀（简称 p 节点），黑色节点表示一个字符串的结尾位置（简称 e 节点）。

有了如上结构，针对问题1，判断