Question

write a java program that implements the splay tree data structure for the dictionary abstract data type.

Initially the program reads data from "in.dat", and establishes an ordinary binary search tree by inserting the data into the tree. The data file contains integers, one per line.

in.dat file contents:

3456
5678
1234
2369
7721
3354
1321
4946
3210
8765

Then the program starts an interactive mode. The commands are as follows.

S 1000 - splay the tree at 1000

F 2000 - search/find the node with key 2000

I 3000 - insert a node with key 3000

D 4000 - delete the node with key 4000

For each command,

1. Report appropriate message after the command is executed. Examples are:

Splay is done

Search is successful

Search is unsuccessful

The key is inserted into the tree

Duplicated keys

The key is deleted from the tree

The key is not in the tree

2. Display the new tree.

Answer 1

public class Main

{

    class SplayNode

    {    

        SplayNode left, right, parent;

        int element;

        

        public SplayNode()  // Constructor

        {

            this(0, null, null, null);

        }          

    

        public SplayNode(int ele)  // Constructor

        {

            this(ele, null, null, null);

        }   

     

        public SplayNode(int ele, SplayNode left, SplayNode right, SplayNode parent)   // Constructor

        {

            this.left = left;

            this.right = right;

            this.parent = parent;

            this.element = ele;         

        }    

    }

    class SplayTree

    {

        private SplayNode root;

        private int count = 0;

        public SplayTree() // Constructor

        {

            root = null;

        }

        public boolean isEmpty()   // to check if tree is empty

        {

            return root == null;

        }

        

        public void clear()    //to clear tree

        {

            root = null;

            count = 0;

        }

        public void insert(int ele)    // to insert element

        {

            SplayNode z = root;

            SplayNode p = null;

            while (z != null)

            {

                p = z;

                if (ele > p.element)

                    z = z.right;

                else

                    z = z.left;

            }

            z = new SplayNode();

            z.element = ele;

            z.parent = p;

            if (p == null)

                root = z;

            else if (ele > p.element)

                p.right = z;

            else

                p.left = z;

            Splay(z);

            count++;

        }

        public void makeLeftChildParent(SplayNode c, SplayNode p)

        {

            if ((c == null) || (p == null) || (p.left != c) || (c.parent != p))

                throw new RuntimeException("WRONG");

            if (p.parent != null)

            {

                if (p == p.parent.left)

                    p.parent.left = c;

                else

                    p.parent.right = c;

            }

            if (c.right != null)

                c.right.parent = p;

            c.parent = p.parent;

            p.parent = c;

            p.left = c.right;

            c.right = p;

        }

        

        public void makeRightChildParent(SplayNode c, SplayNode p)

        {

            if ((c == null) || (p == null) || (p.right != c) || (c.parent != p))

                throw new RuntimeException("WRONG");

            if (p.parent != null)

            {

                if (p == p.parent.left)

                    p.parent.left = c;

                else

                    p.parent.right = c;

            }

            if (c.left != null)

                c.left.parent = p;

            c.parent = p.parent;

            p.parent = c;

            p.right = c.left;

            c.left = p;

        }

        private void Splay(SplayNode x)    // function to splay

        {

            while (x.parent != null)

            {

                SplayNode Parent = x.parent;

                SplayNode GrandParent = Parent.parent;

                if (GrandParent == null)

                {

                    if (x == Parent.left)

                        makeLeftChildParent(x, Parent);

                    else

                        makeRightChildParent(x, Parent);                 

                }

                else

                {

                    if (x == Parent.left)

                    {

                        if (Parent == GrandParent.left)

                        {

                            makeLeftChildParent(Parent, GrandParent);

                            makeLeftChildParent(x, Parent);

                        }

                        else

                        {

                            makeLeftChildParent(x, x.parent);

                            makeRightChildParent(x, x.parent);

                        }

                    }

                    else

                    {

                        if (Parent == GrandParent.left)

                        {

                            makeRightChildParent(x, x.parent);

                            makeLeftChildParent(x, x.parent);

                        }

                        else

                        {

                            makeRightChildParent(Parent, GrandParent);

                            makeRightChildParent(x, Parent);

                        }

                    }

                }

            }

            root = x;

        }

        public void remove(int ele)     //to remove element

        {

            SplayNode node = findNode(ele);

            remove(node);

        }

        private void remove(SplayNode node)     //to remove node

        {

            if (node == null)

                return;

            Splay(node);

            if( (node.left != null) && (node.right !=null))

            {

                SplayNode min = node.left;

                while(min.right!=null)

                    min = min.right;

                min.right = node.right;

                node.right.parent = min;

                node.left.parent = null;

                root = node.left;

            }

            else if (node.right != null)

            {

                node.right.parent = null;

                root = node.right;

            }

            else if( node.left !=null)

            {

                node.left.parent = null;

                root = node.left;

            }

            else

            {

                root = null;

            }

            node.parent = null;

            node.left = null;

            node.right = null;

            node = null;

            count--;

        }

        public int countNodes()     // to count number of nodes

        {

            return count;

        }

        public boolean search(int val)    // to search for an element

        {

            return findNode(val) != null;

        }

        private SplayNode findNode(int ele)

        {

            SplayNode PrevNode = null;

            SplayNode z = root;

            while (z != null)

            {

                PrevNode = z;

                if (ele > z.element)

                    z = z.right;

                else if (ele < z.element)

                    z = z.left;

                else if(ele == z.element)

                {

                    Splay(z);

                return z;

                }

            }

            if(PrevNode != null)

            {

                Splay(PrevNode);

                return null;

            }

            return null;

        }

        public void inorder()  //for inorder traversal

        {

            inorder(root);

        }

        private void inorder(SplayNode r)

        {

            if (r != null)

            {

                inorder(r.left);

                System.out.print(r.element +" ");

                inorder(r.right);

            }

        }

        public static void main(String[] args)

        {

            File file = new File("in.dat");

            Scanner scnr = new Scanner(file);

            int n,i=0;

        

            while(scnr.hasNextLine())   // count number of integers in file

            {

                n= Integer.parseInt(scnr.nextLine());

                i++;

            }

            int item[i];    //to store data in array

            i=0;

            while(scnr.hasNextLine())

            {

                n= Integer.parseInt(scnr.nextLine();

                item[i]=n;

                i++;

            }

            node root = newNode(1000);

            System.out.System.out.println("splay is done");

            root = spt.search(2000);

            if(root!=null)

                System.out.System.out.println("search is successful");

            else

                System.out.System.out.println("search is not successful");

            spt.insert(3000);

            System.out.System.out.println("The key is inserted into the tree");

            k=spt.remove(4000);

            if(k)

                System.out.System.out.println("The key is deleted from the tree");

            else

                System.out.System.out.println("The key is not in the tree");

            System.out.System.out.println("the tree is :");

            spt.inorder();

        

        }

}