Program To Implement Red Black Tree and Binary Tree Using Java Programming Language Assignment Solutions

Instructions

Objective

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()); } }