The Given code is: public class BinarySearchTree { public static Node root; publ

Question

The Given code is:

public class BinarySearchTree {
  
   public static Node root;

   public static void main(String[] args){
       root = new Root(5);
       System.out.println(root);
   }
  
public BinarySearchTree(){ // Constructor
       this.root = null;
   }
  
   public boolean search(int id){
       Node current = root;
       while(current!=null){
           if(current.key==id){
               return true;
           }else if(current.key>id){
               current = current.left;
           }else{
               current = current.right;
           }
       }
       return false;
   }
  
  

  
public void insert(int id){
     
  
   }

public double height(){ // Compute the height of Binary Search
  
}

  
  
  
}

public class Node{
   int key;
   Node left;
   Node right;

   public Node(int data){
       key = data;
       left = null;
       right = null;
   }
}

1. BST, 40 pts The purpose of this questions is to observe the behavior of binary search trees when adding random integers. You have already given a code for binary search tree (see zip file BST a Add the function insert (int id) to the BST class. b Add a function height(Node x) to the BST class. This function will compute the height of a tree rooted at Node x. c Let n denote the number of nodes. Construct binary search trees for n 10, n 100, n 500, n 1000, n 2000, n 5000, n 10000 n 100000, n 1million. For each n you will pick uniformly random keys in the range I-231,231 -1]. For each n repeat the experiment several time and calculate the average height of the tree for each n. d Compare the average height to log2 n for each n. Calculate constants that relate the average height to log2 n for each n. Is there any rela tionship betweens constants for each n

Explanation / Answer

public class BinarySearchTree {
  
  
  
public static Node root;
public static void main(String[] args){
//root = new Node(5);
BinarySearchTree bs=new BinarySearchTree();
System.out.println("Inserting node 2 1 8");
bs.insert(2);
bs.insert(1);
bs.insert(8);

System.out.println("Height of BST is "+bs.height());

if(bs.search(1))
System.out.println("Element 1 found");
else
System.out.println("Element 1 not found");
  
if(bs.search(10))
System.out.println("Element 10 found");
else
System.out.println("Element 10 not found");

  
}
  
public BinarySearchTree(){ // Constructor
this.root = null;
}
  
public boolean search(int id){
Node current = root;
while(current!=null){
if(current.key==id){
return true;
}else if(current.key>id){
current = current.left;
}else{
current = current.right;
}
}
return false;
}
  
Node insertRec(Node root, int key) {
     
if (root == null) {
root = new Node(key);
return root;
}

if (key < root.key)
root.left = insertRec(root.left, key);
else if (key > root.key)
root.right = insertRec(root.right, key);

return root;
}
  
public void insert(int id){
   root = insertRec(root, id);

  
}
double computeHeight(Node node)
{
if (node == null)
return 0;
else
{
/* compute the depth of each subtree */
double lDepth = computeHeight(node.left);
double rDepth = computeHeight(node.right);

/* use the larger one */
if (lDepth > rDepth)
return (lDepth + 1);
else
return (rDepth + 1);
}
}
public double height(){ // Compute the height of Binary Search
   return computeHeight(root);
  
}
  
  
  
}

============================================================================

Output:(eclipse)

Inserting node 2 1 8
Height of BST is 2.0
Element 1 found
Element 10 not found

==============================================================

.Let me know if you have any problem

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.