trie树

PinkieDeer · 2021-09-22 13:29:16 · 个人记录

trie树，也称字典树

前置知识

字符串（都会？）

快速搜索字符串

插入，删除，查询长度为 \tt len 的字符串都是 \tt O(len)

n次插入，最大长度len，有x个不同字符：\tt O(min(x \times len \times n, x^{len}))

插入字符串 \tt str。

我们从根开始，往下走，根的深度为 \tt 0，当前深度为 \tt i，我们看看当前节点有没有子节点 \tt str[i]（\tt str 的第 \tt i 个字符的编号），有，继续往下走，没有，那就增加一个，然后继续走。直到执行完 \tt str.size() 次

![]()

查询字符串str。

同理，我们从根开始，往下走，根的深度为 \tt 0，当前深度为 \tt i，我们看看当前节点有没有子节点 \tt str[i]（\tt str 的第 \tt i个字符的编号），有，继续往下走，没有，就是没有这个字符串了

![]()

删除字符串str。

同上，只是查找到后把只属于这个字符串的东西删了就行了。

![]()

我们可以发现这算法时间复杂度很好，但是空间太大了。

所以我们考虑用一下奇怪的优化

正常的话要储存基本的字符串我们要每个节点 \tt 128 个儿子，这样空间复杂度很大。

但是，我们可以考虑把一个字符拆分成 \tt 2 个一次插入，这样一个字符串长度就为 \tt 2 \times len，然后每个节点儿子个数就为 \tt 16 了

因为一般情况下都是 \tt 128 \times len \times n 比 \tt 128 ^ {len} 小

那原来空间为 \tt 128 \times len \times n，现在变为 \tt 16 \times 2 \times len \times n = 32 \times len \times n

减少了 \tt 4 倍！~~当然你也可以考虑拆成4份~~

\color{3498DB}{\texttt{P2580 于是他错误的点名开始了}}

\color{9D3DCF}{\texttt{P4551 最长异或路径}}

\color{black}\tt 点击此处快速前往Trie树题目