1. The purpose of this questions is to observe the behavior of binary search tre
ID: 3844510 • Letter: 1
Question
1. 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.
A 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 [231, 231 1]. For each n repeat the experiment several time and calculate the average height of the tree for each n.
B Compare the average height to log2(n + 1) 1 for each n. Calculateconstants that relate the average height to log2(n + 1) 1 for each n.Is there any relationship betweens constants for each n.
Here is the given code:
public class BinarySearchTree {
public static Node 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 static void main(String arg[]){
}
}
Public class Node{
int key;
Node left;
Node right;
public Node(int data){
key = data;
left = null;
right = null;
}
}
Explanation / Answer
public double height(Node node)
{
// here we are checking if the node is leaf node or it has no child node.
if (node == null)
return 0; // we will return o for this case
else
{
/* here we will compute the depth of each subtree i.e going left and right*/
double leftTreeDepth = height(node.left);
double rightTreeDepth = hieght(node.right);
/* now we will check whoch subtree is the larger now...i.e simply fiding the max amoung left or right and pass larger one*/
if (leftTreeDepth > rightTreeDepth)
return (leftTreeDepth + 1);
else
return (rightTreeDepth + 1);
}
}
I have provided a function to find the max height from the gicrn node, finding out the max subtree from that node.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.