Question

Complete the redblacktree in Java.

Add a public boolean isBlack field to the Node inner class. Make every Node object have a false isBlack field, all new node is red by default.

In the end of the insert method, set the root node of your red black tree to be black.

Implement the rotate() and recolor() functions, and create tests for them in a separate class.

import java.util.LinkedList;

public class BinarySearchTree<T extends Comparable<T>> {

protected static class Node<T> {
public T data;
public Node<T> parent; // null for root node
public Node<T> leftChild;
public Node<T> rightChild;

public Node(T data) {
this.data = data;
}

public boolean isLeftChild() {
return parent != null && parent.leftChild == this;
}

@Override
public String toString() { // display subtree in order traversal
String output = "[";
LinkedList<Node<T>> q = new LinkedList<>();
q.add(this);
while (!q.isEmpty()) {
Node<T> 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<T> root; // reference to root node of tree, null when empty

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<T> newNode = new Node<>(data);
if (root == null) {
root = newNode;
} // add first node to an empty tree
else
insertHelper(newNode, root); // recursively insert into subtree
}

private void insertHelper(Node<T> newNode, Node<T> 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);
}
}

@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.
*/
private void rotate(Node<T> child, Node<T> parent) throws IllegalArgumentException {
// TODO: Implement this method.
}

/**
* recolor() takes a reference to a newly added red node as its only parameter. This method may
* also be called recursively, in which case the input parameter may reference a different red
* node in the tree that potentially has a red parent node. The job of this method is to resolve
* red child under red parent red black tree property violations that are introduced by inserting
* new nodes into a red black tree. All other red black tree properties must also be preserved.
* The method should be called from insertHelper after adding a new red node to the tree (in both
* the cases of adding this new node as a left child and as a right child). No further changes to
* the insertHelper method should be made.
*/
private void recolor(Node<T> newNode) {
// TODO: Implement this method.
}

}

Answer 1

/*
Add a public boolean isBlack field to the Node inner class. Make every Node object have a false isBlack field,
all new node is red by default.

In the end of the insert method, set the root node of your red black tree to be black.

Implement the rotate() and recolor() functions, and create tests for them in a separate class

*/
import java.util.LinkedList;

