data-structures - 随机二叉搜索树

Question

像 treap 这样的随机二叉搜索树以高概率提供了良好的性能(以 O(log n) 的顺序)，同时避免了确定性平衡树(如 AVL、red-blackm、AA 等)所需的复杂(且昂贵)的重新平衡操作.

我们知道，如果我们向一个简单的 BST 添加随 secret 钥，我们可以预期它是合理的平衡。一个简单的原因是 n 个节点的严重非平衡树的数量远低于“几乎平衡”的树的数量，因此，插入 key 的随机顺序可能会以可接受的树结束。

在这种情况下，在“计算机编程的艺术”中，Knuth 给出了比 1.3*lg2(n) 多一点的路径的平均长度，这是相当不错的。他还说从随机树中删除随 secret 钥可以保留其随机性(因此具有良好的平均平衡性)。

那么，对于所有三个操作:搜索、插入和删除，以随机顺序插入和删除键的二叉搜索树似乎最有可能以 O(log n) 的顺序提供性能。

也就是说，我想知道以下方法是否会提供相同的良好属性:

采用已知为“好”的散列函数 h(x)(例如，它确保键的均匀分布)

使用 h(x) 在键上设置的顺序而不是 k 上的顺序。

发生碰撞时，按key排序。如果散列键足够好并且散列函数的范围比键集大得多，那么这种情况应该很少见。

举例说明按该顺序插入的键 { 4, 3, 5 , 1, 2} 的 BST 将是:

                  4
                 / \
                3   5
               /\
              1  2

假设散列函数将它们映射到(分别){221,142,12,380,18) 我们会得到。

                    221(4)
                   /   \
              142(3)  380(1)
             /    \
           12(5) 18(2)

关键是“常规”BST 可能会退化，因为键是根据用于将它们存储在树中的相同顺序关系插入的(它们的“自然”顺序，例如字符串的字母顺序)，但散列函数对与“自然”键完全无关的键进行排序，因此应该给出与以随机顺序插入键相同的结果。

一个强有力的假设是散列函数是“好”的，但我认为这不是不合理的。

我没有在文献中找到任何对类似方法的引用，所以它可能是完全错误的，但我不明白为什么!

你看我的推理有什么缺点吗？有人已经尝试过吗？

Answer 1

我认为您的建议是简单地使用哈希值进行排序，依赖于平衡树的哈希值的传播。这是有效的，它应该在实践中为您提供充分平衡的树，并具有良好的散列函数。

我们没有看到其他人使用这样的东西的原因，IMO，是如果你按哈希函数排序，你的数据结构不再排序。是的，它仍然按哈希函数排序，但是具有最小哈希函数的元素通常不是您需要搜索的元素，而像最小/最大/第 k 个元素这样的搜索通常很有用。由于数据结构将不再具有此属性，因此拥有一个使用哈希函数存储在数组中以获得 O(1) 性能而不是 O(log n) 的哈希表更有意义。