随机化二叉搜索树（如treap）在高概率下可以提供良好的性能（O(log n)级别），同时避免了确定性平衡树（如AVL，红黑树，AA等）需要复杂（且昂贵）的再平衡操作。
我们知道，如果向简单的BST添加随机键，则可以期望它被合理地平衡。一个简单的原因是，n个节点的重度不平衡树的数量远低于“几乎平衡”的树的数量，因此，按键的随机顺序可能会得出一个可接受的树。
在这种情况下，Knuth在《计算机程序设计艺术》中给出的路径平均长度略大于1.3×lg2(n)，这相当不错。他还说，从随机树中删除随机键会保持其随机性（因此保持其良好平衡性）。
因此，在随机顺序插入和删除键的二叉搜索树最有可能为所有三个操作（搜索、插入和删除）提供O(log n)级别的性能。
也就是说，我想知道以下方法是否具有同样良好的性质：
- 使用已知为“优秀”的哈希函数h(x)（例如，它确保键均匀分布） - 使用h(x)对键进行排序，而不是按照 k 的顺序。 - 如果有冲突，则按键排序。如果哈希键足够好且哈希函数的范围比键集大得多，则这应该很少发生。
例如，按照 {4, 3, 5, 1, 2} 的顺序插入键的BST将为：
假设哈希函数将它们分别映射到{221, 142, 12, 380, 18}，那么我们就会得到。
关键点在于，“常规”的二叉搜索树可能会退化，因为插入键是根据与存储在树中的顺序关系相同的顺序进行的（例如它们的“自然”排序，例如字符串的字母顺序），但哈希函数会对键产生完全不相关的排序，因此应该产生与随机顺序插入键时相同的结果。
一个强烈的假设是哈希函数是“好的”，但我认为这并不是一个不合理的假设。
我没有在文献中找到类似方法的参考，因此它可能是完全错误的，但我看不出来为什么！
你是否看到我的推理有任何缺陷？有人已经尝试过吗？
我们知道，如果向简单的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)
关键点在于，“常规”的二叉搜索树可能会退化，因为插入键是根据与存储在树中的顺序关系相同的顺序进行的（例如它们的“自然”排序，例如字符串的字母顺序），但哈希函数会对键产生完全不相关的排序，因此应该产生与随机顺序插入键时相同的结果。
一个强烈的假设是哈希函数是“好的”，但我认为这并不是一个不合理的假设。
我没有在文献中找到类似方法的参考，因此它可能是完全错误的，但我看不出来为什么！
你是否看到我的推理有任何缺陷？有人已经尝试过吗？