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

Question

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

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

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

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

Answer 1

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