This is java. I need a BST thats I will be able to do the following things below
ID: 3606656 • Letter: T
Question
This is java. I need a BST thats I will be able to do the following things below.
Run empirical studies to compute the average and standard deviation of the average length of a path to a random node in a BST built by insertion of N random keys into an initially empty tree, for N from 100 to 12,800 (with N doubling from 100, 200, 400 ...)
Details:
- I recommend developing your own BST implementation in MyBST.java, building on the code in the BST class provided in algs4.jar.
- For each tree size, do 1000 trial trees. That means: create an empty BST object, generate N keys, and put them into the BST.
- Once you have a filled BST, the average path length on this tree (mt) is the sum of all node depths divided by the number of nodes, plus 1. You'll need to create a function in your BST implementation to compute and return this.
- I'm asking you to compute the average and standard deviations of those mt values.
- Print those values to a table, captured in your README file
Explanation / Answer
class BinarySearchTree {
/* Class containing left and right child of current node and key value*/
class Node {
int key;
Node left, right;
public Node(int item) {
key = item;
left = right = null;
}
}
// Root of BST
Node root;
BinarySearchTree() {
root = null;
}
void insert(int key) {
root = insertRec(root, key);
}
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;
}
void inorder() {
inorderRec(root);
}
void inorderRec(Node root) {
if (root != null) {
inorderRec(root.left);
System.out.print(root.key + " ");
inorderRec(root.right);
}
}
void calculatedeviation(int mu){
if (root != null) {
inorderRec(root.left);
System.out.println(root.key + " - " +(root.key - mu)*(root.key - mu));
inorderRec(root.right);
}
}
public static void main(String[] args) {
BinarySearchTree tree = new BinarySearchTree();
int sum = 0;
int count = 0;
int avg = 0;
for(int i = 100; i<= 12800; i*2){
tree.insert(i);
sum += i;
count++;
}
System.out.println("Inorder Tree Travesal:");
tree.inorder();
avg = sum/count;
System.out.println("Average Node Value: "+ avg);
System.out.println("Standard Deviation:");
tree.calculatedeviation(avg);
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.