Splay Trees in C++

Data Structures and Algorithms are an essential part of programming. Understanding the different data structures and algorithms, and how to use them, is essential to becoming an effective programmer. In this article, we will be discussing Splay Trees, a type of self-balancing tree data structure, and how to implement them in C++. We will discuss the structure of the tree, its time and space complexities, and provide some code examples.

What is a Splay Tree?

A Splay Tree is a self-balancing binary search tree. It was first introduced by Daniel Sleator and Robert Tarjan in 1985 and is an efficient data structure for fast retrieval, insertion, and deletion. Splay Trees use the splay operation, which is a modification of the standard binary tree operations. The splay operation reorganizes the tree so that the recently accessed elements are faster to access again.

Splay Trees are a type of self-balancing tree, which means they keep the tree balanced after each operation. This helps to ensure the tree remains balanced and efficient.

How Does the Tree Structure Work?

A Splay Tree is a binary search tree, which means that each node in the tree has a left and right child. The root node of the tree is the entry point. Each node in the tree holds a data value. The tree is structured such that the left child of a node contains a data value that is smaller than or equal to the parent node, and the right child of a node contains a data value that is larger than or equal to the parent node.

The splay operation works by reorganizing the tree after each operation. When an element is accessed, the tree is modified such that the recently accessed element becomes the root of the tree. This makes it easier to access again.

Time Complexity

Splay Trees have an average time complexity of O(log n) for access, search, insertion, and deletion. This means that the time to complete an operation is proportional to the logarithm of the number of elements in the tree.

The worst-case time complexity of Splay Trees is also O(log n). This means that even in the worst case, the time to complete an operation is proportional to the logarithm of the number of elements in the tree.

Space Complexity

The space complexity of Splay Trees is O(n). This means that the amount of memory used by the tree is proportional to the number of elements in the tree.

Implementing Splay Trees in C++

Now that we have discussed the structure of Splay Trees and their time and space complexities, let’s look at how to implement them in C++.

First, we must define the structure of the Splay Tree node. This will store the data value and the pointers to the left and right child nodes.

struct Node {
    int data;
    Node *left;
    Node *right;
};

Next, we must define the structure of the Splay Tree. This will store the root node of the tree and the number of elements in the tree.

struct SplayTree {
    Node *root;
    int size;
};

Now, we must define the operations that can be performed on the Splay Tree. These operations include insertion, search, deletion, and splay.

Insertion

The insertion operation adds a new element to the Splay Tree. It takes the data value to be inserted and the root node of the tree as parameters.

// Function to insert a node in the Splay Tree
void insert(int data, Node *&root)
{
    // Create a new node
    Node *newNode = new Node;
    newNode->data = data;
    newNode->left = newNode->right = NULL;

    // If the tree is empty, make the new node the root
    if (root == NULL)
    {
        root = newNode;
        return;
    }

    // Start at the root node
    Node *curr = root;

    // Traverse the tree to find the correct position for the new node
    while (true)
    {
        if (data < curr->data)
        {
            // Go left
            if (curr->left == NULL)
            {
                curr->left = newNode;
                break;
            }
            else
            {
                curr = curr->left;
            }
        }
        else
        {
            // Go right
            if (curr->right == NULL)
            {
                curr->right = newNode;
                break;
            }
            else
            {
                curr = curr->right;
            }
        }
    }

    // Perform the splay operation
    splay(data, root);
}

Search

The search operation searches the Splay Tree for a given data value. It takes the data value to be searched for and the root node of the tree as parameters.

// Function to search for a node in the Splay Tree
Node *search(int data, Node *&root)
{
    // Start at the root node
    Node *curr = root;

    // Traverse the tree to find the node
    while (curr != NULL)
    {
        if (data == curr->data)
        {
            // Perform the splay operation
            splay(data, root);
            return curr;
        }
        else if (data < curr->data)
        {
            // Go left
            curr = curr->left;
        }
        else
        {
            // Go right
            curr = curr->right;
        }
    }

    // If the node is not found, return NULL
    return NULL;
}

Deletion

The deletion operation deletes a node from the Splay Tree. It takes the data value to be deleted and the root node of the tree as parameters.

