127. Introducing the Splay Tree data structure
A Splay Tree is a flavor of Binary Search Tree (BST). Its particularity consists of the fact that it is a self-balancing tree that places the recently accessed items at the root level.
The splaying operation or splaying an item is a process that relies on tree rotations meant to bring the item to the root position. Every operation on the tree is followed by splaying.
So, the goal of splaying is to bring the most recently used item closer to the root. This means that subsequent operations on these items will be performed faster.
The splaying operation relies on six rotations:
- Zig rotation – the tree rotates to the right (every node rotates to the right)
- Zag rotation – the tree rotates to the left (every node rotates to the left)
- Zig-Zig rotation – double Zig rotation (every node moves twice to the right)
- Zag-Zag rotation – double Zag rotation (every node moves twice to...
