Splay Tree

Introduction

• The splay tree was introduced by Daniel Sleator and Robert Tarjan in 1985.
• Splay trees perform a splay operation, which is a combination of rotations and reorganizations, to move the accessed element to the root. 

Definition

• A splay tree is a self-adjusting binary search tree data structure that provides efficient/optimized access to recently accessed elements along with insertion, and deletion operations. It automatically adjusts its structure during these operations to improve the performance of frequently accessed elements. 

Characteristics

• The key idea behind a splay tree is to bring the most recently accessed element to the root of the tree using a series of rotations called “plays.”
• When an element is accessed (searched, inserted, or deleted), a series of splay operations are performed to move the accessed element to the root. This splaying process involves a set of rotations that move the accessed element up the tree, adjusting the tree structure along the way. The rotations are performed based on the relative positions of the accessed element, its parent, and its grandparent.
• By repeatedly applying the splay operation, the most recently accessed elements tend to move closer to the root, resulting in improved access times for frequently accessed elements. However, it’s important to note that splaying doesn’t guarantee perfect balance in the tree, and in the worst case, the tree can become skewed and degrade to linear search time.
• Splay trees have an amortized time complexity of O(log n) for search, insertion, and deletion operations, where n is the number of elements in the tree. However, the worst-case time complexity can be O(n) if the tree becomes unbalanced.

Structure of Splay tree

• In a splay tree, the elements are stored in a binary search tree fashion, where each node has a key and two child nodes (left and right). The keys in the left subtree are less than the key of the current node, and the keys in the right subtree are greater than the key of the current node.
• There are three main types of splay operations: zig-zig, zig-zag, and zig. These operations are applied recursively until the desired element becomes the root. These three types of splay operations involve three main cases, depending on the relative positions of the nodes involved:
  1. Zig-Zig: If the accessed element, its parent, and its grandparent all have the same orientation (either left or right), two rotations are performed to bring the accessed element to the root.
  2. Zig-Zag: If the accessed element, its parent, and its grandparent have alternating orientations, a single rotation is performed to bring the accessed element to the root.
  3. Zig: If the accessed element has no grandparent or its parent is the root, a single rotation is performed to bring the accessed element to the root.
• During an insertion or deletion operation, the splay operation is performed on the element being inserted or deleted to bring it to the root. If the element is already present in the tree, it is splayed to the root to maintain the tree’s self-adjusting property.

Advantages

• The main idea behind a splay tree is to bring the most recently accessed element to the root of the tree. This way, subsequent accesses to the same or nearby elements can be performed faster since they will be closer to the root, reducing the overall access time.

Use/Application

• In practice, splay trees perform well and are widely used in various applications that require efficient dynamic search structures.