Trie实现 - 将元素插入到trie中

Question

我正在开发一个Trie数据结构,其中每个节点代表一个单词.所以的话st,stack,stackoverflow并overflow会安排为

root
--st
---stack
-----stackoverflow
--overflow

我的Trie在HashTable内部使用,因此所有节点查找将花费恒定时间.以下是我将算法插入到trie中的算法.

1. 检查trie中的项目是否存在.如果存在,返回,否则转到步骤2.
2. 迭代中的每个字符key并检查单词是否存在.这样做直到我们得到一个节点,其中新值可以作为子节点添加.如果未找到任何节点,则将添加到根节点下.
3. 插入后,重新排列插入新节点的节点的兄弟节点.这将遍历所有兄弟节点并与新插入的节点进行比较.如果任何节点以与新节点相同的字符开头,则将从那里移动并添加为新节点的子节点.

我不确定这是实现trie的正确方法.欢迎任何建议或改进.

使用的语言:C++

Answer 1

这个特里应该是这样的

                      ROOT
             overflow/    \st
                    O      O
                            \ack
                             O
                              \overflow
                               O

通常,您不需要将哈希表用作trie的一部分; trie本身已经是一种有效的索引数据结构.当然你可以做到这一点.

但无论如何,你的步骤(2)实际上应该在搜索期间下降trie,而不仅仅是查询哈希函数.通过这种方式,您可以轻松找到插入点,而不需要在以后单独搜索它.

我相信步骤(3)是错误的,你不需要重新排列一个特里,事实上你不应该这样做,因为它只是你存储在特里的附加字符串片段; 见上图.