Java Program to Implement Weight Balanced Tree

«
»
This is a Java Program to implement Weight Balanced Tree. A weight-balanced binary tree is a binary tree which is balanced based on knowledge of the probabilities of searching for each individual node. Within each subtree, the node with the highest weight appears at the root. This can result in more efficient searching performance.
Construction of such a tree is similar to that of a Treap, but node weights are chosen randomly in the latter.

Here is the source code of the Java program to implement Weight Balanced 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 Weight Balanced Tree
  3.  **/
  4.  
  5.  import java.util.Scanner;
  6.  import java.util.Random;
  7.  
  8.  /** Class WBTNode **/
  9.  class WBTNode
  10.  {
  11.      WBTNode left, right;
  12.      int weight, element;     
  13.  
  14.      /** Constructor **/    
  15.      public WBTNode(int ele, int wt)
  16.      {
  17.          this(ele, wt, null, null);
  18.      } 
  19.      /** Constructor **/
  20.      public WBTNode(int ele, int wt, WBTNode left, WBTNode right)
  21.      {
  22.          this.element = ele;
  23.          this.left = left;
  24.          this.right = right;
  25.          this.weight = wt;
  26.      }    
  27.  }
  28.  
  29.  /** Class WeightBalancedTree **/
  30.  class WeightBalancedTree
  31.  {
  32.      private WBTNode root;
  33.      private static WBTNode nil = new WBTNode(0, Integer.MAX_VALUE);
  34.  
  35.      /** Constructor **/
  36.      public WeightBalancedTree()
  37.      {
  38.          root = nil;
  39.      }
  40.  
  41.      /** Function to check if tree is empty **/
  42.      public boolean isEmpty()
  43.      {
  44.          return root == nil;
  45.      }
  46.  
  47.      /** clear tree **/
  48.      public void clear()
  49.      {
  50.          root = nil;
  51.      }
  52.  
  53.      /** Functions to insert data **/
  54.      public void insert(int X, int WT)
  55.      {
  56.          root = insert(X, WT, root);
  57.      }
  58.      private WBTNode insert(int X, int WT, WBTNode T)
  59.      {
  60.          if (T == nil)
  61.              return new WBTNode(X, WT, nil, nil);
  62.          else if (X < T.element)
  63.          {
  64.              T.left = insert(X, WT, T.left);
  65.              if (T.left.weight < T.weight)
  66.              {
  67.                   WBTNode L = T.left;
  68.                   T.left = L.right;
  69.                   L.right = T;
  70.                   return L;
  71.               }    
  72.          }
  73.          else if (X > T.element)
  74.          {
  75.              T.right = insert(X, WT, T.right);
  76.              if (T.right.weight < T.weight)
  77.              {
  78.                  WBTNode R = T.right;
  79.                   T.right = R.left;
  80.                   R.left = T;
  81.                   return R;
  82.              }
  83.          }
  84.          return T;
  85.      }
  86.  
  87.      /** Functions to count number of nodes **/
  88.      public int countNodes()
  89.      {
  90.          return countNodes(root);
  91.      }
  92.      private int countNodes(WBTNode r)
  93.      {
  94.          if (r == nil)
  95.              return 0;
  96.          else
  97.          {
  98.              int l = 1;
  99.              l += countNodes(r.left);
  100.              l += countNodes(r.right);
  101.              return l;
  102.          }
  103.      }
  104.  
  105.      /** Functions to search for an element **/
  106.      public boolean search(int val)
  107.      {
  108.          return search(root, val);
  109.      }
  110.      private boolean search(WBTNode r, int val)
  111.      {
  112.          boolean found = false;
  113.          while ((r != nil) && !found)
  114.          {
  115.              int rval = r.element;
  116.              if (val < rval)
  117.                  r = r.left;
  118.              else if (val > rval)
  119.                  r = r.right;
  120.              else
  121.              {
  122.                  found = true;
  123.                  break;
  124.              }
  125.              found = search(r, val);
  126.          }
  127.          return found;
  128.      }
  129.  
  130.      /** Function for inorder traversal **/
  131.      public void inorder()
  132.      {
  133.          inorder(root);
  134.      }
  135.      private void inorder(WBTNode r)
  136.      {
  137.          if (r != nil)
  138.          {
  139.              inorder(r.left);
  140.              System.out.print(r.element +" ");
  141.              inorder(r.right);
  142.          }
  143.      }
  144.  
  145.      /** Function for preorder traversal **/
  146.      public void preorder()
  147.      {
  148.          preorder(root);
  149.      }
  150.      private void preorder(WBTNode r)
  151.      {
  152.          if (r != nil)
  153.          {
  154.              System.out.print(r.element +" ");
  155.              preorder(r.left);             
  156.              preorder(r.right);
  157.          }
  158.      }
  159.  
  160.      /** Function for postorder traversal **/
  161.      public void postorder()
  162.      {
  163.          postorder(root);
  164.      }
  165.      private void postorder(WBTNode r)
  166.      {
  167.          if (r != nil)
  168.          {
  169.              postorder(r.left);             
  170.              postorder(r.right);
  171.              System.out.print(r.element +" ");
  172.          }
  173.      }         
  174.  }
  175.  
  176. /** Class WeightBalancedTreeTest **/
  177. public class WeightBalancedTreeTest
  178. {
  179.     public static void main(String[] args)
  180.     {            
  181.         Scanner scan = new Scanner(System.in);
  182.         /** Creating object of WeightBalancedTree**/
  183.         WeightBalancedTree wbt = new WeightBalancedTree(); 
  184.         System.out.println("Weight Balanced TreeTest\n");          
  185.         char ch;
  186.         /**  Perform tree operations  **/
  187.         do    
  188.         {
  189.             System.out.println("\nWeight Balanced TreeOperations\n");
  190.             System.out.println("1. insert ");
  191.             System.out.println("2. search");
  192.             System.out.println("3. count nodes");
  193.             System.out.println("4. check empty");
  194.             System.out.println("5. clear");
  195.  
  196.             int choice = scan.nextInt();            
  197.             switch (choice)
  198.             {
  199.             case 1 : 
  200.                 System.out.println("Enter integer element to insert and weight of the element");
  201.                 wbt.insert( scan.nextInt(), scan.nextInt() );                     
  202.                 break;                           
  203.             case 2 : 
  204.                 System.out.println("Enter integer element to search");
  205.                 System.out.println("Search result : "+ wbt.search( scan.nextInt() ));
  206.                 break;                                          
  207.             case 3 : 
  208.                 System.out.println("Nodes = "+ wbt.countNodes());
  209.                 break;     
  210.             case 4 : 
  211.                 System.out.println("Empty status = "+ wbt.isEmpty());
  212.                 break;
  213.             case 5 : 
  214.                 System.out.println("\nWeightBalancedTreeCleared");
  215.                 wbt.clear();
  216.                 break;            
  217.             default : 
  218.                 System.out.println("Wrong Entry \n ");
  219.                 break;   
  220.             }
  221.             /**  Display tree  **/ 
  222.             System.out.print("\nPost order : ");
  223.             wbt.postorder();
  224.             System.out.print("\nPre order : ");
  225.             wbt.preorder();    
  226.             System.out.print("\nIn order : ");
  227.             wbt.inorder();
  228.  
  229.             System.out.println("\nDo you want to continue (Type y or n) \n");
  230.             ch = scan.next().charAt(0);                        
  231.         } while (ch == 'Y'|| ch == 'y');               
  232.     }
  233. }

