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可能退化，因爲密鑰是根據被用於將它們存儲在樹中（它們的「天然」排序相同次序關係插入，例如，按字母順序但是哈希函數會導致與「自然」完全無關的密鑰排序，因此應該給出與密鑰以隨機順序插入相同的結果。
一個強有力的假設是哈希函數是「好」的，但它不是一個不合理的，我想。
我沒有在文獻中找到任何類似方法的參考，所以它可能是完全錯誤的，但我不明白爲什麼！
你看到我的推理有什麼缺點嗎？任何人都已經試圖做到這一點？