// Function to delete a node from the Splay Tree
void deleteNode(int data, Node *&root)
{
    // If the tree is empty, there is nothing to delete
    if (root == NULL)
    {
        return;
    }

    // Search for the node to be deleted
    Node *nodeToDelete = search(data, root);

    if (nodeToDelete != NULL)
    {
        // If the node has no children, just delete it
        if (nodeToDelete->left == NULL && nodeToDelete->right == NULL)
        {
            delete nodeToDelete;
            nodeToDelete = NULL;
            root = NULL;
        }
        else
        {
            // Find the inorder successor of the node
            Node *inorderSuccessor = findInorderSuccessor(nodeToDelete);

            // Copy the data of the inorder successor to the node to be deleted
            nodeToDelete->data = inorderSuccessor->data;

            // Delete the inorder successor
            delete inorderSuccessor;
            inorderSuccessor = NULL;
        }
    }
}

Splay

The splay operation reorganizes the tree after each operation. It takes the data value of the node to be splayed and the root node of the tree as parameters.

// Function to perform the splay operation
void splay(int data, Node *&root)
{
    // If the tree is empty, there is nothing to splay
    if (root == NULL)
    {
        return;
    }

    // Create two auxiliary trees
    Node *leftTreeMax = NULL;
    Node *rightTreeMin = NULL;

    // Start at the root node
    Node *curr = root;

    while (true)
    {
        if (data < curr->data)
        {
            // Go left
            if (curr->left == NULL)
            {
                break;
            }

            if (data < curr->left->data)
            {
                // Zig-Zig (Left Left)
                rotateRight(curr);
                if (curr->left == NULL)
                {
                    break;
                }
            }

            // Link Right
            if (rightTreeMin == NULL)
            {
                rightTreeMin = curr;
            }
            else
            {
                rightTreeMin->right = curr;
            }

            curr = curr->left;
        }
        else if (data > curr->data)
        {
            // Go right
            if (curr->right == NULL)
            {
                break;
            }

            if (data > curr->right->data)
            {
                // Zig-Zag (Right Left)
                rotateLeft(curr);
                if (curr->right == NULL)
                {
                    break;
                }
            }

            // Link Left
            if (leftTreeMax == NULL)
            {
                leftTreeMax = curr;
            }
            else
            {
                leftTreeMax->left = curr;
            }

            curr = curr->right;
        }
        else
        {
            break;
        }
    }

    // Reassemble the tree
    if (leftTreeMax != NULL)
    {
        leftTreeMax->left = curr->right;
    }

    if (rightTreeMin != NULL)
    {
        rightTreeMin->right = curr->left;
    }

    curr->left = root;
    curr->right = root->right;
    root->right = NULL;
    root = curr;
}

Conclusion

In this article, we discussed Splay Trees, a type of self-balancing binary search tree. We discussed the structure of the tree, its time and space complexities, and how to implement it in C++. We also provided code examples for the operations of insertion, search, deletion, and splay.

Exercises

// Function to count the number of nodes in a Splay Tree
int countNodes(Node *root)
{
    // Base case
    if (root == NULL)
    {
        return 0;
    }

    // Recursive case
    return 1 + countNodes(root->left) + countNodes(root->right);
}

// Function to find the maximum value stored in a Splay Tree
int maxValue(Node *root)
{
    // Base case
    if (root == NULL)
    {
        return INT_MIN;
    }

    // Recursive case
    int leftMax = maxValue(root->left);
    int rightMax = maxValue(root->right);

    return max(root->data, max(leftMax, rightMax));
}

// Function to delete all nodes in a Splay Tree
void deleteAllNodes(Node *&root)
{
    // Base case
    if (root == NULL)
    {
        return;
    }

    // Recursive case
    deleteAllNodes(root->left);
    deleteAllNodes(root->right);
    delete root;
    root = NULL;
}

// Function to check if a Splay Tree is a valid binary search tree
bool isBST(Node *root, int minValue, int maxValue)
{
    // Base case
    if (root == NULL)
    {
        return true;
    }

    // Recursive case
    if (root->data < minValue || root->data > maxValue)
    {
        return false;
    }

    return isBST(root->left, minValue, root->data) && isBST(root->right, root->data, maxValue);
}

// Function to find the height of a Splay Tree
int height(Node *root)
{
    // Base case
    if (root == NULL)
    {
        return 0;
    }

    // Recursive case
    int leftHeight = height(root->left);
    int rightHeight = height(root->right);

    return 1 + max(leftHeight, rightHeight);
}