type
status
date
slug
summary
tags
category
icon
password
字典树简介
字典树 ( Trie 树 ) 又称单词查找树，
是一种用于在字符串集合中高效地存储和查找字符串的树形数据结构。
从根节点出发，到达某个指定的结点的路径可以构成一个字符串。
- 根节点不包含字符，除根节点外每一个节点都只包含一个字符。
- 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
- 每个节点的所有子节点包含的字符都不相同。
应用场景
维护一个字符串集合 ，支持两种操作：
向集合中插入一个字符串 xx；
询问一个字符串 xx及其作为前缀在集合中出现了多少次。
有时需要标记插入进 Trie 的是哪些字符串，每次插入完成时在这个字符串所代表的节点处打上记即可
01trie
简化版trie，树边不再是一个字符，而是0或1作为二进制的一个位，可以理解为：每一个数写成进制都是一个字符串，我们存数的时候把这个01字符串存下去，由高位到低位 = 由树根到叶节点。
ac代码
- Author:Grimner
- URL:https://tangly1024.com/article/example-21
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!