Self-Optimizing Binary Search Tree

The Splay Tree

Published in

smucs

9 min readApr 5, 2021

Introduction

A splay tree is a data structure that was invented by computer science professors Daniel Sleator and Robert Tarjan in 1985.

While most self balancing binary search trees are designed to decrease the worst case time for a single operation, Slaetor and Tarjan designed the splay tree to reduce the time for a sequence of operations.

A splay tree is a self adjusting binary search tree that “splays” an element any time it is accessed. Splaying is the process of moving the given element to the root of the tree through a series of rotations. Therefore, whenever an item is searched for or inserted, its node is splayed. When a node is deleted, it is splayed before it is removed from the tree and one of its children becomes the new root of the tree, depending on implementation.

Advantages of a Splay Tree

Splay trees are ideal in applications where data is non-uniformly accessed. Since the most frequently accessed nodes are closer to the root of the tree, less comparisons are required to access them. The tree is self optimizing, so the more operations that are done on the tree, the better it will suit the given use case.

This self optimization is more efficient after sequence of operations than a weight or a height balanced tree, like an AVL tree. Since AVL trees are static when searching, an item that is never searched for could remain at the top of the tree while an item that is searched for millions of times could remain 50 levels deep in the tree. Additionally, splay trees are simpler to implement, and require less space than other self-balancing trees, since balance information does not need to be stored in each of the nodes.

A splay tree has an average search time of O(log n) using amortized analysis¹, meaning a sequence of m operations for a splay tree with n nodes will take O(m log n) time². An AVL tree has an average search time of O(log n) for any single operation. Since the more frequently accessed nodes are closer to the root in a splay tree, total runtime for a sequence of operations is theoretically much faster.

“Splay trees are used in Windows NT (in the virtual memory, networking, and file system code), the gcc compiler and GNU C++ library, the sed string editor, Fore Systems network routers, the most popular implementation of Unix malloc, Linux loadable kernel modules, and in much other software.” ³

Disadvantages of a Splay Tree

Unlike a height balanced tree, splay trees cannot guarantee a fast lookup time for a single operation. While an AVL can guarantee a worst case lookup time of O(log n), the worst case lookup for single operation in a splay tree is O(n). If items are inserted in order, the tree can take the structure of a linked list. Therefore, a splay tree would not be ideal for real-time single searches since it is optimized for a sequence of operations.

When elements are accessed with uniform frequency, the benefits of a splaying become obsolete.

Additionally, since splay trees are modified after every search, they cannot be used in multithreaded environments with parallel searches.

Splay

Splaying is the process by which a splay tree moves a given node to the root of the tree using a series of rotations. These rotations are: Zig, Zag, Zig-Zig, Zag-Zag, Zig-Zag, and Zag-Zig.

Zig and Zag

A zig rotation is used if the given node x is the left child of its parent node and it is a rightward rotation. A zag rotation is used when the given node y is the right child of its parent node and is a leftward rotation. Only one rotation is required:

The following code example shows how nodes are swapped in a Zig (right) rotation:

// Zig at node x
void rightRotate(NodePtr x) {
    NodePtr y = x->left;
    x->left = y->right;
    if (y->right != nullptr) {
        y->right->parent = x;
    }
    y->parent = x->parent;
    if (x->parent == nullptr) {
        this->root = y;
    } else if (x == x->parent->right) {
        x->parent->right = y;
    } else {
        x->parent->left = y;
    }
    y->right = x;
    x->parent = y;
}

The following code example shows how nodes are swapped in a Zag (left) rotation:

// Zag at node x
void leftRotate(NodePtr x) {
    NodePtr y = x->right;
    x->right = y->left;
    if (y->left != nullptr) {
        y->left->parent = x;
    }
    y->parent = x->parent;
    if (x->parent == nullptr) {
        this->root = y;
    } else if (x == x->parent->left) {
        x->parent->left = y;
    } else {
        x->parent->right = y;
    }
    y->left = x;
    x->parent = y;
}

If the the parent of the current node is the root of the tree. A zig or zag rotation will occur to move it to the root of the tree:

if (!x->parent->parent) {
            if (x == x->parent->left) {
                // zig rotation
                rightRotate(x->parent);
            } else {
                // zag rotation
                leftRotate(x->parent);
            }
}

Zig-Zig and Zag-Zag

A zig-zig rotation is used when a given node X is is the left child of its parent node P, and its parent node is the left child of the grandparent node G. As the title implies, two zig rotations are executed in top down order; first the parent and grandparent nodes are rotated, then the parent and current nodes are rotated.

The following code shows the case when zig-zig is used:

else if (x == x->parent->left && x->parent == x->parent->parent->left) {
            // zig-zig rotation
            rightRotate(x->parent->parent);
            rightRotate(x->parent);
        }

A zag-zag rotation is used when a given node X is is the right child of its parent node P, and its parent node is the right child of the grandparent node G. First, there is a zag rotation between the parent and grandparent nodes, then there is a zag rotation between the parent and current nodes:

The following code shows the case when zag-zag is used:

else if (x == x->parent->right && x->parent == x->parent->parent->right) {
            // zag-zag rotation
            leftRotate(x->parent->parent);
            leftRotate(x->parent);
        }

Zig-Zag and Zag-Zig

