Why use Splay Trees?

Правка en1, от proofbycontradiction, 2018-11-28 12:52:13

In programming contests, I see that many of the codes that require an implementation of a balanced BST actually use a splay tree. Why do you use them over other trees that offer stronger guarantees such as AVL trees and Red Black?

For example, see this solution by tourist.

Are they that much faster than other trees (like quicksort or binary search trees)? Or do they have some interesting non-trivial properties that are especially useful? What I mean to ask is if there are questions where using a Splay Tree gives a much better result than using other kinds of trees.

Теги splay tree, i am stupid

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский proofbycontradiction 2018-11-28 12:52:13 675 Initial revision (published)