Java Program to Implement Range Tree

«
»
This is a java program to implement Range Tree. A range tree on a set of 1-dimensional points is a balanced binary search tree on those points. The points stored in the tree are stored in the leaves of the tree; each internal node stores the largest value contained in its left subtree. A range tree on a set of points in d-dimensions is a recursively defined multi-level binary search tree. Each level of the data structure is a binary search tree on one of the d-dimensions. The first level is a binary search tree on the first of the d-coordinates. Each vertex v of this tree contains an associated structure that is a (d-1)-dimensional range tree on the last (d-1)-coordinates of the points stored in the subtree of v.

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

  1. //This is a java program to implement Range Tree
  2. import java.util.Random;
  3. import java.util.Scanner;
  4.  
  5. class BSTNodes
  6. {
  7.     BSTNodes left, right;
  8.     int      data;
  9.  
  10.     public BSTNodes()
  11.     {
  12.         left = null;
  13.         right = null;
  14.         data = 0;
  15.     }
  16.  
  17.     public BSTNodes(int n)
  18.     {
  19.         left = null;
  20.         right = null;
  21.         data = n;
  22.     }
  23.  
  24.     public void setLeft(BSTNodes n)
  25.     {
  26.         left = n;
  27.     }
  28.  
  29.     public void setRight(BSTNodes n)
  30.     {
  31.         right = n;
  32.     }
  33.  
  34.     public BSTNodes getLeft()
  35.     {
  36.         return left;
  37.     }
  38.  
  39.     public BSTNodes getRight()
  40.     {
  41.         return right;
  42.     }
  43.  
  44.     public void setData(int d)
  45.     {
  46.         data = d;
  47.     }
  48.  
  49.     public int getData()
  50.     {
  51.         return data;
  52.     }
  53. }
  54.  
  55. class BST
  56. {
  57.     private BSTNodes root;
  58.  
  59.     public BST()
  60.     {
  61.         root = null;
  62.     }
  63.  
  64.     public boolean isEmpty()
  65.     {
  66.         return root == null;
  67.     }
  68.  
  69.     public void insert(int data)
  70.     {
  71.         root = insert(root, data);
  72.     }
  73.  
  74.     private BSTNodes insert(BSTNodes node, int data)
  75.     {
  76.         if (node == null)
  77.             node = new BSTNodes(data);
  78.         else
  79.         {
  80.             if (data <= node.getData())
  81.                 node.left = insert(node.left, data);
  82.             else
  83.                 node.right = insert(node.right, data);
  84.         }
  85.         return node;
  86.     }
  87.  
  88.     public void delete(int k)
  89.     {
  90.         if (isEmpty())
  91.             System.out.println("Tree Empty");
  92.         else if (search(k) == false)
  93.             System.out.println("Sorry " + k + " is not present");
  94.         else
  95.         {
  96.             root = delete(root, k);
  97.             System.out.println(k + " deleted from the tree");
  98.         }
  99.     }
  100.  
  101.     private BSTNodes delete(BSTNodes root, int k)
  102.     {
  103.         BSTNodes p, p2, n;
  104.         if (root.getData() == k)
  105.         {
  106.             BSTNodes lt, rt;
  107.             lt = root.getLeft();
  108.             rt = root.getRight();
  109.             if (lt == null && rt == null)
  110.                 return null;
  111.             else if (lt == null)
  112.             {
  113.                 p = rt;
  114.                 return p;
  115.             } else if (rt == null)
  116.             {
  117.                 p = lt;
  118.                 return p;
  119.             } else
  120.             {
  121.                 p2 = rt;
  122.                 p = rt;
  123.                 while (p.getLeft() != null)
  124.                     p = p.getLeft();
  125.                 p.setLeft(lt);
  126.                 return p2;
  127.             }
  128.         }
  129.         if (k < root.getData())
  130.         {
  131.             n = delete(root.getLeft(), k);
  132.             root.setLeft(n);
  133.         } else
  134.         {
  135.             n = delete(root.getRight(), k);
  136.             root.setRight(n);
  137.         }
  138.         return root;
  139.     }
  140.  
  141.     public int countNodes()
  142.     {
  143.         return countNodes(root);
  144.     }
  145.  
  146.     private int countNodes(BSTNodes r)
  147.     {
  148.         if (r == null)
  149.             return 0;
  150.         else
  151.         {
  152.             int l = 1;
  153.             l += countNodes(r.getLeft());
  154.             l += countNodes(r.getRight());
  155.             return l;
  156.         }
  157.     }
  158.  
  159.     public boolean search(int val)
  160.     {
  161.         return search(root, val);
  162.     }
  163.  
  164.     private boolean search(BSTNodes r, int val)
  165.     {
  166.         boolean found = false;
  167.         while ((r != null) && !found)
  168.         {
  169.             int rval = r.getData();
  170.             if (val < rval)
  171.                 r = r.getLeft();
  172.             else if (val > rval)
  173.                 r = r.getRight();
  174.             else
  175.             {
  176.                 found = true;
  177.                 break;
  178.             }
  179.             found = search(r, val);
  180.         }
  181.         return found;
  182.     }
  183.  
  184.     public void inorder()
  185.     {
  186.         inorder(root);
  187.     }
  188.  
  189.     private void inorder(BSTNodes r)
  190.     {
  191.         if (r != null)
  192.         {
  193.             inorder(r.getLeft());
  194.             System.out.print(r.getData() + " ");
  195.             inorder(r.getRight());
  196.         }
  197.     }
  198.  
  199.     public void preorder()
  200.     {
  201.         preorder(root);
  202.     }
  203.  
  204.     private void preorder(BSTNodes r)
  205.     {
  206.         if (r != null)
  207.         {
  208.             System.out.print(r.getData() + " ");
  209.             preorder(r.getLeft());
  210.             preorder(r.getRight());
  211.         }
  212.     }
  213.  
  214.     public void postorder()
  215.     {
  216.         postorder(root);
  217.     }
  218.  
  219.     private void postorder(BSTNodes r)
  220.     {
  221.         if (r != null)
  222.         {
  223.             postorder(r.getLeft());
  224.             postorder(r.getRight());
  225.             System.out.print(r.getData() + " ");
  226.         }
  227.     }
  228. }
  229.  
  230. public class RangeTree
  231. {
  232.     public static void main(String[] args)
  233.     {
  234.         Scanner scan = new Scanner(System.in);
  235.         BST bst = new BST();
  236.         System.out
  237.                 .println("Range Tree in One Dimensional points(Binary Search Tree)\n");
  238.         Random random = new Random();
  239.         int N = 10;
  240.         for (int i = 0; i < N; i++)
  241.             bst.insert(Math.abs(random.nextInt(100)));
  242.  
  243.         char ch;
  244.         do
  245.         {
  246.             System.out.print("Operations\n");
  247.             System.out.println("1. Print Tree ");
  248.             System.out.println("2. Delete");
  249.             System.out.println("3. Search");
  250.             System.out.println("4. Count Nodes");
  251.             System.out.println("5. Check Empty");
  252.  
  253.             int choice = scan.nextInt();
  254.             switch (choice)
  255.             {
  256.                 case 1:
  257.                     System.out.print("\nPost order : ");
  258.                     bst.postorder();
  259.                     System.out.print("\nPre order  : ");
  260.                     bst.preorder();
  261.                     System.out.print("\nIn order   : ");
  262.                     bst.inorder();
  263.                     break;
  264.                 case 2:
  265.                     System.out.println("Enter integer element to delete");
  266.                     bst.delete(scan.nextInt());
  267.                     break;
  268.                 case 3:
  269.                     System.out.println("Enter integer element to search");
  270.                     System.out.println("Search result : "
  271.                             + bst.search(scan.nextInt()));
  272.                     break;
  273.                 case 4:
  274.                     System.out.println("Nodes = " + bst.countNodes());
  275.                     break;
  276.                 case 5:
  277.                     System.out.println("Empty status = " + bst.isEmpty());
  278.                     break;
  279.                 default:
  280.                     System.out.println("Wrong Entry \n ");
  281.                     break;
  282.             }
  283.  
  284.             System.out.println("\nDo you want to continue (Type y or n) \n");
  285.             ch = scan.next().charAt(0);
  286.         } while (ch == 'Y' || ch == 'y');
  287.         scan.close();
  288.     }
  289. }