public class BinarySearchTree<T extends Comparable<T>> {

protected static class Node<T> {
public T data;
public Node<T> parent; // null for root node
public Node<T> leftChild;
public Node<T> rightChild;
public String color;

public Node(T data) {
this.data = data;
this.color = "Red";
}

public boolean isBlack(){
return this.color.equals("Black");
}

public boolean isLeftChild() {
return parent != null && parent.leftChild == this;
}

@Override
public String toString() { // display subtree in order traversal
String output = "[";
LinkedList<Node<T>> q = new LinkedList<>();
q.add(this);
while (!q.isEmpty()) {
Node<T> 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<T> root; // reference to root node of tree, null when empty

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<T> newNode = new Node<>(data);
if (root == null) {
root = newNode;
root.color = "Black";
} // add first node to an empty tree
else
insertHelper(newNode, root); // recursively insert into subtree
}

private void insertHelper(Node<T> newNode, Node<T> 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;
recolor(newNode);
// 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;
recolor(newNode);
// otherwise continue recursive search for location to insert
} else
insertHelper(newNode, subtree.rightChild);
}
}

@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.
*/
private void rotate(Node<T> child, Node<T> parent) throws IllegalArgumentException {

if(parent.leftChild == child){
if(parent.parent.leftChild == parent) {
parent.parent.leftChild = child;
}
else if (parent.parent.rightChild == parent){
parent.parent.rightChild = child;
}
parent.leftChild = child.rightChild;
child.rightChild = parent;
}
else if (parent.rightChild == child){
if(parent.parent.leftChild == parent) {
parent.parent.leftChild = child;
}
else if (parent.parent.rightChild == parent){
parent.parent.rightChild = child;
}
parent.rightChild = child.leftChild;
child.leftChild = parent;
}
else
throw new IllegalArgumentException("Child Parent do not match!");
}

/**
* recolor() takes a reference to a newly added red node as its only parameter. This method may
* also be called recursively, in which case the input parameter may reference a different red
* node in the tree that potentially has a red parent node. The job of this method is to resolve
* red child under red parent red black tree property violations that are introduced by inserting
* new nodes into a red black tree. All other red black tree properties must also be preserved.
* The method should be called from insertHelper after adding a new red node to the tree (in both
* the cases of adding this new node as a left child and as a right child). No further changes to
* the insertHelper method should be made.
*/
private void recolor(Node<T> newNode) {

if (newNode.parent!=null) {

// Case 1 Node is red, parent is red, grandparent is black, uncle is red
if (!newNode.isBlack()) {
if (!newNode.parent.isBlack()) {
if (newNode.parent.parent.isBlack()) {
if (!newNode.parent.parent.rightChild.isBlack()) {
newNode.parent.color = "Black";
newNode.parent.parent.rightChild.color = "Black";
newNode.parent.parent.color = "Red";
recolor(newNode.parent.parent);
}
else if (!newNode.parent.parent.leftChild.isBlack()) {
newNode.parent.color = "Black";
newNode.parent.parent.leftChild.color = "Black";
newNode.parent.parent.color = "Red";
}
}
}
}
// Case 2 Node is red, parent is red, grandparent is black, uncle is black
if(!newNode.isBlack()){
if (newNode.parent.rightChild == newNode) {
if (!newNode.parent.isBlack()) {
if (newNode.parent.parent.isBlack()) {
if (newNode.parent.parent.rightChild.isBlack()) {
rotate(newNode, newNode.parent);
rotate(newNode.parent.parent, newNode.parent.parent.rightChild);
recolor(newNode.parent);
}
}
}
}
else if(newNode.parent.leftChild == newNode){
if (!newNode.parent.isBlack()) {
if (newNode.parent.parent.isBlack()) {
if (newNode.parent.parent.leftChild.isBlack()) {
rotate(newNode, newNode.parent);
rotate(newNode.parent.parent, newNode.parent.parent.leftChild);
recolor(newNode.parent);
}
}
}
}
}
// Case 3 same condition making rotation.
if (!newNode.isBlack()){
if (newNode.parent.rightChild == newNode) {
if (!newNode.parent.isBlack()) {
if (newNode.parent.parent.isBlack()) {
if(newNode.parent.parent.leftChild == newNode.parent) {
if (newNode.parent.parent.rightChild.isBlack()) {
rotate(newNode.parent.parent, newNode.parent.parent.rightChild);
recolor(newNode.parent);
}
}
}
}
}
else if (newNode.parent.leftChild == newNode){
if (!newNode.parent.isBlack()) {
if(newNode.parent.parent.rightChild == newNode.parent) {
if (newNode.parent.parent.isBlack()) {
if (newNode.parent.parent.leftChild.isBlack()) {
rotate(newNode.parent.parent, newNode.parent.parent.leftChild);
recolor(newNode.parent);
}
}
}
}
}
}
// Case 4 same as 1 but coloring
if (!newNode.isBlack()){
if(newNode.parent.leftChild == newNode) {
if (!newNode.parent.isBlack()){
if(newNode.parent.parent.leftChild == newNode.parent){
if(newNode.parent.parent.isBlack()){
if(!newNode.parent.parent.rightChild.isBlack()){
newNode.parent.color = "Black";
newNode.parent.parent.color = "Red";
newNode.parent.parent.rightChild.color = "Black";
recolor(newNode.parent.parent);
}
}
}
}
}
else if (newNode.parent.rightChild == newNode){
if(newNode.parent.parent.rightChild == newNode.parent){
if(!newNode.parent.color.isBlank()){
if(!newNode.parent.parent.leftChild.isBlack()){
newNode.parent.color ="Black";
newNode.parent.parent.color = "Red";
newNode.parent.parent.leftChild.color = "Black";
recolor(newNode.parent.parent);
}
}
}
}
}
}
}

}