Java Program to Implement Splay Tree

This is a Java Program to implement Splay Tree. A splay tree is a self-adjusting binary search tree with the additional property that recently accessed elements are quick to access again. It performs basic operations such as insertion, look-up and removal in O(log n) amortized time. For many sequences of non-random operations, splay trees perform better than other search trees, even when the specific pattern of the sequence is unknown. The splay tree was invented by Daniel Dominic Sleator and Robert Endre Tarjan in 1985.

Here is the source code of the Java program to implement Splay Tree. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

  1. /**
  2.  *  Java Program to Implement SplayTree
  3.  **/
  4.  
  5.  import java.util.Scanner;
  6.  
  7.  /** Class Node **/
  8.  class SplayNode
  9.  {    
  10.      SplayNode left, right, parent;
  11.      int element;
  12.  
  13.      /** Constructor **/
  14.      public SplayNode()
  15.      {
  16.          this(0, null, null, null);
  17.      }          
  18.      /** Constructor **/
  19.      public SplayNode(int ele)
  20.      {
  21.          this(ele, null, null, null);
  22.      } 
  23.      /** Constructor **/
  24.      public SplayNode(int ele, SplayNode left, SplayNode right, SplayNode parent)
  25.      {
  26.          this.left = left;
  27.          this.right = right;
  28.          this.parent = parent;
  29.          this.element = ele;         
  30.      }    
  31.  }
  32.  
  33.  /** Class SplayTree **/
  34.  class SplayTree
  35.  {
  36.      private SplayNode root;
  37.      private int count = 0;
  38.  
  39.      /** Constructor **/
  40.      public SplayTree()
  41.      {
  42.          root = null;
  43.      }
  44.  
  45.      /** Function to check if tree is empty **/
  46.      public boolean isEmpty()
  47.      {
  48.          return root == null;
  49.      }
  50.  
  51.      /** clear tree **/
  52.      public void clear()
  53.      {
  54.          root = null;
  55.          count = 0;
  56.      }
  57.  
  58.      /** function to insert element */
  59.      public void insert(int ele)
  60.      {
  61.          SplayNode z = root;
  62.          SplayNode p = null;
  63.          while (z != null)
  64.          {
  65.              p = z;
  66.              if (ele > p.element)
  67.                  z = z.right;
  68.              else
  69.                  z = z.left;
  70.          }
  71.          z = new SplayNode();
  72.          z.element = ele;
  73.          z.parent = p;
  74.          if (p == null)
  75.              root = z;
  76.          else if (ele > p.element)
  77.              p.right = z;
  78.          else
  79.              p.left = z;
  80.          Splay(z);
  81.          count++;
  82.      }
  83.      /** rotate **/
  84.      public void makeLeftChildParent(SplayNode c, SplayNode p)
  85.      {
  86.          if ((c == null) || (p == null) || (p.left != c) || (c.parent != p))
  87.              throw new RuntimeException("WRONG");
  88.  
  89.          if (p.parent != null)
  90.          {
  91.              if (p == p.parent.left)
  92.                  p.parent.left = c;
  93.              else 
  94.                  p.parent.right = c;
  95.          }
  96.          if (c.right != null)
  97.              c.right.parent = p;
  98.  
  99.          c.parent = p.parent;
  100.          p.parent = c;
  101.          p.left = c.right;
  102.          c.right = p;
  103.      }
  104.  
  105.      /** rotate **/
  106.      public void makeRightChildParent(SplayNode c, SplayNode p)
  107.      {
  108.          if ((c == null) || (p == null) || (p.right != c) || (c.parent != p))
  109.              throw new RuntimeException("WRONG");
  110.          if (p.parent != null)
  111.          {
  112.              if (p == p.parent.left)
  113.                  p.parent.left = c;
  114.              else
  115.                  p.parent.right = c;
  116.          }
  117.          if (c.left != null)
  118.              c.left.parent = p;
  119.          c.parent = p.parent;
  120.          p.parent = c;
  121.          p.right = c.left;
  122.          c.left = p;
  123.      }
  124.  
  125.      /** function splay **/
  126.      private void Splay(SplayNode x)
  127.      {
  128.          while (x.parent != null)
  129.          {
  130.              SplayNode Parent = x.parent;
  131.              SplayNode GrandParent = Parent.parent;
  132.              if (GrandParent == null)
  133.              {
  134.                  if (x == Parent.left)
  135.                      makeLeftChildParent(x, Parent);
  136.                  else
  137.                      makeRightChildParent(x, Parent);                 
  138.              } 
  139.              else
  140.              {
  141.                  if (x == Parent.left)
  142.                  {
  143.                      if (Parent == GrandParent.left)
  144.                      {
  145.                          makeLeftChildParent(Parent, GrandParent);
  146.                          makeLeftChildParent(x, Parent);
  147.                      }
  148.                      else 
  149.                      {
  150.                          makeLeftChildParent(x, x.parent);
  151.                          makeRightChildParent(x, x.parent);
  152.                      }
  153.                  }
  154.                  else 
  155.                  {
  156.                      if (Parent == GrandParent.left)
  157.                      {
  158.                          makeRightChildParent(x, x.parent);
  159.                          makeLeftChildParent(x, x.parent);
  160.                      } 
  161.                      else 
  162.                      {
  163.                          makeRightChildParent(Parent, GrandParent);
  164.                          makeRightChildParent(x, Parent);
  165.                      }
  166.                  }
  167.              }
  168.          }
  169.          root = x;
  170.      }
  171.  
  172.      /** function to remove element **/
  173.      public void remove(int ele)
  174.      {
  175.          SplayNode node = findNode(ele);
  176.         remove(node);
  177.      }
  178.  
  179.      /** function to remove node **/
  180.      private void remove(SplayNode node)
  181.      {
  182.          if (node == null)
  183.              return;
  184.  
  185.          Splay(node);
  186.          if( (node.left != null) && (node.right !=null))
  187.          { 
  188.              SplayNode min = node.left;
  189.              while(min.right!=null)
  190.                  min = min.right;
  191.  
  192.              min.right = node.right;
  193.              node.right.parent = min;
  194.              node.left.parent = null;
  195.              root = node.left;
  196.          }
  197.          else if (node.right != null)
  198.          {
  199.              node.right.parent = null;
  200.              root = node.right;
  201.          } 
  202.          else if( node.left !=null)
  203.          {
  204.              node.left.parent = null;
  205.              root = node.left;
  206.          }
  207.          else
  208.          {
  209.              root = null;
  210.          }
  211.          node.parent = null;
  212.          node.left = null;
  213.          node.right = null;
  214.          node = null;
  215.          count--;
  216.      }
  217.  
  218.      /** Functions to count number of nodes **/
  219.      public int countNodes()
  220.      {
  221.          return count;
  222.      }
  223.  
  224.      /** Functions to search for an element **/
  225.      public boolean search(int val)
  226.      {
  227.          return findNode(val) != null;
  228.      }
  229.  
  230.      private SplayNode findNode(int ele)
  231.      {
  232.     	 SplayNode PrevNode = null;
  233.          SplayNode z = root;
  234.          while (z != null)
  235.          {
  236.         	 PrevNode = z;
  237.              if (ele > z.element)
  238.                  z = z.right;
  239.              else if (ele < z.element)
  240.                  z = z.left;
  241.              else if(ele == z.element) {
  242.                  Splay(z);
  243.                  return z;
  244.              }
  245.  
  246.          }
  247.          if(PrevNode != null)
  248.          {
  249.              Splay(PrevNode);
  250.              return null;
  251.          }
  252.          return null;
  253.      }
  254.  
  255.      /** Function for inorder traversal **/ 
  256.      public void inorder()
  257.      {
  258.          inorder(root);
  259.      }
  260.      private void inorder(SplayNode r)
  261.      {
  262.          if (r != null)
  263.          {
  264.              inorder(r.left);
  265.              System.out.print(r.element +" ");
  266.              inorder(r.right);
  267.          }
  268.      }
  269.  
  270.      /** Function for preorder traversal **/
  271.      public void preorder()
  272.      {
  273.          preorder(root);
  274.      }
  275.      private void preorder(SplayNode r)
  276.      {
  277.          if (r != null)
  278.          {
  279.              System.out.print(r.element +" ");
  280.              preorder(r.left);             
  281.              preorder(r.right);
  282.          }
  283.      }
  284.  
  285.      /** Function for postorder traversal **/
  286.      public void postorder()
  287.      {
  288.          postorder(root);
  289.      }
  290.      private void postorder(SplayNode r)
  291.      {
  292.          if (r != null)
  293.          {
  294.              postorder(r.left);             
  295.              postorder(r.right);
  296.              System.out.print(r.element +" ");
  297.          }
  298.      }     
  299.  }
  300.  
  301.  /** Class SplayTreeTest **/
  302.  public class SplayTreeTest
  303.  {
  304.     public static void main(String[] args)
  305.     {            
  306.         Scanner scan = new Scanner(System.in);
  307.         /** Creating object of SplayTree **/
  308.         SplayTree spt = new SplayTree(); 
  309.         System.out.println("Splay Tree Test\n");          
  310.         char ch;
  311.         /**  Perform tree operations  **/
  312.         do    
  313.         {
  314.             System.out.println("\nSplay Tree Operations\n");
  315.             System.out.println("1. insert ");
  316.             System.out.println("2. remove ");
  317.             System.out.println("3. search");
  318.             System.out.println("4. count nodes");
  319.             System.out.println("5. check empty");
  320.             System.out.println("6. clear tree");
  321.  
  322.             int choice = scan.nextInt();            
  323.             switch (choice)
  324.             {
  325.             case 1 : 
  326.                 System.out.println("Enter integer element to insert");
  327.                 spt.insert( scan.nextInt() );                     
  328.                 break;
  329.             case 2 : 
  330.                 System.out.println("Enter integer element to remove");
  331.                 spt.remove( scan.nextInt() );                     
  332.                 break;                          
  333.             case 3 : 
  334.                 System.out.println("Enter integer element to search");
  335.                 System.out.println("Search result : "+ spt.search( scan.nextInt() ));
  336.                 break;                                          
  337.             case 4 : 
  338.                 System.out.println("Nodes = "+ spt.countNodes());
  339.                 break;     
  340.             case 5 : 
  341.                 System.out.println("Empty status = "+ spt.isEmpty());
  342.                 break;     
  343.             case 6 : 
  344.                 System.out.println("\nTree Cleared");
  345.                 spt.clear();
  346.                 break;        
  347.             default : 
  348.                 System.out.println("Wrong Entry \n ");
  349.                 break;   
  350.             }
  351.             /**  Display tree  **/
  352.             System.out.print("\nPost order : ");
  353.             spt.postorder();
  354.             System.out.print("\nPre order : ");
  355.             spt.preorder();
  356.             System.out.print("\nIn order : ");
  357.             spt.inorder(); 
  358.  
  359.             System.out.println("\nDo you want to continue (Type y or n) \n");
  360.             ch = scan.next().charAt(0);                        
  361.         } while (ch == 'Y'|| ch == 'y');               
  362.     }
  363. }

