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.
/** * Java Program to Implement Weight Balanced Tree **/ import java.util.Scanner; import java.util.Random; /** Class WBTNode **/ class WBTNode { WBTNode left, right; int weight, element; /** Constructor **/ public WBTNode(int ele, int wt) { this(ele, wt, null, null); } /** Constructor **/ public WBTNode(int ele, int wt, WBTNode left, WBTNode right) { this.element = ele; this.left = left; this.right = right; this.weight = wt; } } /** Class WeightBalancedTree **/ class WeightBalancedTree { private WBTNode root; private static WBTNode nil = new WBTNode(0, Integer.MAX_VALUE); /** Constructor **/ public WeightBalancedTree() { root = nil; } /** Function to check if tree is empty **/ public boolean isEmpty() { return root == nil; } /** clear tree **/ public void clear() { root = nil; } /** Functions to insert data **/ public void insert(int X, int WT) { root = insert(X, WT, root); } private WBTNode insert(int X, int WT, WBTNode T) { if (T == nil) return new WBTNode(X, WT, nil, nil); else if (X < T.element) { T.left = insert(X, WT, T.left); if (T.left.weight < T.weight) { WBTNode L = T.left; T.left = L.right; L.right = T; return L; } } else if (X > T.element) { T.right = insert(X, WT, T.right); if (T.right.weight < T.weight) { WBTNode R = T.right; T.right = R.left; R.left = T; return R; } } return T; } /** Functions to count number of nodes **/ public int countNodes() { return countNodes(root); } private int countNodes(WBTNode r) { if (r == nil) return 0; else { int l = 1; l += countNodes(r.left); l += countNodes(r.right); return l; } } /** Functions to search for an element **/ public boolean search(int val) { return search(root, val); } private boolean search(WBTNode r, int val) { boolean found = false; while ((r != nil) && !found) { int rval = r.element; if (val < rval) r = r.left; else if (val > rval) r = r.right; else { found = true; break; } found = search(r, val); } return found; } /** Function for inorder traversal **/ public void inorder() { inorder(root); } private void inorder(WBTNode r) { if (r != nil) { inorder(r.left); System.out.print(r.element +" "); inorder(r.right); } } /** Function for preorder traversal **/ public void preorder() { preorder(root); } private void preorder(WBTNode r) { if (r != nil) { System.out.print(r.element +" "); preorder(r.left); preorder(r.right); } } /** Function for postorder traversal **/ public void postorder() { postorder(root); } private void postorder(WBTNode r) { if (r != nil) { postorder(r.left); postorder(r.right); System.out.print(r.element +" "); } } } /** Class WeightBalancedTreeTest **/ public class WeightBalancedTreeTest { public static void main(String[] args) { Scanner scan = new Scanner(System.in); /** Creating object of WeightBalancedTree**/ WeightBalancedTree wbt = new WeightBalancedTree(); System.out.println("Weight Balanced TreeTest\n"); char ch; /** Perform tree operations **/ do { System.out.println("\nWeight Balanced TreeOperations\n"); System.out.println("1. insert "); System.out.println("2. search"); System.out.println("3. count nodes"); System.out.println("4. check empty"); System.out.println("5. clear"); int choice = scan.nextInt(); switch (choice) { case 1 : System.out.println("Enter integer element to insert and weight of the element"); wbt.insert( scan.nextInt(), scan.nextInt() ); break; case 2 : System.out.println("Enter integer element to search"); System.out.println("Search result : "+ wbt.search( scan.nextInt() )); break; case 3 : System.out.println("Nodes = "+ wbt.countNodes()); break; case 4 : System.out.println("Empty status = "+ wbt.isEmpty()); break; case 5 : System.out.println("\nWeightBalancedTreeCleared"); wbt.clear(); break; default : System.out.println("Wrong Entry \n "); break; } /** Display tree **/ System.out.print("\nPost order : "); wbt.postorder(); System.out.print("\nPre order : "); wbt.preorder(); System.out.print("\nIn order : "); wbt.inorder(); System.out.println("\nDo you want to continue (Type y or n) \n"); ch = scan.next().charAt(0); } while (ch == 'Y'|| ch == 'y'); } }
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
Related posts:
Java Program to Implement Slicker Algorithm that avoids Triangulation to Find Area of a Polygon
How to Replace Many if Statements in Java
Hướng dẫn tạo và sử dụng ThreadPool trong Java
New Features in Java 11
Spring Boot Configuration with Jasypt
Biểu thức Lambda trong Java 8 – Lambda Expressions
Java Program to Implement the String Search Algorithm for Short Text Sizes
Kết hợp Java Reflection và Java Annotations
Java Program to Implement the MD5 Algorithm
Java Program to Implement Binomial Heap
Comparing Strings in Java
Spring Boot - Actuator
Java Program to Implement Singly Linked List
The Registration Process With Spring Security
A Guide to Apache Commons Collections CollectionUtils
The Guide to RestTemplate
Java Program to Create a Random Linear Extension for a DAG
Java Program to Check Whether a Weak Link i.e. Articulation Vertex Exists in a Graph
Hướng dẫn sử dụng Java Generics
So sánh HashMap và HashSet trong Java
Java Program to Perform Cryptography Using Transposition Technique
Period and Duration in Java
Java Program to Implement the RSA Algorithm
Java Program to Implement Cartesian Tree
Java – Reader to String
An Intro to Spring Cloud Security
Java Program to Check Cycle in a Graph using Topological Sort
Custom Thread Pools In Java 8 Parallel Streams
Java Program to Implement Jarvis Algorithm
Java Perform to a 2D FFT Inplace Given a Complex 2D Array
Java 8 and Infinite Streams
Hướng dẫn Java Design Pattern – State