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

Question

我正在开发一个 Trie 数据结构，其中每个节点代表一个词。所以词 st, stack, stackoverflow 和 overflow 将被排列为

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

我的 Trie 在内部使用 HashTable，因此所有节点查找都将花费恒定时间。以下是我想出的将项目插入到 trie 中的算法。

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

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

使用语言:C++

Answer 1

trie 应该是这样的

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

通常您不需要将哈希表用作 trie 的一部分； trie 本身已经是一种高效的索引数据结构。当然可以。

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

我认为第 (3) 步是错误的，您不需要重新排列 trie，事实上您不应该这样做，因为它只是您需要的附加 字符串片段存储在 trie 中；见上图。