Question

Homework assignment number 13 Binary search trees have their best performance when they are balanced, which means that at each noden, the size of the left subtree of n is within one of the size of the right subtree of n. Write a program thatwill take an array of generic values that are in sorted order in the array, create a binary search tree, and put the values in the array into the tree. Your binary search tree should be complete ("complete" as defined in chapter 24). Or put another way, it should have the fewest number of levels and still be "complete".Use the following array: "A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M","N".Remember, your code is to handle generic data types, not just strings. So while I want you to use the specified array of strings, your program should work if I choose to use an array of Integers, or Characters. Printout the values from the tree (not the array) in a tree fashion so that I can readily see the tree structure, something like this:HD LBFJN A C EGIK M-Name the file that contains the main method TreeDriver.ja

Answer 1

See explaination for the program code

Step-by-step explanation:

Code below:

package trees;

import java.util.NoSuchElementException;

public class TreeDriver<T extends Comparable<? super T>> {

private Entry<T> root;

publicTreeDriver() {

root = null;

}

public static<T extends Comparable<? super T>>TreeDriver<T> createTestTree() {

return newTreeDriver<T>();

}

public void insert(T value) {

root = insert(value, root);

}

public void remove(T value) {

root = remove(value, root);

}

public boolean contains(T value) {

return valueOf(find(value, root)) != null;

}

private T valueOf(Entry<T> entry) {

return entry == null ? null : entry.element;

}

private Entry<T> insert(T value, Entry<T> entry) {

if (entry == null)

entry = new Entry<T>(value);

else if (value.compareTo(entry.element) < 0)

entry.left = insert(value, entry.left);

else if (value.compareTo(entry.element) > 0)

entry.right = insert(value, entry.right);

else

throw new RuntimeException("Duplicate Entry : " + value.toString());

return entry;

}

private Entry<T> remove(T value, Entry<T> entry) {

if (entry == null)

throw new NoSuchElementException("Entry not found : " + value.toString());

if (value.compareTo(entry.element) < 0)

entry.left = remove(value, entry.left);

else if (value.compareTo(entry.element) > 0)

entry.right = remove(value, entry.right);

else {

// Entry found.

if (entry.left != null && entry.right != null) {

// Replace with in-order successor (the left-most child of the right subtree)

entry.element = findMin(entry.right).element;

entry.right = removeInorderSuccessor(entry.right);

// Replace with in-order predecessor (the right-most child of the left subtree)

// entry.element = findMax(entry.left).element;

// entry.left = removeInorderPredecessor(entry.left);

} else

entry = (entry.left != null) ? entry.left : entry.right;

}

return entry;

}

private Entry<T> removeInorderSuccessor(Entry<T> entry) {

if (entry == null)

throw new NoSuchElementException();

else if (entry.left != null) {

entry.left = removeInorderSuccessor(entry.left);

return entry;

} else

return entry.right;

}

private Entry<T> removeInorderPredecessor(Entry<T> entry) {

if (entry == null)

throw new NoSuchElementException();

else if (entry.right != null) {

entry.right = removeInorderPredecessor(entry.right);

return entry;

} else

return entry.left;

}

private Entry<T> findMin(Entry<T> entry) {

if (entry != null)

while (entry.left != null)

entry = entry.left;

return entry;

}

private Entry<T> findMax(Entry<T> entry) {

if (entry != null)

while (entry.right != null)

entry = entry.right;

return entry;

}

private Entry<T> find(T value, Entry<T> entry) {

while (entry != null) {

if (value.compareTo(entry.element) < 0)

entry = entry.left;

else if (value.compareTo(entry.element) > 0)

entry = entry.right;

else

return entry;

}

return null;

}

private void printInOrder(Entry<T> entry) {

if (entry != null) {

printInOrder(entry.left);

System.out.println(entry.element);

printInOrder(entry.right);

}

}

public void printInOrder() {

printInOrder(root);

}

private static class Entry<T extends Comparable<? super T>> {

T element;

Entry<T> left;

Entry<T> right;

Entry(T theElement) {

element = theElement;

left = right = null;

}

}

private static class Test implements Comparable<Test> {

private String value;

public Test(String value) {

this.value = value;

}

public String toString() {

return value;

}

atOverride // Replace the at with at symbol

public int compareTo(Test o) {

return this.value.compareTo(o.toString());

}

}

private static class Test1 extends Test {

public Test1(String value) {

super(value);

}

}

public static vo id main(String[] args) {

TreeDriver<Test> tree =TreeDriver.createTestTree();

int size = 20;

for (int i = 0; i <= size; i++) {

tree.insert(new Test1(String.valueOf(i)));

}

tree.insert(new Test1("100"));

tree.remove(new Test1("10"));

tree.remove(new Test1(String.valueOf(15)));

tree.remove(new Test1(String.valueOf(20)));

tree.printInOrder();

System.out.println("Contains (10) : " + tree.contains(new Test1("10")));

System.out.println("Contains (11) : " + tree.contains(new Test1(String.valueOf(11))));

}

}