双数组实现Trie树冲突解决方法

问题描述

问 题

假设我想利用双数组构建一个这样的Trie树：

设定字符编码表：清-1，华-2，大-3，学-4，新-5，中-6，人-7

那么在Base Array 中，各状态的Base 值是多少？

转移公式是 base[s] + c = t, check[base[s]+c] = s ，基于上述编码和转移公式，按序构建清华、清华大学、清新、中华、华人五个词，最后发现华人这个词难以写入 Trie 树中，原因是华的位置已经被占用，往后找新的位置之后，就需要将根节点的base 值一并改写， 这样前面几个已经构建好的词就无法执行正确的状态转移了。这是否意味着：双数组 Trie 构词时必须按照一定的规则对词典进行建树？

解决方案

没有人回答，为此专门写了一篇文章：小白详解 Trie 树

这篇关于双数组实现Trie树冲突解决方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！