树数据结构

Question

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

所以最坏情况下的复杂度是线性的。 有什么建议。

Answer 1

给出两件事：

• 您节点的优先级与您的数据无关（它是一个随机数）
• 您描述的最坏情况的概率是 2/(n!)（ascending/descending 个随机数）

因此可以考虑（摊销）Log(n) 运行时间（具有相同（最坏情况）数据的平均运行时间）。