随机二叉搜索树

Question

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

我们知道,如果我们将随机密钥添加到简单的BST中,我们可以预期它是合理平衡的.一个简单的原因是n个节点的非均衡树的数量远远低于"几乎平衡的"树的数量,因此,插入密钥的随机顺序很可能以可接受的树结束.

在这种情况下,在"计算机程序设计的艺术"中,Knuth给出了一点点多于1.3*lg2(n)作为相当好的路径的平均长度.他还说,从随机树中删除一个随机密钥可以保持其随机性(因此它具有良好的平均平衡).

那么,似乎二进制搜索树以随机顺序插入和删除密钥,很可能为所有三个操作提供O(log n)顺序的性能:搜索,插入和删除.

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

• 采用已知为"好"的散列函数h(x)(例如,它确保密钥的均匀扩展)
• 使用键上h(x)设置的顺序而不是k上的顺序.
• 如果发生碰撞,请按钥匙订购.如果散列键足够好并且散列函数的范围远大于键的集合,那么这应该是罕见的.

举例来说,按顺序插入的密钥{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)更有意义.