language-agnostic - 使用 HashMap 将二叉树插入优化为 O(1) 以写入重树

Question

首先，我假设我在考虑这个时错过了一些重要的东西，但我仍然想发布它，看看我是否真的没有错过任何东西，继续......

我有一个非常重的二叉树(写入和读取之间大约 50/50)，在今天回家的路上我正在考虑优化它的方法，特别是使写入更快 - 这就是我想出的。

考虑到将 x 添加到树 T 的操作 add(T, x) 首先包含 find(T, x) 以查看 x 是否已经存在，在这种情况下它不会返回父级，因此我们可以添加它而不是其中一位 parent 空着叶子。

如果我们添加一个哈希表作为添加操作的中间缓存，那么当我们调用 add(T, x) 时，真正发生的是 x 被哈希并插入到哈希映射 M 中。就是这样。当我们在其他地方要求 find(T, x) 时进行优化，现在当我们搜索树时，我们将找到一个叶节点，因为 x 尚未插入树(它仅存在于哈希映射 M 中) ，我们散列 x 并将其与 M 中的键进行比较，以查看它是否应该在树中。如果它在 M 中找到，那么我们将它添加到树中并从 M 中删除它。

这将消除 add(T, x) 上的 find(T, x) 操作并将其减少到 add(M, x) ，即 O(1)。然后 (ab)-使用我们第一次查找节点时执行的 find(T, x) 操作来插入它。

Answer 1

为什么不对所有内容都使用哈希表并完全省略二叉树？

这完全取决于您最初使用二叉树的原因。如果你选择二叉树来增强共享，你会失去哈希表缓存，因为哈希表不是共享的。

缓存也不会让比较两个 map 变得更容易。

编辑:

如果利用树的特殊性的操作很少见(您提到利用 RB 树已排序的事实)，并且另一方面，如果您经常查找最近添加的键，或替换最近添加的键的值，用另一种结构实现的小尺寸缓存可能是有意义的。您还可以考虑使用哈希表表示，偶尔转换为树。

这个缓存层的额外复杂性可能意味着你在实践中没有任何时间，或者不足以偿还拥有这样的临时数据结构的技术债务。