字典树 ( Trie 树 ) 详解 |
您所在的位置：网站首页 › 字典树数组实现数组转换 › 字典树 ( Trie 树 ) 详解 |
字典树 ( Trie 树 ) 详解
|
字典树 ( Trie 树 ) 详解
一、字典树 ( Trie 树 ) 简介
字典树 ( Trie 树 ) 又称单词查找树， 是一种用于在 字符串集合 中 高效地 存储 和 查找 字符串 的 树形 数据结构。 二、应用场景维护一个 字符串集合 ，并支持两种操作： 向集合中插入一个字符串 xx； 询问一个字符串 xx 在集合中出现了多少次。例如：有字符串集合 { “abc” , "acwing" , "hhhh"} 1. 插入字符串 “abc” ==> 集合 { “abc” , “abc” , "acwing" , "hhhh"} 2. 查询字符串 “abc” 出现的次数：2 次。 题源： 835. Trie字符串统计 - AcWing题库 三、Trie 树举例原字符串集合：{ abcde 、aced 、bcdf 、bcff } 插入字符串：aced 、cdaa 新字符串集合：{ abcde 、abde、aced 、bcdf 、bcff 、cdaa }
说明：图中 ※ 为 字符串结束的标记 。 若某结点上有标记 ※，则说明 从根结点 到该结点为止， 每个结点表示的字符 相连 组成的字符串存在于集合中。 相应的，对于 没有标记 的结点， 串联成的字符串只是原有字符串的 一部分 ，不属于 字符串集合。 四、操作原理解析：1. 插入 ( insert ) 操作 将字符串 逐个拆分 成 单个字符， 从第一个字符开始与 Trie 树的 根结点开始 的 子结点 比对， 若有结点具有 相同 的字符， 则以同样的方式对比 下一个字符 与该结点的 子结点 。 举例：在 图 1 中插入字符串 abde ( 拆分：a/b/d/e) 对于字符 a ，根结点 的 子结点 中有 a ，向后判断 下一个字符 b 与 结点 a 的 子结点； 对于字符 b ，a 结点的 子结点 中有 b ，向后判断下一个字符 d 与 结点 b 的子结点； 对于字符 d ，b 结点的子结点中 没有 d ， 因此要创建新结点 d，向后 判断下一个字符 e 与 结点 d 的 子结点； 对于字符 e ，d 结点的子结点中没有 e ，因此要创建新结点 e ( 从创建了一个新结点起，后面剩下的字符显然都要创建新的结点，但其 操作和之前的判断相同 ) 举例：在 图 2 中插入字符串 cdaa ( 拆分：c/d/a/a) 对于字符 c ，根结点的子结点中没有 c ，因此要创建新结点 c， 剩下的字符 daa 以相同的操作，逐个创建，以存储字符串。 注意：在插入完字符串之后，要给末尾的结点加上 结束标记。 2. 查询 ( query ) 操作 与插入操作的原理基本相同， 将需要查询的字符串 逐个拆分 成单个字符，逐个与 Trie 树中的结点比较， 直至发现 Trie 树中 不存在 的字符，或要查询的字符串的各个字符都 比较完成 。 对于发现 Trie 树中不存在的字符， 一旦发现，就能确定要查询的字符串不属于原集合。 举例：在图 3 中查询 acwing ， 能找到 a → c ，但 c 的子结点中没有 w ，则确定集合中不存在该字符串 ) 对于要查询的字符串的各个字符都比较完成，则存在两种情况： ① 要查询的字符的确属于集合； ② 要查询的字符是集合中某个字符串的前缀。 举例：在图 3 中查询 ac ，能找到 a → c ，字符串比较完成。 因为 ac 是原有字符串 aced 的一部分 ( 前缀 )。 此时就需要用到结点上的 字符串结束标记 了。 在 ac 的查询过程中，最后判断的结点落在了结点 c 上， 但该结点没有 字符串结束标记 ，因此可以判断 ac 不属于原集合。 举例：在图 3 中查询 aced ，最后判断的结点落在了结点 d 上， 该结点具有 字符串结束标记 ，因此可以判断 aced 属于原集合。 五、数组模拟实现 Trie 树 1. Trie 树的定义 int son[N][26]; // 存储每个结点的所有儿子结点 // 在题目中，字符串只包含 26 个小写字母 // 因此每个结点最多只会向外连 26 条边 ( 最多只有 26 个儿子结点 ) int cnt[N]; // count，记录以这个结点结尾的单词有多少个 // 它在本模板中作为 字符串结束标记 int idx; // 存储当前已经使用到的结点的下标 // 下标是 0 的结点，既是根节点，又是空结点 char str[N]; // 存储输入的字符串 ( 1 ) 对二维数组的理解：一维数组 array[x]，表示以 array 为名的数组， 其中有 x 个元素，对应下标 0/1/2/.../x-1 对于二维数组，例如上述的 son[N][26] ，表示以 son 为名的数组， 其中共有 N * 26 个元素。 对于第一个下标 0 ，有 son[0][0] son[0][1] son[0][2] … son[0][25] 共 26 个元素 对于第一个下标 1 ，有 son[1][0] son[1][1] son[1][2] … son[1][25] 共 26 个元素 ...... 因此可以把 son[N][26] 看成 由 N 个数组组成，每个数组有 26 个元素。 即 将 son[N] 看作数组名，而其下标 N ，可以作为数组的编号。 回到 Trie 树，我们将这 N 个数组看作 N 个 结点 。 下标是 0 的结点 son[0]，既是根节点 root ，又是空结点。 ( 2 ) 对二维数组中 26 的理解一个结点，它包含了 26 个元素，对应 26 个小写字母。 ( 0 - a / 1 - b / 2 - c / ... / 25 - z) 这些元素的初始值均为 0 ，表示该结点没有指向任何一个字母的边。 若值不等于零，则表示有指向对应字母的边。 当然，若值不等于零，也就能判断该字符串属于集合。 例如 图 3 中 son[0][0] (a) son[0][1] (b) son[0][2] (c) 的值均不为 0 说明从根结点 ( root ) son[0] 出发，有到 a b c 的边。 而这个值，就是指向的 结点的编号。 son[0][0] = x ，则指向的结点 a 为 son[x] 结点 a 指向结点 b —— son[x][1] = y ， c —— son[x][2] = z 则结点 b 为 son[y] ，结点 c 为 son[z] 2. 插入 ( insert ) 操作 void insert( char str[] ) { int p = 0; // 每次都从根结点出发 for( int i = 0; str[i]; i++ ) // c++ 字符串结尾是 \0，可用于遍历整个字符串 { int u = str[i] - 'a'; // 得到当前字母子结点编号 if( !son[p][u] ) son[p][u] = ++ idx; // 如果该子结点不存在，创建子结点 p = son[p][u]; // 进入该子结点 } // 上面的 for 循环结束，则要插入的字符串遍历结束 // 此时 p 对应的就是最后一个字符所在的结点 cnt[p] ++; // 在末尾的结点处增加 结束标记 ( 该字符串出现的次数的累加 ) }
说明：cnt[N] 作为字符串结束标记，其值默认初始值均为 0 若 cnt[p] == x != 0 则说明结点 p 具有结束标记。(其值 x 表示字符串的数量) 六、函数模板 #include using namespace std; const int N = 100010; int son[N][26]; // 存储每个结点的所有儿子结点 // 在题目中，字符串只包含 26 个小写字母 // 因此每个结点最多只会向外连 26 条边 ( 最多只有 26 个儿子结点 ) int cnt[N]; // count，记录以这个结点结尾的单词有多少个 // 它在本模板中作为 字符串结束标记 int idx; // 存储当前已经使用到的结点的下标 // 下标是 0 的结点，既是根节点，又是空结点 char str[N]; // 存储输入的字符串 void insert( char str[] ) { int p = 0; // 每次都从根结点出发 for( int i = 0; str[i]; i++ ) // c++ 字符串结尾是 \0，可用于遍历整个字符串 { int u = str[i] - 'a'; // 得到当前字母子结点编号 if( !son[p][u] ) son[p][u] = ++ idx; // 如果该子结点不存在，创建子结点 p = son[p][u]; // 进入该子结点 } // 上面的 for 循环结束，则要插入的字符串遍历结束 // 此时 p 对应的就是最后一个字符所在的结点 cnt[p] ++; // 在末尾的结点处增加 结束标记 ( 该字符串出现的次数的累加 ) } int query( char str[] ) // 返回该字符串出现过多少次 { int p = 0; // 每次都从根结点出发 for( int i = 0; str[i]; i++) // c++ 字符串结尾是 \0，可用于遍历整个字符串 { int u = str[i] - 'a'; // 得到当前字母子结点编号 if( !son[p][u] ) return 0; // 发现不存在的字符，则断定不存在该单词，return 0 p = son[p][u]; // 存在则进入该子结点 } // 上述 for 循环结束，查询的字符串遍历结束 return cnt[p]; // 返回以 p 结尾的单词数量 // 若该结点没有 结束标记 则会返回 0 } int main() { int n; scanf( "%d", &n ); while( n-- ) { char op[2]; // 用于输入一个字符， scanf( "%s%s", op, str ); if( op[0] == 'I' ) insert(str); else printf( "%d\n", query(str) ); // op[0] == 'Q' } return 0; }说明：代码中的 char op[2] 是一种输入单个字符的技巧 函数 scanf 对于 char 类型的单个字符，是可以输入 空格 、回车 等字符的。 在代码的 提交测试过程 中，我们不确定输入的字符之后是否会有空格， 而这类错误是我们无法解决的。 而用 scanf 读入字符串能忽略掉 空格 和 回车， 采用这种方式，此时的 op[0]便是所输入的字符。 七、补充 1. Trie 树 基本性质： 根节点不包含字符，除根节点外每一个节点都只包含一个字符； 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串； 每个节点的所有子节点包含的字符都不相同。 2. Trie 树的优缺点Trie 树是一种 以空间换时间 的数据结构。 优点：利用字符串的 公共前缀 来减少查询时间，最大限度地减少无谓的字符串比较。 公共前缀：例如字符串 abcdef 与 abcghi 有公共前缀 abc 。 缺点：其每一个字符都可能包含至多字符集大小数目的指针。 在本模板采用子结点默认包含 所有字符集 的连接方式， 对于少量的字符串存储来说，大量的结点的儿子是空闲的，造成了 空间的浪费 。 3. 何时使用 Trie 树当需要存储的字符串的字符种类有限 ( 较少 ) 时， 可以用 Trie 树来存储字符串。 例如：只包含小写字母 ( 26 个 )，或包含大小字母 ( 52 个 )， 或包含 0 / 1，或包含整数 八、参考资料y 总的课~~ 字典树_百度百科 (baidu.com) Trie（前缀树/字典树）及其应用 - bonelee - 博客园 (cnblogs.com) 九、( 无注释版 ) 函数模板 #include using namespace std; const int N = 100010; int son[N][26], idx, cnt[N]; char str[N]; void insert( char str[] ) { int p = 0; for( int i = 0; str[i]; i++ ) { int u = str[i] - 'a'; while( !son[p][u] ) son[p][u] = ++idx; p = son[p][u]; } cnt[p]++; } int query( char str[] ) { int p = 0; for( int i = 0; str[i]; i++ ) { int u = str[i] - 'a'; while( !son[p][u] ) return 0; p = son[p][u]; } return cnt[p]; } int main() { int n; scanf( "%d", &n ); while( n-- ) { char op[2]; scanf( "%s%s", op, str ); if( op[0] == 'I' ) insert( str ); else if( op[0] == 'Q' ) printf( "%d\n", query( str )); } return 0; }（接受批评指正，欢迎交流补充~~ XD） |
【本文地址】
今日新闻 |
推荐新闻 |