binary-search-tree - 数据结构

Question

据说 Treap 的高度按顺序是对数的。但是在按顺序对给定键(1,2),(1,3),(3,4),(4,5)执行在线插入时，treap 的高度是输入的顺序。

所以最坏情况的复杂性变成了线性的。有什么建议么。

Answer 1

给出了两件事：

• 您的节点的优先级与您的数据无关（它是一个随机数）
• 您描述的最坏情况的机会是 2/(n!) （随机数的升序/降序出现）

所以运行时间可以被认为是（摊销的）Log(n)（具有相同（最坏情况）数据的平均运行时间）。