Q1. If the array size n is fixed, what does a worst-case input array (resulting in the maximum total number of key comparisons) look like? Q2. If the array size n is fixed, what does a best-case input array (resulting in the minimum total number of key comparisons) look like?
I'm having issue understanding how to go on with this question.
Q1. If the array size n is fixed, what does a worst-case input array (resulting in the maximum total
number of key comparisons) look like?
Q2. If the array size n is fixed, what does a best-case input array (resulting in the minimum total number
of key comparisons) look like?
In particular, set n = 15. Run your program by creating a worst-case input array and a best-case input
array. For each case, include the following in the “README” file.
•Take a screenshot of your program’s output;
Draw the BST after all 15 keys are inserted.
Write your answers to Q1 and Q2 for general n as part of the summary of your testing results in the
this is my code for it
class BST
{
class Node
{
int key;
Node left, right;
public Node(int item)
{
key = item;
left = right = null;
}
}
// Root of BST
Node root;
int count=0;
// Constructor
BST()
{
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;
}
count++;
if (key < root.key) {
root.left = insertRec(root.left, key);
} else {
root.right = insertRec(root.right, key);
}
return root;
}
void inorderRec(Node root)
{
if (root != null)
{
inorderRec(root.left);
System.out.print(" "+ root.key +" ");
inorderRec(root.right);
}
}
void treeins(int arr[])
{
for(int i = 0; i < arr.length; i++)
{
insert(arr[i]);
}
}
}
public class PAssign07{
public static void main(String[] args)
{
BST tree = new BST();
int arr[] = {4, 1, 3, 2};
int key=3;
int [] a = new int[15];
for(int i = 0; i <a.length; i++){
a[i] = (int)(Math.random()*1000 + 1);
}
tree.treeins(arr);
System.out.printf("array size %d%n",arr.length);
System.out.print("sorted array pre insertion: ");
tree.inorderRec(tree.root);
System.out.printf("%nKey comparision differences in pre insertion: ");
System.out.println(tree.count);
System.out.printf("element inserted: ");
tree.insert(key);
System.out.println(key);
System.out.printf("sorted array post insertion: ");
tree.inorderRec(tree.root);
System.out.printf("\nkey comparision difference in post insertion: ");
System.out.println(tree.count);
}
}
Trending now
This is a popular solution!
Step by step
Solved in 4 steps with 4 images
