Tree

Sply Tree Implementation

Pinterest LinkedIn Tumblr

Data structure Description

A splay tree is a self-adjusting binary search tree with the additional property that recently accessed elements are quick to access again. The splay tree has good performance during the average case and uses small memory compare than another tree.

The main disadvantage is that the height of the splay tree is linear. It may be difficult to handle in the multithreaded environment. Splay tree reshape the nodes to know frequently access elements which improve the better lookup time. Splay trees can only guarantee that any sequence of n operations takes at most O (n log n) time.

Write a program to implement the splay tree with insert and remove operations.

Algorithm Explanation

Splay can be three steps.
(1) Zig operation is performed when the parent of X is the root of the tree.
(2) The zig-zig operation is performed when X and its parent are the same child type as each other It performs either two right rotations or two left rotations depending on the side.
(3) The zig-zag operation is performed when is a different child type to its parent.
Insert the node into the tree.
Remove the node form the tree.

Source Code

package com.dsacode.DataStructre.splytree;
 
import java.util.Arrays;
 
class BinaryNode {
    BinaryNode(Integer theKey) {
        key = theKey;
        left = right = null;
    }
 
    Integer key;
    BinaryNode left;
    BinaryNode right;
}
 
public class SplayTreeImpl {
 
    private BinaryNode root;
    private static BinaryNode header = new BinaryNode(null);
     
    public SplayTreeImpl() {
        root = null;
    }
 
    public BinaryNode getRoot(){
        return root;
    }
     
    public void insert(Integer key) {
        int c;
        if (root == null) {
            root = new BinaryNode(key);
            return;
        }
        splay(key);
        if ((c = key.compareTo(root.key)) == 0) {
 
            return;
        }
        BinaryNode n = new BinaryNode(key);
        if (c < 0) {
            n.left = root.left;
            n.right = root;
            root.left = null;
        } else {
            n.right = root.right;
            n.left = root;
            root.right = null;
        }
        root = n;
    }
 
    public void remove(Integer key) {
        BinaryNode x;
        splay(key);
        if (key.compareTo(root.key) != 0) {
            return;
        }
        if (root.left == null) {
            root = root.right;
        } else {
            x = root.right;
            root = root.left;
            splay(key);
            root.right = x;
        }
    }
 
    public Integer findMin() {
        BinaryNode x = root;
        if (root == null)
            return null;
        while (x.left != null)
            x = x.left;
        splay(x.key);
        return x.key;
    }
 
     
    public Integer findMax() {
        BinaryNode x = root;
        if (root == null)
            return null;
        while (x.right != null)
            x = x.right;
        splay(x.key);
        return x.key;
    }
 
    public Integer find(Integer key) {
        if (root == null)
            return null;
        splay(key);
        if (root.key.compareTo(key) != 0)
            return null;
        return root.key;
    }
 
     
    public boolean isEmpty() {
        return root == null;
    }
 
     
 
    private void splay(Integer key) {
        BinaryNode l, r, t, y;
        l = r = header;
        t = root;
        header.left = header.right = null;
        for (;;) {
            if (key.compareTo(t.key) < 0) {
                if (t.left == null)
                    break;
                if (key.compareTo(t.left.key) < 0) {
                    y = t.left;
                    t.left = y.right;
                    y.right = t;
                    t = y;
                    if (t.left == null)
                        break;
                }
                r.left = t;
                r = t;
                t = t.left;
            } else if (key.compareTo(t.key) > 0) {
                if (t.right == null)
                    break;
                if (key.compareTo(t.right.key) > 0) {
                    y = t.right;
                    t.right = y.left;
                    y.left = t;
                    t = y;
                    if (t.right == null)
                        break;
                }
                l.right = t;
                l = t;
                t = t.right;
            } else {
                break;
            }
        }
        l.right = t.left;
        r.left = t.right;
        t.left = header.right;
        t.right = header.left;
        root = t;
    }
 
    public void postorder(BinaryNode r)  {
 
        if (r != null)   {
            postorder(r.left);            
            postorder(r.right);
            System.out.print(r.key +" ");
        }
 
    }    
 
    public static void main(String[] args) {
        SplayTreeImpl t = new SplayTreeImpl();
 
        Integer []array={45,67,34,22,89,56,78,11};
        System.out.println("Array of items insert into the Splay  tree:"+ Arrays.toString(array));
         
        System.out.print("Splay tree items after insert into Splay  tree using post order:");
        for(Integer i : array)
            t.insert(i);
        t.postorder(t.getRoot());
        System.out.println();
         
        System.out.println("Minimum  item from Splay tree:" + t.findMin());
        System.out.println("Max item from Splay tree:" + t.findMax());
    }
 
}

Output

Array of items insert into the splay tree:[45, 67, 34, 22, 89, 56, 78, 11]
Splay tree items after insert into Splay tree using post order:34 56 45 89 78 67 22 11
Minimum item from Splay tree:11
Max item from Splay tree:89

Source Explanation

Build an array of elements and insert each element to the splay tree.
Insert into the tree. If the element already in the tree, throw the exception.
The top-down splay operation based on the given key. If the key is in the tree, then the Binary Node containing that key becomes the root.
If the key is not in the tree, then after the splay, key.root is either the greatest key < key in the tree, or least key > key in the tree.
Return minimum of the element and display the value.
Return the maximum of the element and display the value.

Complexity

OperationsBest CaseAverage Caseworst Case
SearchO(log(n))O(log(n))
InsertionO(log n)O(log(n))
DeletionO(log n)O(log(n))

Real Applications

  1. Lexicographic Search Tree
  2. Data Compression
  3. Encryption
  4. Cache Implementation

Reference

  1. https://www.cs.usfca.edu/~galles/visualization/SplayTree.html
  2. https://en.wikipedia.org/wiki/Splay_tree
  3. http://www.drdobbs.com/cpp/implementing-splay-trees-in-c/184402007
  4. http://www.cs.cornell.edu/courses/cs3110/2011sp/recitations/rec25-splay/splay.htm
  5. http://www.link.cs.cmu.edu/splay/

Write A Comment