4
像treap这样的随机二分搜索树以高概率提供了良好性能（按O（log n）的顺序），同时避免了确定性平衡树（如AVL）所需的复杂（且昂贵）的重新平衡操作， red-blackm，AA等随机二分搜索树
我们知道，如果我们向一个简单的BST添加随机密钥，我们可以期望它是相当均衡的。一个简单的原因是，对于n个节点而言，严重的非平衡树的数量远低于“几乎平衡”的树的数量，因此，插入密钥的随机顺序很可能以可接受的树结束。
在这种情况下，在“计算机编程的艺术”中，Knuth给出了一个比1.3 * lg2（n）多一点的平均长度，这个路径相当不错。他还说删除从随机树中随机密钥保留其随机性（因此它的良好平均平衡）。
因此，似乎在随机顺序中插入和删除密钥的二叉搜索树最有可能在所有三个操作（搜索，插入和删除）中按O（log n）的顺序执行性能。
这么说，我不知道下面的方法将给出相同的优良性能：
- 采取散列函数H（X），其被称为是“好”（例如，它确保甚至蔓延的键）
- 使用h（x）在键上设置的顺序而不是k上的顺序。
- 万一发生碰撞，按键重新排序。如果散列键足够好并且散列函数的范围比键集大得多，那么这应该是罕见的。
举个例子的密钥的BST {4，3，5，1，2}插入的顺序，将是：
4
/\
3 5
/\
1 2
假设散列函数将它们映射到（分别）{221,142,12,380,18）我们会得到。
221(4)
/ \
142(3) 380(1)
/ \
12(5) 18(2)
的关键点是“常规” BST可能退化，因为密钥是根据被用于将它们存储在树中（它们的“天然”排序相同次序关系插入，例如，按字母顺序但是哈希函数会导致与“自然”完全无关的密钥排序，因此应该给出与密钥以随机顺序插入相同的结果。
一个强有力的假设是哈希函数是“好”的，但它不是一个不合理的，我想。
我没有在文献中找到任何类似方法的参考，所以它可能是完全错误的，但我不明白为什么！
你看到我的推理有什么缺点吗？任何人都已经试图做到这一点？