Why use Splay Trees?

Revision en1, by 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.

Tags splay tree, i am stupid

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English proofbycontradiction 2018-11-28 12:52:13 675 Initial revision (published)