For this problem, you will need the base AVL tree code and the test code below.
This problem will test your ability to traverse a tree and identify a collection of nodes. The AVLTree.java file contains the minimum amount of code for this problem. You will see there is a section designated as STUDENT CODE. This is where your method/methods should be placed. DO NOT MODIFY ANY OTHER CODE OR THE METHOD HEADER OF OUTER. You may add any additional private utility methods you see fit.
The OuterTest.java file contains the test code that will test different trees and produce output indicating whether you pass or fail a test. There are 10 tests. Each passed test is worth 10 points for a total of 100 points. Simply returning the result based on the tree given will not count as a solution. You must write an algorithm to calculate the solution. I will be using additional tests to ensure this is the case.
You must implement the method outer in AVLTree.java which returns a HashSet of the values, not the nodes, which are the outer elements of the tree. The outer elements of a tree are those which are the root, extreme left, extreme right, and those which can be reached from the bottom and are not "blocked". A "blocked" element is one that has both a left and right child. An example tree is the following.
Figure: see image.
In the above tree, the nodes which are red triangles are considered outer nodes. Node a is the root node. Nodes b, d, and h are the extreme left nodes. Nodes c and g are the extreme right nodes. Nodes i, e, j, k, and l are not blocked from the bottom. Only 1 node is not considered an outer node because it is blocked from the bottom. Your implementation should return a hashset of the elements contained in nodes a, b, d, h, i, e, j, k, l, g, and c.
In addition to the OuterTest.java file, here are images of each of the trees in OuterTest.java except for the empty tree which should just return an empty HashSet.
Single Node: see image.
Balance Tree 1: see image.
Balance Tree 2: see image.
Balance Tree 3: see image.
Balance Tree 4: see image.
Balance Tree 5 see image.
Balance Tree 6: see image.
Balance Tree 7: see image.
AVLTree.java
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;
public class AVLTree< T extends Comparable< ? super T > > {
private Node root;
private int size;
//Do Not Modify
public boolean isEmpty() {
return size == 0;
}
//Do Not Modify
public boolean add(T item) {
boolean added = false;
if(isEmpty()) {
root = new Node(item);
size += 1;
added = true;
} else {
added = add(null, root, item);
}
return added;
}
//Do Not Modify
private boolean add(Node parent, Node current, T data) {
boolean added = false;
if(current == null) {
int result = data.compareTo(parent.data);
if(result < 0) {
parent.left = new Node(data);
} else {
parent.right = new Node(data);
}
size += 1;
return true;
} else if(data.compareTo(current.data) < 0) {
added = add(current, current.left, data);
} else if(data.compareTo(current.data) > 0) {
added = add(current, current.right, data);
} else {
return false;
}
fixHeight(current);
if(added) {
rebalance(parent, current);
}
return added;
}
//Do Not Modify
private int getHeight(Node node) {
if(node == null) {
return -1;
}
return Math.max(node.leftHeight, node.rightHeight);
}
//Do Not Modify
private void fixHeight(Node node) {
if(node != null) {
node.leftHeight = getHeight(node.left) + 1;
node.rightHeight = getHeight(node.right) + 1;
}
}
//Do Not Modify
private void rebalance(Node parent, Node node) {
if(node == null) {
return;
}
//Left
if(balance(node) > 1) {
//Handle Case III
if(balance(node.left) < 0) {
//leftrotation
node.left = leftRotation(node.left);
}
//right rotation
if(parent == null) {
root = rightRotation(node);
} else if(parent.left == node) {
parent.left = rightRotation(node);
} else {
parent.right = rightRotation(node);
}
//Right
} else if(balance(node) < -1) {
//Handle Case IV
if(balance(node.right) > 0) {
node.right = rightRotation(node.right);
}
//left rotation
if(parent == null) {
root = leftRotation(node);
} else if(parent.left == node) {
parent.left = leftRotation(node);
} else {
parent.right = leftRotation(node);
}
}
}
//Do Not Modify
private int balance(Node node) {
int diff = node.leftHeight - node.rightHeight;
return diff;
}
//Do Not Modify
private Node rightRotation(Node n) {
Node c = n.left;
Node t2 = c.right;
c.right = n;
n.left = t2;
fixHeight(n);
fixHeight(c);
return c;
}
//Do Not Modify
private Node leftRotation(Node n) {
Node c = n.right;
Node t2 = c.left;
c.left = n;
n.right = t2;
fixHeight(n);
fixHeight(c);
return c;
}
/***********STUDENT CODE******************/
//Final Part 2 Question.
public Set< T > outer() {
return null;
}
/****************************************/
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("{ ");
if(!isEmpty()) {
Queue< Node > q = new LinkedList< >();
Node temp = root;
do {
sb.append(temp.data);
if(temp.left != null) {
q.add(temp.left);
}
if(temp.right != null) {
q.add(temp.right);
}
if(!q.isEmpty()) {
sb.append(", ");
temp = q.remove();
} else {
break;
}
}while(true);
}
sb.append(" }");
return sb.toString();
}
private class Node {
private Node left;
private Node right;
private int leftHeight;
private int rightHeight;
private T data;
public Node(T data) {
this.data = data;
}
}
}
OuterTest.java
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class OuterTest {
private static void testEmptyTree() {
System.out.println("************TESTING EMPTY TREE**********");
AVLTree< Integer > balanced = new AVLTree< >();
Integer nums[] = { };
for (Integer n : nums) {
balanced.add(n);
}
System.out.println("Testing tree: " + balanced);
List< Integer > ansList = Arrays.asList(new Integer[] { });
Set< Integer > ans = new HashSet< >();
for (Integer num : ansList) {
ans.add(num);
}
System.out.println("\tExpected:\t" + ans);
Set< Integer > outer = balanced.outer();
System.out.println("\tYour Output:\t" + outer);
System.out.println("\t" + (ans.equals(outer) ? "[+] PASS\n" : "[-] FAIL\n"));
}
private static void testSingleNode() {
System.out.println("************TESTING SINGLE NODE**********");
AVLTree< Integer > balanced = new AVLTree< >();
Integer nums[] = { 50 };
for (Integer n : nums) {
balanced.add(n);
}
System.out.println("Testing tree: " + balanced);
List< Integer > ansList = Arrays.asList(new Integer[] { 50 });
Set< Integer > ans = new HashSet< >();
for (Integer num : ansList) {
ans.add(num);
}
System.out.println("\tExpected:\t" + ans);
Set< Integer > outer = balanced.outer();
System.out.println("\tYour Output:\t" + outer);
System.out.println("\t" + (ans.equals(outer) ? "[+] PASS\n" : "[-] FAIL\n"));
}
private static void testThreeNodes() {
System.out.println("************TESTING THREE NODE TREE**********");
AVLTree< Integer > balanced = new AVLTree< >();
Integer nums[] = { 50, 25, 75 };
for (Integer n : nums) {
balanced.add(n);
}
System.out.println("Testing tree: " + balanced);
List< Integer > ansList = Arrays.asList(new Integer[] { 50, 25, 75 });
Set< Integer > ans = new HashSet< >();
for (Integer num : ansList) {
ans.add(num);
}
System.out.println("\tExpected:\t" + ans);
Set< Integer > outer = balanced.outer();
System.out.println("\tYour Output:\t" + outer);
System.out.println("\t" + (ans.equals(outer) ? "[+] PASS\n" : "[-] FAIL\n"));
}
private static void testBalancedTree7() {
System.out.println("************TESTING BALANCED TREE 7**********");
AVLTree< Integer > balanced = new AVLTree< >();
Integer nums[] = { 63, 22,78, 16, 28, 65, 85, 7, 21, 25, 51, 64, 72, 82, 92, 3, 13, 27, 31, 55, 69, 79, 83, 86, 33 };
for (Integer n : nums) {
balanced.add(n);
}
System.out.println("Testing tree: " + balanced);
List< Integer > ansList = Arrays.asList(new Integer[] { 63, 22, 16, 7, 3, 13, 21, 25, 27, 31, 33, 55, 64, 69, 72, 79, 83, 86, 92, 85, 78 });
Set< Integer > ans = new HashSet< >();
for (Integer num : ansList) {
ans.add(num);
}
System.out.println("\tExpected:\t" + ans);
Set< Integer > outer = balanced.outer();
System.out.println("\tYour Output:\t" + outer);
System.out.println("\t" + (ans.equals(outer) ? "[+] PASS\n" : "[-] FAIL\n"));
}
private static void testBalancedTree6() {
System.out.println("************TESTING BALANCED TREE 6**********");
AVLTree< Integer > balanced = new AVLTree< >();
Integer nums[] = { 36, 19, 73, 8, 22, 58, 75, 23, 94 };
for (Integer n : nums) {
balanced.add(n);
}
System.out.println("Testing tree: " + balanced);
List< Integer > ansList = Arrays.asList(new Integer[] { 36, 19, 8, 22, 23, 58, 75, 94, 73});
Set< Integer > ans = new HashSet< >();
for (Integer num : ansList) {
ans.add(num);
}
System.out.println("\tExpected:\t" + ans);
Set< Integer > outer = balanced.outer();
System.out.println("\tYour Output:\t" + outer);
System.out.println("\t" + (ans.equals(outer) ? "[+] PASS\n" : "[-] FAIL\n"));
}
private static void testBalancedTree5() {
System.out.println("************TESTING BALANCED TREE 5**********");
AVLTree< Integer > balanced = new AVLTree< >();
Integer nums[] = { 65, 26, 83, 15, 27, 68, 84, 21, 63, 80, 92 };
for (Integer n : nums) {
balanced.add(n);
}
System.out.println("Testing tree: " + balanced);
List< Integer > ansList = Arrays.asList(new Integer[] { 65, 26, 15, 21, 27, 63, 68, 80, 92, 84, 83 });
Set< Integer > ans = new HashSet< >();
for (Integer num : ansList) {
ans.add(num);
}
System.out.println("\tExpected:\t" + ans);
Set< Integer > outer = balanced.outer();
System.out.println("\tYour Output:\t" + outer);
System.out.println("\t" + (ans.equals(outer) ? "[+] PASS\n" : "[-] FAIL\n"));
}
private static void testBalancedTree4() {
System.out.println("************TESTING BALANCED TREE 4**********");
AVLTree< Integer > balanced = new AVLTree< >();
Integer nums[] = { 77, 26, 78, 32, 80 };
for (Integer n : nums) {
balanced.add(n);
}
System.out.println("Testing tree: " + balanced);
List< Integer > ansList = Arrays.asList(new Integer[] { 77, 26, 32, 80, 78 });
Set< Integer > ans = new HashSet< >();
for (Integer num : ansList) {
ans.add(num);
}
System.out.println("\tExpected:\t" + ans);
Set< Integer > outer = balanced.outer();
System.out.println("\tYour Output:\t" + outer);
System.out.println("\t" + (ans.equals(outer) ? "[+] PASS\n" : "[-] FAIL\n"));
}
private static void testBalancedTree3() {
System.out.println("************TESTING BALANCED TREE 3**********");
AVLTree< Integer > balanced = new AVLTree< >();
Integer nums[] = { 50, 25, 75, 15, 35, 70, 85, 20, 80 };
for (Integer n : nums) {
balanced.add(n);
}
System.out.println("Testing tree: " + balanced);
List< Integer > ansList = Arrays.asList(new Integer[] { 50, 25, 15, 20, 35, 70, 80, 85, 75 });
Set< Integer > ans = new HashSet< >();
for (Integer num : ansList) {
ans.add(num);
}
System.out.println("\tExpected:\t" + ans);
Set< Integer > outer = balanced.outer();
System.out.println("\tYour Output:\t" + outer);
System.out.println("\t" + (ans.equals(outer) ? "[+] PASS\n" : "[-] FAIL\n"));
}
private static void testBalancedTree2() {
System.out.println("************TESTING BALANCED TREE 2**********");
AVLTree< Integer > balanced = new AVLTree< >();
Integer nums[] = { 15, 6, 50, 4, 7, 23, 71, 5 };
for (Integer n : nums) {
balanced.add(n);
}
System.out.println("Testing tree: " + balanced);
List< Integer > ansList = Arrays.asList(new Integer[] { 15, 6, 4, 5, 7, 23, 71, 50 });
Set< Integer > ans = new HashSet< >();
for (Integer num : ansList) {
ans.add(num);
}
System.out.println("\tExpected:\t" + ans);
Set< Integer > outer = balanced.outer();
System.out.println("\tYour Output:\t" + outer);
System.out.println("\t" + (ans.equals(outer) ? "[+] PASS\n" : "[-] FAIL\n"));
}
private static void testBalancedTree1() {
System.out.println("************TESTING BALANCED TREE 1**********");
AVLTree< Integer > balanced = new AVLTree< >();
Integer nums[] = { 50, 25, 75, 20, 35, 70, 85, 15, 23, 30, 37, 65, 73, 80, 90 };
for (Integer n : nums) {
balanced.add(n);
}
System.out.println("Testing tree: " + balanced);
List< Integer > ansList = Arrays.asList(new Integer[] { 50, 25, 20, 15, 23, 30, 37, 65, 73, 80, 90, 85, 75 });
Set< Integer > ans = new HashSet< >();
for (Integer num : ansList) {
ans.add(num);
}
System.out.println("\tExpected:\t" + ans);
Set< Integer > outer = balanced.outer();
System.out.println("\tYour Output:\t" + outer);
System.out.println("\t" + (ans.equals(outer) ? "[+] PASS\n" : "[-] FAIL\n"));
}
public static void main(String[] args) {
testEmptyTree();
testSingleNode();
testThreeNodes();
testBalancedTree1();
testBalancedTree2();
testBalancedTree3();
testBalancedTree4();
testBalancedTree5();
testBalancedTree6();
testBalancedTree7();
}
}