Splay Trees 🎯

Welcome to a deep dive into Splay Trees! In this lesson, we'll cover the fundamentals of Splay Trees, a self-balancing binary search tree, and understand why they are important for practical applications.

What are Splay Trees? 📝

Splay Trees are a type of self-balancing binary search tree, invented by Daniel Sleator and Robert Tarjan. They are designed to minimize the average time complexity of operations like search, insert, and delete, making them highly efficient in many real-world scenarios.

The Importance of Splay Trees 💡

Splay Trees offer several advantages over other data structures like AVL Trees and Red-Black Trees. For instance, Splay Trees do not require constant height maintenance, making them simpler to implement. Additionally, Splay Trees perform better in certain scenarios, such as when there are many frequent insertions, deletions, or searches in random order.

Splay Tree Operations 📝

Search Operation 🎯

The search operation finds the node with a specific key in the Splay Tree.
The time complexity of the search operation is O(log n) in the average case.

Insert Operation 🎯

The insert operation adds a new node with a specific key to the Splay Tree.
After inserting a new node, the Splay Tree rebalances itself to minimize the height of the tree, making the average time complexity of the insert operation O(log n) in the amortized sense.

Delete Operation 🎯

The delete operation removes a node with a specific key from the Splay Tree.
Similar to the insert operation, the Splay Tree rebalances itself after deleting a node to maintain a balanced tree, making the average time complexity of the delete operation O(log n) in the amortized sense.

Splay Tree Types 📝

There are four basic Splay Tree operations that rotate the tree to minimize its height:

Left Rotation (Zig Operation)
- When a node has two children on its right, it rotates left.
Right Rotation (Zag Operation)
- When a node has two children on its left, it rotates right.
Double Rotation
- A double rotation involves a sequence of left and right rotations or right and left rotations to rebalance the tree.
Splay Operation
- The splay operation performs a series of rotations to move the searched node to the root of the tree.

Practical Example 💡

Let's take a look at a simple example of a Splay Tree.

python

class Node:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.left = None
        self.right = None
        self.size = 1

    def get_size(self):
        return self.size

    def insert(self, key, value):
        if self.key is None:
            self.key = key
            self.value = value
            self.size = 1
        else:
            if self.key < key:
                if self.right is None:
                    self.right = Node(key, value)
                else:
                    self.right.splay(key, value)
            else:
                if self.left is None:
                    self.left = Node(key, value)
                else:
                    self.left.splay(key, value)

    # Splay Tree Operations are not shown here for brevity