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

假设我想利用双数组构建一个这样的Trie树:
图片描述

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

那么在Base Array 中,各状态的Base 值是多少?

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

回复
阅读 3.8k
1 个回答
宣传栏