Splay Tree Test
 
 
Splay Tree Operations
 
1. insert 
2. remove 
3. search
4. count nodes
5. check empty
6. clear tree
1
Enter integer element to insert
14
 
Post order : 14 
Pre order : 14 
In order : 14 
Do you want to continue (Type y or n) 
 
y
 
Splay Tree Operations
 
1. insert 
2. remove 
3. search
4. count nodes
5. check empty
6. clear tree
1
Enter integer element to insert
28
 
Post order : 14 28 
Pre order : 28 14 
In order : 14 28 
Do you want to continue (Type y or n) 
 
y
 
Splay Tree Operations
 
1. insert 
2. remove 
3. search
4. count nodes
5. check empty
6. clear tree
1
Enter integer element to insert
19
 
Post order : 14 28 19 
Pre order : 19 14 28 
In order : 14 19 28 
Do you want to continue (Type y or n) 
 
y
 
Splay Tree Operations
 
1. insert 
2. remove 
3. search
4. count nodes
5. check empty
6. clear tree
1
Enter integer element to insert
63
 
Post order : 14 19 28 63 
Pre order : 63 28 19 14 
In order : 14 19 28 63 
Do you want to continue (Type y or n) 
 
y
 
Splay Tree Operations
 
1. insert 
2. remove 
3. search
4. count nodes
5. check empty
6. clear tree
1
Enter integer element to insert
5
 