advertisement
Weight Balanced TreeTest
 
 
Weight Balanced TreeOperations
 
1. insert
2. search
3. count nodes
4. check empty
5. clear
1
Enter integer element to insert and weight of the element
24 28
 
Post order : 24
Pre order : 24
In order : 24
Do you want to continue (Type y or n)
 
y
 
Weight Balanced TreeOperations
 
1. insert
2. search
3. count nodes
4. check empty
5. clear
1
Enter integer element to insert and weight of the element
5 6
 
Post order : 24 5
Pre order : 5 24
In order : 5 24
Do you want to continue (Type y or n)
 
y
 
Weight Balanced TreeOperations
 
1. insert
2. search
3. count nodes
4. check empty
5. clear
1
Enter integer element to insert and weight of the element
63 94
 
Post order : 63 24 5
Pre order : 5 24 63
In order : 5 24 63
Do you want to continue (Type y or n)
 
y
 
Weight Balanced TreeOperations
 
1. insert
2. search
3. count nodes
4. check empty
5. clear
1
Enter integer element to insert and weight of the element
14 6
 
Post order : 63 24 14 5
Pre order : 5 14 24 63
In order : 5 14 24 63
Do you want to continue (Type y or n)
 
y
 
Weight Balanced TreeOperations
 
1. insert
2. search
3. count nodes
4. check empty
5. clear
1
Enter integer element to insert and weight of the element
1 17
 
Post order : 1 63 24 14 5
Pre order : 5 1 14 24 63
In order : 1 5 14 24 63
Do you want to continue (Type y or n)
 
y
 
Weight Balanced TreeOperations
 
1. insert
2. search
3. count nodes
4. check empty
5. clear
1
Enter integer element to insert and weight of the element
70 91
 
Post order : 1 63 70 24 14 5
Pre order : 5 1 14 24 70 63
In order : 1 5 14 24 63 70
Do you want to continue (Type y or n)
 
y
 
Weight Balanced TreeOperations
 
1. insert
2. search
3. count nodes
4. check empty
5. clear
2
Enter integer element to search
24
Search result : true
 
Post order : 1 63 70 24 14 5
Pre order : 5 1 14 24 70 63
In order : 1 5 14 24 63 70
Do you want to continue (Type y or n)
 
y
 
Weight Balanced TreeOperations
 
1. insert
2. search
3. count nodes
4. check empty
5. clear
3
Nodes = 6
 
Post order : 1 63 70 24 14 5
Pre order : 5 1 14 24 70 63
In order : 1 5 14 24 63 70
Do you want to continue (Type y or n)
 
y
 
Weight Balanced TreeOperations
 
1. insert
2. search
3. count nodes
4. check empty
5. clear
5
 
WeightBalancedTreeCleared
 
Post order :
Pre order :
In order :
Do you want to continue (Type y or n)
 
y
 
Weight Balanced TreeOperations
 
1. insert
2. search
3. count nodes
4. check empty
5. clear
4
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.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
advertisement
If you wish to look at all Java Programming examples, go to Java Programs.

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 & technical discussions at Telegram SanfoundryClasses.