Question
Once you have all the structures working as intended, it is time to compare the performances of the 2. Use runBenchmark() to start. a. First,
Once you have all the structures working as intended, it is time to compare the performances of the 2. Use runBenchmark() to start.
a. First, generate an increasing number (N) of random integers (1000, 5000, 10000, 50000, 75000, 100000, 500000 or as far as your computing power will let you)
i. Time and print how long it takes to insert the random integers into an initially empty BST. Do not print the tree. You can get a random list using the java class Random, located in java.util.Random. To test the speed of the insertion algorithm, you should use the System.currentTimeMillis() method, which returns a long that contains the current time (in milliseconds). Call System.currentTimeMillis() before and after the algorithm runs and subtract the two times. (Instant.now() is an alternative way of recording the time.)
ii. Time and print how long it takes to insert the same random integers into an initially empty AVL tree. Do not print the tree.
iii. If T(N) is the time function, how does the growth of TBST(N) compare with the growth of TAVL(N)? Plot a simple graph to of time against N for the two types of BSTs to visualize your results. b. Second, generate a list of k random integers. k is also some large value.
i. Time how long it takes to search your various N-node BSTs for all k random integers. It does not matter whether the search succeeds.
ii. Time how long it takes to search your N-node AVL trees for the same k random integers.
iii. Compare the growth rates of these two search time-functions with a graph the same way you did in part a.
public class BinarySearchTree
protected BinaryNode
public BinarySearchTree() {
root = null;
}
/**
* Insert into the tree; duplicates are ignored.
*
* @param x the item to insert.
* @param root
* @return
*/
protected BinaryNode
// If the root is null, we've reached an empty leaf node, so we create a new node
// with the value x and return it
if (root == null) {
return new BinaryNode<>(x, null, null);
}
// Compare the value of x to the value stored in the root node
int compareResult = x.compareTo(root.element);
// If x is less than the value stored in the root node, we insert it into the left subtree
if (compareResult < 0) {
root.left = insert(x, root.left);
}
// If x is greater than the value stored in the root node, we insert it into the right subtree
else if (compareResult > 0) {
root.right = insert(x, root.right);
}
// If x is equal to the value stored in the root node, we ignore it since the tree does not allow duplicates
return root;
}
/**
* Counts the number of leaf nodes in this tree.
*
* @param t The root of the tree.
* @return
*/
private int countLeafNodes(BinaryNode
// If the root is null, it means the tree is empty, so we return 0
if (root == null) {
return 0;
}
// If the root has no children, it means it is a leaf node, so we return 1
if (root.left == null && root.right == null) {
return 1;
}
// If the root has children, we recursively count the number of leaf nodes in both the
// left and right subtrees and return the sum
return countLeafNodes(root.left) + countLeafNodes(root.right);
}
/**
* Checks if the tree is a full tree.
*
* @param t The root of the tree.
* @return
*/
private boolean isFull(BinaryNode
// If the root is null, it means the tree is empty, so it is not full
if (root == null) {
return false;
}
// If the root has no children, it means the tree only has one node, which makes it a full tree
if (root.left == null && root.right == null) {
return true;
}
// If the root has only one child, it is not a full tree
if (root.left == null || root.right == null) {
return false;
}
// If the root has two children, we recursively check both the left and right subtrees
// to see if they are both full
return isFull(root.left) && isFull(root.right);
}
public void insert(AnyType x) {
root = insert(x, root);
}
/**
* Counts the number of leaf nodes in a tree.
*
* @return
*/
public int countLeafNodes() {
return countLeafNodes(root);
}
/**
* Checks if the tree is full.
*
* @return
*/
public boolean isFull() {
return isFull(root);
}
/**
* Remove from the tree. Nothing is done if x is not found.
*
* @param x the item to remove.
*/
public void remove(AnyType x) {
root = remove(x, root);
}
/**
* Internal method to remove from a subtree.
*
* @param x the item to remove.
* @param root the node that roots the subtree.
* @return the new root of the subtree.
*/
protected BinaryNode
// If item not found, do nothing.
if (root == null) {
return root;
}
int compareResult = x.compareTo(root.element);
if (compareResult < 0) {
root.left = remove(x, root.left);
} else if (compareResult > 0) {
root.right = remove(x, root.right);
} // Two children.
else if (root.left != null && root.right != null) {
root.element = findMin(root.right).element;
root.right = remove(root.element, root.right);
} // Zero or one child.
else {
root = (root.left != null) ? root.left : root.right;
}
return root;
}
/**
* Find an item in the tree.
*
* @param x the item to search for.
* @return true if not found.
*/
public boolean contains(AnyType x) {
return contains(x, root);
}
private boolean contains(AnyType x, BinaryNode
if (root == null) {
return false;
}
int compareResult = x.compareTo(root.element);
if (compareResult < 0) {
return contains(x, root.left);
} else if (compareResult > 0) {
return contains(x, root.right);
} else {
return true; // Match with current node
}
}
/**
* Find the smallest item in the tree.
*
* @return smallest item or null if empty.
* @throws Exception
*/
public AnyType findMin() throws Exception {
if (isEmpty()) {
throw new Exception();
}
return findMin(root).element;
}
private BinaryNode
if (root == null) {
return null;
} else if (root.left == null) {
return root; // found the leftmost node
} else {
return findMin(root.left);
}
}
/**
* Test if the tree is logically empty.
*
* @return true if empty, false otherwise.
*/
public boolean isEmpty() {
return root == null;
}
/**
* Calculate the height of the tree.
*
* @return the height.
*/
public int height() {
return height(this.root);
}
/**
* Internal method to compute height of a subtree.
*
* @param root the node that roots the subtree.
* @return
*/
protected int height(BinaryNode
return root == null ? -1
: 1 + Math.max(height(root.left), height(root.right));
}
public BinaryNode
return root;
}
public void setRoot(BinaryNode
this.root = root;
}
public void printSideways(String label) {
System.out.println(
" -------------------------------" + label + "----------------------------");
printSideways(root, "");
}
private void printSideways(BinaryNode root,
String indent) {
if (root != null) {
printSideways(root.right, indent + " ");
System.out.println(indent + root.element);
printSideways(root.left, indent + " ");
}
}
}
public class AVLTree
public AVLTree() { super(); this.BALANCE_FACTOR = 1; }
private final int BALANCE_FACTOR;
/** * * @param root The root of the BST * @return The balanced tree. */ private BinaryNode
private BinaryNode
if (root == null) {
return root;
}
int heightDiff = height(root.left) - height(root.right);
if (heightDiff > BALANCE_FACTOR) {
// case 1: left-left
if (height(root.left.left) >= height(root.left.right)) {
root = rotateRightWithLeftChild(root);
}
// case 2: left-right
else {
root = doubleLeftRight(root);
}
} else if (heightDiff < -BALANCE_FACTOR) {
// case 3: right-right
if (height(root.right.right) >= height(root.right.left)) {
root = rotateLeftWithRightChild(root);
}
// case 4: right-left
else {
root = doubleRightLeft(root);
}
}
return root;
}
return root; }
/** * Rotate binary tree node with left child. For AVL trees, this is a single * rotation for case 1. */ private BinaryNode
return k1; }
/** * Rotate binary tree node with right child. For AVL trees, this is a single * rotation for case 4. */ private BinaryNode
BinaryNode
return k2; }
/** * Double rotate binary tree node: first left child with its right child; * then node k3 with new left child. For AVL trees, this is a double * rotation for case 2. */ private BinaryNode
k3.left = rotateLeftWithRightChild(k3.left);
return rotateRightWithLeftChild(k3); }
/** * Double rotate binary tree node: first right child with its left child; * then node k1 with new right child. For AVL trees, this is a double * rotation for case 3. */ private BinaryNode
k1.right = rotateRightWithLeftChild(k1.right);
return rotateLeftWithRightChild(k1); }
/** * Insert into the tree; duplicates are ignored. * * @param x the item to insert. */ @Override public void insert(AnyType x) { root = insert(x, root); }
/** * Internal method to insert into a subtree. * * @param x the item to insert. * @param root the node that roots the subtree. * @return the new root of the subtree. */ @Override protected BinaryNode
/** * Remove from the tree. Nothing is done if x is not found. * * @param x the item to remove. */ @Override public void remove(AnyType x) { root = remove(x, root); }
/** * Internal method to remove from a subtree. * * @param x the item to remove. * @param root the node that roots the subtree. * @return the new root of the subtree. */ @Override protected BinaryNode
return balance(super.remove(x, root)); }
public void checkBalance() { checkBalance(root); }
private int checkBalance(BinaryNode
return height(root); }
}
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access with AI-Powered Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started