Splay Tree: Implementation and Usage

By Shivam Chaturvedi• 5 min read
Last Updated: 2024-08-17

Splay Trees Blog

Introduction

A Splay Tree is a self-adjusting binary search tree where recently accessed elements are moved closer to the root. This property helps to improve access time for frequently accessed elements, balancing the tree dynamically without requiring explicit balancing operations like in AVL trees.

Splay Operation Code

#include <iostream>

using namespace std;

class Node {
public:
    int data;
    Node* left;
    Node* right;

    Node(int data) : data(data), left(nullptr), right(nullptr) {}
};

class SplayTree {
private:
    Node* root;

    Node* rightRotate(Node* y) {
        Node* x = y->left;
        y->left = x->right;
        x->right = y;
        return x;
    }

    Node* leftRotate(Node* x) {
        Node* y = x->right;
        x->right = y->left;
        y->left = x;
        return y;
    }

    Node* splay(Node* root, int key) {
        if (!root || root->data == key)
            return root;

        if (root->data > key) {
            if (!root->left) return root;
            if (root->left->data > key) {
                root->left->left = splay(root->left->left, key);
                root = rightRotate(root);
            } else if (root->left->data < key) {
                root->left->right = splay(root->left->right, key);
                if (root->left->right) root->left = leftRotate(root->left);
            }
            return (root->left == nullptr) ? root : rightRotate(root);
        } else {
            if (!root->right) return root;
            if (root->right->data < key) {
                root->right->right = splay(root->right->right, key);
                root = leftRotate(root);
            } else if (root->right->data > key) {
                root->right->left = splay(root->right->left, key);
                if (root->right->left) root->right = rightRotate(root->right);
            }
            return (root->right == nullptr) ? root : leftRotate(root);
        }
    }

public:
    SplayTree() : root(nullptr) {}

    void insert(int key) {
        if (!root) {
            root = new Node(key);
            return;
        }
        root = splay(root, key);
        if (root->data == key) return;

        Node* newNode = new Node(key);
        if (root->data > key) {
            newNode->right = root;
            newNode->left = root->left;
            root->left = nullptr;
        } else {
            newNode->left = root;
            newNode->right = root->right;
            root->right = nullptr;
        }
        root = newNode;
    }
};

Key Points

Splay Trees dynamically adjust based on access patterns.
They do not require explicit balancing, unlike AVL trees.
They can degrade to O(n) time complexity in the worst case, but this is generally acceptable in practice.
Useful in applications where access patterns are skewed.

Search Operation Example

#include <iostream>

using namespace std;

class SplayTree {
    // Previous implementation ...

public:
    // Previous methods ...

    void search(int key) {
        root = splay(root, key);
        if (root && root->data == key) {
            cout << key << " found in the tree." << endl;
        } else {
            cout << key << " not found in the tree." << endl;
        }
    }
};

Frequently Asked Questions

Q: How does a Splay Tree compare to an AVL Tree?
A: Splay Trees are less strict in balancing compared to AVL Trees, but they offer better amortized time complexity for access operations.
Q: Can Splay Trees be used for real-time applications?
A: Yes, Splay Trees are suitable for applications where access patterns are skewed and real-time performance is not critical.
Q: What are the common use cases for Splay Trees?
A: They are commonly used in systems where recent accesses are more likely to be accessed again, such as caches and memory management systems.