type
status
date
slug
summary
tags
category
icon
password
简单结构如下图所示
以树的结构他的每一条从根到叶子节点的路径便是一个字符串了，这样便可以轻易发现将共同前缀的字符串就连在一起了
下图中就存着了[to,tea,ted,ten,a,inn]这些字符串，基于这些我们如果找共同前缀的字符串或者像是在拼写提示这样的功能就实现了。
Trie树（字典树或前缀树）是一种用于存储字符串的树形数据结构，具有以下优缺点：
优点：
- 快速查询：Trie树能在平均O(m)的时间复杂度内实现字符串的查找，其中m是字符串的长度。这对于大量字符串的前缀匹配尤为高效。
- 前缀共享：相同前缀的字符串只需存储一次，从而节省了存储空间。
- 自然排序：可以根据字母顺序从Trie树中获取所有字符串，便于处理有序输出。
- 支持通配符查询：能很容易地实现对特定模式匹配的查询，例如支持“*”或“?”等通配符。
缺点：
- 空间复杂度：在存储大量字符串时，Trie树可能消耗较多内存，尤其是在字符集较大（如Unicode）时，节点的数量和深度可能显著增加。
- 构建时间：构建Trie树需要O(n * m)的时间复杂度，其中n是字符串的数量，m是字符串的平均长度，可能在某些情况下变得较慢。
- 不适合短字符串：对于较短或数量少的字符串，Trie树的优势不明显，反而可能增加不必要的开销。
常见用途：
- 自动补全：广泛应用于搜索引擎和输入法中，以实现快速的字符串前缀匹配。
- 拼写检查：用于词典的存储和校验，快速检测单词的存在性。
- IP路由：在网络中，可以使用Trie树进行IP地址的查找和路由。
- 字符串集合的操作：支持快速地实现集合相关的操作，如并集、交集等。
简单来说trie应该是一种空间换时间的算法，内存消耗较多，当字符串规模大对时间敏感的情况下使用，主要用于对于字符串快速查询或者几类大量字符串操作一类的。
TRIE的简单实现
参照于文首附着的题目leetcode 208 ，来实现一个简单的trie树
主要要实现这三个功能
void insert(String word)向前缀树中插入字符串word。
boolean search(String word)如果字符串word在前缀树中，返回true（即，在检索之前已经插入）；否则，返回false。
boolean startsWith(String prefix)如果之前已经插入的字符串word的前缀之一为prefix，返回true；否则，返回false。
首先初始化的时候将根节点赋值为一个空对象
插入的时候从根节点往下递归查找，如果找的到就一直往下，如果没有就往上一个节点的chidren里添加上，最后在结束的那个节点上添加上一个isEnd，告诉后面search之类的时候，有一个完整的单词在这里完结了的。
查找方法便是从根节点往下便利，然后主要要查的字符串每一个字符遍历的时候已经在树中找不到了，便可以代表树中没有这个字符串，然后，如果一直找到了最后一个字符，且有这个isEnd标志的话，自然表示查找到了，没有该标志即这个字符串只是之前存过的一个字符串的子串。
最后startWith最简单了，跟上面search比较只需要把最后一个判断isEnd拿掉即可了，逻辑上同。
针对trie树这个数据结构的简单学习就此结束😀！
- Author:SAKURAAE
- URL:https://tangly1024.com/article/90b7596e-b514-4bcf-beef-1a029c91a2fb
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!