Post order : 19 14 63 28 5 
Pre order : 5 28 14 19 63 
In order : 5 14 19 28 63 
Do you want to continue (Type y or n) 
 
y
 
Splay Tree Operations
 
1. insert 
2. remove 
3. search
4. count nodes
5. check empty
6. clear tree
1
Enter integer element to insert
7
 
Post order : 5 19 63 28 14 7 
Pre order : 7 5 14 28 19 63 
In order : 5 7 14 19 28 63 
Do you want to continue (Type y or n) 
 
y
 
Splay Tree Operations
 
1. insert 
2. remove 
3. search
4. count nodes
5. check empty
6. clear tree
3
Enter integer element to search
24
Search result : false
 
Post order : 5 14 7 63 28 19 
Pre order : 19 7 5 14 28 63 
In order : 5 7 14 19 28 63 
Do you want to continue (Type y or n) 
 
y
 
Splay Tree Operations
 
1. insert 
2. remove 
3. search
4. count nodes
5. check empty
6. clear tree
2
Enter integer element to remove
28
 
Post order : 5 14 7 63 19 
Pre order : 19 7 5 14 63 
In order : 5 7 14 19 63 
Do you want to continue (Type y or n) 
 
y
 
Splay Tree Operations
 
1. insert 
2. remove 
3. search
4. count nodes
5. check empty
6. clear tree
3
Enter integer element to search
28
Search result : false
 