A zig-zag is a right-left rotation. This is used if the current node X is the left child of its parent node P and the parent node is the right child of the grandparent node G. First, the current node and parent node are rotated with a zig rotation, then the parent node and grandparent node are rotated with a zag rotation:

A zag-zig is a left-right rotation. This is used if the current node X is the right child of its parent node P and the parent node is the left child of the grandparent node G. First, the current node and parent node are rotated with a zag rotation, then the parent node and grandparent node are rotated with a zig rotation:

The following code shows the case when zig-zag is used, and the case when zag-zig is used:

else if (x == x->parent->right && x->parent == x->parent->parent->left) {
            // zig-zag rotation
            leftRotate(x->parent);
            rightRotate(x->parent);
        } else {
            // zag-zig rotation
            rightRotate(x->parent);
            leftRotate(x->parent);
        }

Splay Tree Implementation

Insert

The insert function for the splay tree begins like the insert for a normal binary search tree.

In the following code, the new node is inserted to the binary search tree at its correct location. After the node is inserted at the correct location in the tree, the splay function is called on that node to make it the root of the tree:

void SplayTree::insert(int key) {
    // normal BST insert
    NodePtr node = new Node;
    node->parent = nullptr;
    node->left = nullptr;
    node->right = nullptr;
    node->data = key;
    NodePtr y = nullptr;
    NodePtr x = this->mRoot;

    while (x != nullptr) {
        y = x;
        if (node->data < x->data) {
            x = x->left;
        } else {
            x = x->right;
        }
    }

    // y is parent of x
    node->parent = y;
    if (y == nullptr) {
        mRoot = node;
    } else if (node->data < y->data) {
        y->left = node;
    } else {
        y->right = node;
    }

    // splay the node
    splay(node);
}

In the examples below, trees are displayed as follows:

└──── denotes a right child and ├──── denotes a left child

Consider the following splay tree created by inserting integers 3, 39, 87, 7, 22, 42, 20:

Splay Tree Diagram:└────20
     ├────7
     |    ├────3
     └────42
          ├────22
          |    └────39
          └────87Pre-Order Traversal:
20 7 3 42 22 39 87

After inserting the integer 10, the tree is as follows:

Splay Tree Diagram:└────10
     ├────7
     |    ├────3
     └────20
          └────42
               ├────22
               |    └────39
               └────87Pre-Order Traversal:
10 7 3 20 42 22 39 87

As you can see, 10 is now the root of the tree, and the tree has been rebalanced.

Search

The search function returns a pointer to the node that contains the desired element, and the splay function is called on that node:

The following example shows our tree from the previous section after searching for 42:

Splay Tree Diagram:└────42
     ├────20
     |    ├────10
     |    |    ├────7
     |    |    |    ├────3
     |    └────22
     |         └────39
     └────87Pre-Order Traversal:
42 20 10 7 3 22 39 87

As you can see, the tree has been rebalanced with 42 as its root.

Delete

In Part 1 of the deleteNodeHelper function, the delete function begins by splaying the tree at the node that is to be deleted.

In Part 2 the tree is split, resulting in two new trees: the right subtree of the root, and the left subtree of the root. The root is removed.

In Part 3 the join function splays the node with the maximum value in the left subtree. Then the root of the right subtree becomes the right child of the root of the left subtree. Finally the desired node is deleted and the splay tree has been rebalanced.

//====================Part 1==================
void SplayTree::deleteNodeHelper(NodePtr node, int key) {
    NodePtr x = nullptr;
    NodePtr t, s;
    while (node != nullptr){
        if (node->data == key) {
            x = node;
        }

        if (node->data <= key) {
            node = node->right;
        } else {
            node = node->left;
        }
    }

    if (x == nullptr) {
        cout<<"Couldn't find key in the tree"<<endl;
        return;
    }
    splay(x);
//====================Part 2==================
    split(x, s, t); // split the tree
    if (s->left){ // remove x
        s->left->parent = nullptr;
    }
    //s->left is left subtree, t is right subtree//====================Part 3==================
    mRoot = join(s->left, t);
    delete(s);
    s = nullptr;
}

The following example shows our tree from the previous section after 22 has been deleted:

Splay Tree Diagram:└────20
     ├────10
     |    ├────7
     |    |    ├────3
     └────42
          ├────39
          └────87Pre-Order Traversal:
20 10 7 3 42 39 87

As you can see, the tree has been rebalanced with the left child of the deleted node as the new root.

Github Repository

All source code and tests can be found at the Github page linked here

References

6. https://algorithmtutor.com/Data-Structures/Tree/Splay-Trees/

Self-Optimizing Binary Search Tree

The Splay Tree

Introduction

Advantages of a Splay Tree

Disadvantages of a Splay Tree

Splay

Zig and Zag

Zig-Zig and Zag-Zag

Zig-Zag and Zag-Zig

Splay Tree Implementation

Insert

Search

Delete

Github Repository

Further Reading

Splay Trees

A splay tree is an efficient implementation of a balanced binary search tree that takes advantage of locality in the…

Splay tree - Wikipedia

A splay tree is a binary search tree with the additional property that recently accessed elements are quick to access…

Splay Trees (with implementations in C++, Java, and Python)

A Splay tree is a self-adjusting binary search tree invented by Sleator and Tarjan. Unlike an AVL tree (or a Red-Black…

References

Written by Elias Mann