Trie
用字符或比特路径共享前缀的树;插入和查询 O(L),支持前缀统计和二进制 trie 上的异或最值。标签 数据结构 / Trie / 字符串
定义
Trie,也叫字典树或前缀树,是一棵有根树,用于存字符串或序列。每条边标一个字符;二进制 trie 的每条边只标 或 。
从根到一个节点的路径拼成该节点代表的前缀。根代表空串;节点上的终止标记表示某个完整的串在这里结束。具有相同前缀的串共享同一条路径。
核心性质
- 插入和查询一个长度为 的串,只需要沿路径走 步,时间 ,与已存储的串数无关。
- 空间与所有串的总长度成正比;每个节点需要保存子节点指针和终止信息。
- 一个节点的子树正好包含所有以该节点前缀开头的串,因此可以在节点上维护子树计数。
- 支持前缀查询、前缀计数和按字典序遍历;哈希表只能做精确查询,不能直接回答前缀问题。
- 删除时减少终止计数;节点计数变为 时可以回收,避免空间持续增长。
常见操作
- 插入:从根开始,对每个字符走向对应子节点,没有就新建;走完最后一个字符后,在终止位置增加计数。
- 精确查询:沿字符路径走;路径缺失则不存在,走完后检查终止计数是否大于 。
- 前缀查询:沿前缀走到对应节点;若路径存在,该节点子树中的所有终止串都以这个前缀开头。
- 删除:先确认存在,再沿路径减少计数;需要时回收空节点。
二进制 Trie
二进制 trie 把固定 位的整数看成 位比特串,从高位到低位插入。节点维护子树内的数字个数,删除时沿路径减少计数。
查询与 异或最小的数时,从高位到低位走:
- 若与当前位相同的子树非空,就走同侧,使这一位异或为 ;
- 否则走相反侧,这一位异或只能为 。
查询最大异或值时方向相反:优先走与当前位相反的子树。
因此插入、删除和一次异或查询都是 。这种结构常用于最大异或对、异或最小生成树等按位贪心的问题。
与哈希表的区别
- 哈希表擅长精确查询,平均时间与串长相关;Trie 的查询是固定的 。
- Trie 能直接处理前缀、字典序和子树统计;哈希表不能。
- Trie 的节点和指针可能占用较多空间,尤其是字符集大、串很长且前缀共享少时;压缩 trie 可以减少单链节点。
常见误解
- 认为 Trie 是二叉搜索树:Trie 按字符分支,不按整个键的大小排序。
- 认为 Trie 查询是 :查询代价是键长 ,与 无关。
- 认为只有叶子节点有信息:内部节点代表前缀,也可以存计数、终止标记等。
- 认为 Trie 一定省空间:前缀共享能省空间,但指针和稀疏分支也可能更费空间。
- 认为二进制 trie 求最小异或也优先走相反位:相反位用于最大异或;最小异或应优先走相同位。