Instructions
Requirements and Specifications
Source Code
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.stream.Collectors;
import org.junit.Assert;
import org.junit.Test;
import static org.junit.Assert.*;
/**
* Binary Search Tree implementation with a Node inner class for representing
* the nodes within a binary search tree. You can use this class' insert
* method to build a binary search tree, and its toString method to display
* the level order (breadth first) traversal of values in that tree.
*/
public class BinarySearchTree> {
/**
* This class represents a node holding a single value within a binary tree
* the parent, left, and right child references are always be maintained.
*/
protected static class Node {
public T data;
public Node parent; // null for root node
public Node leftChild;
public Node rightChild;
public Node(T data) { this.data = data; }
/**
* @return true when this node has a parent and is the left child of
* that parent, otherwise return false
*/
public boolean isLeftChild() {
return parent != null && parent.leftChild == this;
}
/**
* This method performs a level order traversal of the tree rooted
* at the current node. The string representations of each data value
* within this tree are assembled into a comma separated string within
* brackets (similar to many implementations of java.util.Collection).
* @return string containing the values of this tree in level order
*/
@Override
public String toString() { // display subtree in order traversal
String output = "[";
LinkedList> q = new LinkedList<>();
q.add(this);
while(!q.isEmpty()) {
Node next = q.removeFirst();
if(next.leftChild != null) q.add(next.leftChild);
if(next.rightChild != null) q.add(next.rightChild);
output += next.data.toString();
if(!q.isEmpty()) output += ", ";
}
return output + "]";
}
}
protected Node root; // reference to root node of tree, null when empty
/**
* Performs a naive insertion into a binary search tree: adding the input
* data value to a new node in a leaf position within the tree. After
* this insertion, no attempt is made to restructure or balance the tree.
* This tree will not hold null references, nor duplicate data values.
* @param data to be added into this binary search tree
* @throws NullPointerException when the provided data argument is null
* @throws IllegalArgumentException when the tree already contains data
*/
public void insert(T data) throws NullPointerException,
IllegalArgumentException {
// null references cannot be stored within this tree
if(data == null) throw new NullPointerException(
"This RedBlackTree cannot store null references.");
Node newNode = new Node<>(data);
if(root == null) { root = newNode; } // add first node to an empty tree
else insertHelper(newNode,root); // recursively insert into subtree
}
/**
* Recursive helper method to find the subtree with a null reference in the
* position that the newNode should be inserted, and then extend this tree
* by the newNode in that position.
* @param newNode is the new node that is being added to this tree
* @param subtree is the reference to a node within this tree which the
* newNode should be inserted as a descenedent beneath
* @throws IllegalArgumentException when the newNode and subtree contain
* equal data references (as defined by Comparable.compareTo())
*/
private void insertHelper(Node newNode, Node subtree) {
int compare = newNode.data.compareTo(subtree.data);
// do not allow duplicate values to be stored within this tree
if(compare == 0) throw new IllegalArgumentException(
"This RedBlackTree already contains that value.");
// store newNode within left subtree of subtree
else if(compare < 0) {
if(subtree.leftChild == null) { // left subtree empty, add here
subtree.leftChild = newNode;
newNode.parent = subtree;
// otherwise continue recursive search for location to insert
} else insertHelper(newNode, subtree.leftChild);
}
// store newNode within the right subtree of subtree
else {
if(subtree.rightChild == null) { // right subtree empty, add here
subtree.rightChild = newNode;
newNode.parent = subtree;
// otherwise continue recursive search for location to insert
} else insertHelper(newNode, subtree.rightChild);
}
}
/**
* This method performs a level order traversal of the tree. The string
* representations of each data value within this tree are assembled into a
* comma separated string within brackets (similar to many implementations
* of java.util.Collection, like java.util.ArrayList, LinkedList, etc).
* @return string containing the values of this tree in level order
*/
@Override
public String toString() { return root.toString(); }
/**
* Performs the rotation operation on the provided nodes within this BST.
* When the provided child is a leftChild of the provided parent, this
* method will perform a right rotation (sometimes called a left-right
* rotation). When the provided child is a rightChild of the provided
* parent, this method will perform a left rotation (sometimes called a
* right-left rotation). When the provided nodes are not related in one
* of these ways, this method will throw an IllegalArgumentException.
* @param child is the node being rotated from child to parent position
* (between these two node arguments)
* @param parent is the node being rotated from parent to child position
* (between these two node arguments)
* @throws IllegalArgumentException when the provided child and parent
* node references are not initially (pre-rotation) related that way
*/
private void rotate(Node child, Node parent) throws IllegalArgumentException {
if (child == null || parent== null || child.parent != parent) {
throw new IllegalArgumentException();
}
if (child.isLeftChild()) {
Node childRightChild = child.rightChild;
if (childRightChild != null) {
childRightChild.parent = parent;
}
parent.leftChild = childRightChild;
if (parent.parent == null) {
root = child;
}
else {
if (parent.isLeftChild()) {
parent.parent.leftChild = child;
}
else {
parent.parent.rightChild = child;
}
}
parent.parent = child;
child.rightChild = parent;
}
else {
Node childLeftChild = child.leftChild;
if (childLeftChild != null) {
childLeftChild.parent = parent;
}
parent.rightChild = childLeftChild;
if (parent.parent == null) {
root = child;
}
else {
if (parent.isLeftChild()) {
parent.parent.leftChild = child;
}
else {
parent.parent.rightChild = child;
}
}
parent.parent = child;
child.leftChild = parent;
}
}
// For the next two test methods, review your notes from the Module 4: Red
// Black Tree Insertion Activity. Questions one and two in that activity
// presented you with an initial BST and then asked you to trace the
// changes that would be applied as a result of performing different
// rotations on that tree. For each of the following tests, you'll first
// create the initial BST that you performed each of these rotations on.
// Then apply the rotations described in that activity: the right-rotation
// in the Part1 test below, and the left-rotation in the Part2 test below.
// Then ensure that these tests fail if and only if the level ordering of
// tree values dose not match the order that you came up with in that
// activity.
@Test
public void week04ActivityTestPart1() {
// Module 04: Red Black Tree Insert Activity - Step 1 (right rotation).
BinarySearchTree tree = new BinarySearchTree<>();
List dataOrder = new ArrayList<>();
dataOrder.add(42);
dataOrder.add(25);
dataOrder.add(67);
dataOrder.add(16);
dataOrder.add(32);
dataOrder.add(57);
dataOrder.add(82);
for (Integer i : dataOrder) {
tree.insert(i);
}
System.out.println(tree);
String expectedString = "[" + dataOrder.stream().map(Object::toString).collect(Collectors.joining(", ")) + "]";
Assert.assertEquals(expectedString, tree.toString());
tree.rotate(tree.root.leftChild, tree.root);
List rotatedDataOrder = new ArrayList<>();
rotatedDataOrder.add(25);
rotatedDataOrder.add(16);
rotatedDataOrder.add(42);
rotatedDataOrder.add(32);
rotatedDataOrder.add(67);
rotatedDataOrder.add(57);
rotatedDataOrder.add(82);
System.out.println(tree);
expectedString = "[" + rotatedDataOrder.stream().map(Object::toString).collect(Collectors.joining(", ")) + "]";
Assert.assertEquals(expectedString, tree.toString());
}
@Test
public void week04ActivityTestPart2() {
// Module 04: Red Black Tree Insert Activity - Step 1 (right rotation).
BinarySearchTree tree = new BinarySearchTree<>();
List dataOrder = new ArrayList<>();
dataOrder.add(42);
dataOrder.add(25);
dataOrder.add(67);
dataOrder.add(16);
dataOrder.add(32);
dataOrder.add(57);
dataOrder.add(82);
for (Integer i : dataOrder) {
tree.insert(i);
}
System.out.println(tree);
String expectedString = "[" + dataOrder.stream().map(Object::toString).collect(Collectors.joining(", ")) + "]";
Assert.assertEquals(expectedString, tree.toString());
tree.rotate(tree.root.leftChild.rightChild, tree.root.leftChild);
List rotatedDataOrder = new ArrayList<>();
rotatedDataOrder.add(42);
rotatedDataOrder.add(32);
rotatedDataOrder.add(67);
rotatedDataOrder.add(25);
rotatedDataOrder.add(57);
rotatedDataOrder.add(82);
rotatedDataOrder.add(16);
System.out.println(tree);
expectedString = "[" + rotatedDataOrder.stream().map(Object::toString).collect(Collectors.joining(", ")) + "]";
Assert.assertEquals(expectedString, tree.toString());
}
}