Output:

advertisement
$ javac RangeTree.java
$ java RangeTree
 
Range Tree in One Dimensional points(Binary Search Tree)
 
Operations
1. Print Tree 
2. Delete
3. Search
4. Count Nodes
5. Check Empty
1
 
Post order : 15 14 12 29 49 47 22 92 91 7 
Pre order  : 7 91 22 12 14 15 47 29 49 92 
In order   : 7 12 14 15 22 29 47 49 91 92 
Do you want to continue (Type y or n) 
 
y
Operations
1. Print Tree 
2. Delete
3. Search
4. Count Nodes
5. Check Empty
2
Enter integer element to delete
7
7 deleted from the tree
 
Do you want to continue (Type y or n) 
 
y
Operations
1. Print Tree 
2. Delete
3. Search
4. Count Nodes
5. Check Empty
3
Enter integer element to search
91
Search result : true
 
Do you want to continue (Type y or n) 
 
y
Operations
1. Print Tree 
2. Delete
3. Search
4. Count Nodes
5. Check Empty
4
Nodes = 9
 
Do you want to continue (Type y or n) 
 
y
Operations
1. Print Tree 
2. Delete
3. Search
4. Count Nodes
5. Check Empty
5
Empty status = false
 
Do you want to continue (Type y or n) 
 
n

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
advertisement

Here’s the list of Best Books in Java Programming, Data Structures and Algorithms.

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.