Splay Trees Data Structures in 5 Minutes

Addendum: A special case where insertion takes constant time is when the elements that are inserted are already sorted. e. g. 1 2 3 4 5. When 2 is added, 2 is splayed, leaving its right child slot empty, and so 3 can easily take its spot and become the new root after being splayed. However, the tradeoff is that this tree will be extremely unbalanced. For a picture of the chalkboard, visit: