什麼時候使用樹枝

Question

任何人都可以提供什麼時候存儲數據的最佳方式是treap的真實示例？

我想了解在哪些情況下treap會比堆和樹結構更好。

如果可能，請提供一些來自實際情況的示例。

我試過在這裏搜索使用treaps的例子，並用谷歌搜索，但沒有找到任何東西。

謝謝。

Answer 1

我無法爲您提供任何真實世界的例子。但我用treaps解決編程競賽的一些問題：

• http://poj.org/problem?id=2761
• http://poj.org/problem?id=3481

這些都不是真正真正問題，但它們是有意義的。

Answer 2

您可以將其用作基於樹的地圖實現。取決於應用程序，它可能是faster。幾年前，我自己（用Java）實現了Treap和Skip列表，只是爲了好玩，並且做了一些比較TreeMap的基本基準測試，而Treap是最快的。你可以看到結果here。

例如，與紅黑樹相比，其最大的優點之一是實施起來非常簡單。但是，據我所知，它的操作沒有保證的成本（搜索是O（log n），其概率爲high），與紅黑樹相比，這意味着你將無法將其用於需要特定時間限制的安全關鍵型應用中。

Answer 3

Treaps是平衡二叉搜索樹的很棒變體。確實存在許多用於平衡二叉樹的算法，但其中大多數算法都是可怕的，需要處理大量特殊情況。另一方面，對Treap進行編碼非常容易。通過使用隨機性，我們有一個預期爲對數高度的BBT。 一些很好的問題要解決使用treaps是 - http://www.spoj.com/problems/QMAX3VN/（簡易級） http://www.spoj.com/problems/GSS6/（中等水平）

Answer 4

如果哈希值作爲重點，treaps提供內容的唯一代表。

考慮作爲AVL樹或rb-tree實現的項目的順序集。以不同順序插入項目通常會以不同形狀的樹木結束（儘管它們都是平衡的）。對於一個給定的內容，無論歷史情況如何，它都將具有相同的形狀。

我見過兩個原因爲什麼唯一表示可能是有用的：

1. 安全原因。跳樹不能包含歷史信息。
2. 高效的子樹共享。用於設定操作的最快算法我見過使用treaps。