Post order : 5 14 7 19 63 
Pre order : 63 19 7 5 14 
In order : 5 7 14 19 63 
Do you want to continue (Type y or n) 
 
y
 
Splay Tree Operations
 
1. insert 
2. remove 
3. search
4. count nodes
5. check empty
6. clear tree
2
Enter integer element to remove
14
 
Post order : 5 19 63 7 
Pre order : 7 5 63 19 
In order : 5 7 19 63 
Do you want to continue (Type y or n) 
 
y
 
Splay Tree Operations
 
1. insert 
2. remove 
3. search
4. count nodes
5. check empty
6. clear tree
2
Enter integer element to remove
7
 
Post order : 19 63 5 
Pre order : 5 63 19 
In order : 5 19 63 
Do you want to continue (Type y or n) 
 
y
 
Splay Tree Operations
 
1. insert 
2. remove 
3. search
4. count nodes
5. check empty
6. clear tree
4
Nodes = 3
 
Post order : 19 63 5 
Pre order : 5 63 19 
In order : 5 19 63 
Do you want to continue (Type y or n) 
 
y
 
Splay Tree Operations
 
1. insert 
2. remove 
3. search
4. count nodes
5. check empty
6. clear tree
5
Empty status = false
 
Post order : 19 63 5 
Pre order : 5 63 19 
In order : 5 19 63 
Do you want to continue (Type y or n) 
 
y
 
Splay Tree Operations
 
1. insert 
2. remove 
3. search
4. count nodes
5. check empty
6. clear tree
6
 
Tree Cleared
 
Post order : 
Pre order : 
In order : 
Do you want to continue (Type y or n) 
 
y
 
Splay Tree Operations
 
1. insert 
2. remove 
3. search
4. count nodes
5. check empty
6. clear tree
5
Empty status = true
 
Post order : 
Pre order : 
In order : 
Do you want to continue (Type y or n) 
 
n

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
advertisement
If you wish to look at all Java Programming examples, go to Java Programs.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.