什么时候使用treap

Question

任何人都可以提供真正的例子,说明何时存储数据的最佳方式是什么？

我想了解哪种情况下treap会比堆和树结构更好.

如果可能的话,请提供一些实际情况的例子.

我试图在这里搜索使用treaps的情况,并通过谷歌搜索,但没有找到任何东西.

谢谢.

Answer 1

如果将哈希值用作优先级,则treaps提供内容的唯一表示.

考虑实现为AVL树或rb树的项目的订单集.以不同顺序插入项目通常会以不同形状的树木结束(尽管所有这些都是平衡的).对于给定的内容,无论历史如何,treap总是具有相同的形状.

我已经看到了为什么唯一表示可能有用的两个原因:

1. 安全原因.treap不能包含历史信息.
2. 高效的子树共享.我见过的最快的集合操作算法使用了treaps.

Answer 2

我不能为你提供任何真实的例子.但我确实使用treaps来解决编程竞赛中的一些问题:

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

这些实际上并不是真正的问题,但它们是有道理的.

Answer 3

您可以将其用作基于树的地图实现。根据应用程序，它可能会更快。几年前，我自己（用 Java）实现了一个 Treap 和一个 Skip 列表只是为了好玩，并做了一些基本的基准测试，将它们与 TreeMap 进行比较，并且 Treap 是最快的。您可以在此处查看结果。

例如，与红黑树相比，它最大的优点之一是非常容易实现。但是，据我所知high，与红黑树相比，它的操作成本没有保证（搜索概率为 O(log n) ），这意味着您将无法使用它在需要特定时间限制的安全关键应用中。

Answer 4

Treaps是平衡二叉搜索树的绝佳变体.确实存在许多算法来平衡二叉树,但是大多数都是可怕的事情,需要处理大量的特殊情况.另一方面,对Treaps进行编码非常容易.通过使用随机性,我们有一个预计具有对数高度的BBT.使用treaps解决的一些好问题是 - http://www.spoj.com/problems/QMAX3VN/ (简易级别) http://www.spoj.com/problems/GSS6/ (中等级别)