Что быстрее на практике: Treap или Splay tree?

Question

Я выучил как Treap, так и Splay tree и решил несколько проблем, используя их.
Теоретически, их сложность в среднем равна O(log n), но в худшем случае сложность Treap равна O(n), а у Splay Tree амортизируется O(log n).

В каком случае наихудший случай возникает в Treap (поскольку его приоритеты выбираются случайным образом), и действительно ли Treap медленнее, чем Splay- дерево? Я решил некоторые задачи в SPOJ как с Splay- деревом, так и с Treap, и решения, использующие Treap, были немного быстрее (около 0,2 с), чем решения, использующие Splay- дерево. Так какой из них на самом деле быстрее, и какой я должен в основном использовать и когда?

Answer 1

На практике ни один из них действительно не используется. Они часто намного сложнее, чем необходимо. Они в основном интересны академически и для соревнований по программированию. Я действительно только сталкивался с красно-черными деревьями и B-деревьями в производственном коде, другие типы сбалансированных деревьев встречаются крайне редко.

Если вы обнаружите, что ловушки быстрее, то просто используйте их, так как производительность в худшем случае O(n) обусловлена ​​неудачей, а не состязательным вводом. Splay-деревья немного медленнее, потому что на практике приходится "платить" за амортизацию, чтобы получить наихудший случай до O(log n).