CS4343 Programming Assignment

Introduction
The Red-Black Tree is a self-balancing Binary Search Tree (BST). The structure is governed
by a number of rules which include;
1. Nodes are either red or black
2. The root node is always black
3. Every final/last leaf is black
4. A red node must have both of its children red
5. Simple paths for any node must have equal number of black descendant nodes
How to Compile and Run the Program
The solution developed for this question is presented in a single java file named;
RedBlackTree.java
to compile the program;
 java RedBlackTree.java
 javac RedBlackTree
The program requests for the filename from which it will read the commands, as shown below.

SOURCE CODE
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.Scanner;
public class RedBlackTree {
//The colors will be represented by 0 and 1
private final int RED = 0;
private final int BLACK = 1;
private final RBNode nil = new RBNode(-1);
private RBNode root = nil;
/*
We use a private inner class
to define the NODE
*/
private class RBNode {
int data = -1;
int color = BLACK;
RBNode left = nil;
RBNode right = nil;
RBNode parent = nil;

public RBNode(int key) {
this.data = key;
}
/**
* Constructor
*/
public RBNode(int key, RBNode parent, RBNode left, RBNode right, char color) {
this.data = key;
this.parent = parent;
this.left = left;
this.right = right;
this.color = color;
}
void setColor(char color) {
this.color = color;
}
}
/**
* This function prints out the Tree
* inorder
* @param node
*/
void printInorder(RBNode node) {

if (node == nil) {
return;
}
printInorder(node.left);
//Uncommenting this line will provide a detailed printout of the tree
//System.out.print(((node.color == RED) ? "Color: Red " : "Color: Black ") + "Key: " + node.key + "
Parent: " + node.parent.key + "\n");
System.out.print(node.data + " ");
printInorder(node.right);
}
/**
* This function searches a Node
* @param nodeToSearch
* @param rootNode
* @return
*/
private RBNode searchNode(RBNode nodeToSearch, RBNode rootNode) {
if (root == nil) {
return null;
}
if (nodeToSearch.data < rootNode.data) {
if (rootNode.left != nil) {
return searchNode(nodeToSearch, rootNode.left);
}
} else if (nodeToSearch.data > rootNode.data) {
if (rootNode.right != nil) {

return searchNode(nodeToSearch, rootNode.right);
}
} else if (nodeToSearch.data == rootNode.data) {
return rootNode;
}
return null;
}
/**
* Function to insert a node into a tree
* @param node
*/
private void insert(RBNode node) {
RBNode temp = root;
if (root == nil) {
root = node;
node.color = BLACK;
node.parent = nil;
} else {
node.color = RED;
while (true) {
if (node.data < temp.data) {
if (temp.left == nil) {
temp.left = node;
node.parent = temp;
break;
} else {

temp = temp.left;
}
} else if (node.data >= temp.data) {
if (temp.right == nil) {
temp.right = node;
node.parent = temp;
break;
} else {
temp = temp.right;
}
}
}
fixTree(node);
}
}
/**
* This function fixes the tree.
* It takes the newly inserted Node as
* an argument
* @param node
*/
private void fixTree(RBNode node) {
while (node.parent.color == RED) {
RBNode relativeNode = nil;
if (node.parent == node.parent.parent.left) {

relativeNode = node.parent.parent.right;
if (relativeNode != nil && relativeNode.color == RED) {
node.parent.color = BLACK;
relativeNode.color = BLACK;
node.parent.parent.color = RED;
node = node.parent.parent;
continue;
}
if (node == node.parent.right) {
//Double rotation needed
node = node.parent;
rotateLeft(node);
}
node.parent.color = BLACK;
node.parent.parent.color = RED;
//if the "else if" code hasn't executed, this
//is a case where we only need a single rotation
rotateRight(node.parent.parent);
} else {
relativeNode = node.parent.parent.left;
if (relativeNode != nil && relativeNode.color == RED) {
node.parent.color = BLACK;
relativeNode.color = BLACK;
node.parent.parent.color = RED;
node = node.parent.parent;
continue;

}
if (node == node.parent.left) {
//Double rotation needed
node = node.parent;
rotateRight(node);
}
node.parent.color = BLACK;
node.parent.parent.color = RED;
//if the "else if" code hasn't executed, this
//is a case where we only need a single rotation
rotateLeft(node.parent.parent);
}
}
root.color = BLACK;
}
/**
* The function Rotates the NODE
* to the left
* @param node
*/
void rotateLeft(RBNode node) {
if (node.parent != nil) {
if (node == node.parent.left) {
node.parent.left = node.right;
} else {
node.parent.right = node.right;

}
node.right.parent = node.parent;
node.parent = node.right;
if (node.right.left != nil) {
node.right.left.parent = node;
}
node.right = node.right.left;
node.parent.left = node;
} else {//Need to rotate root
RBNode right = root.right;
root.right = right.left;
right.left.parent = root;
root.parent = right;
right.left = root;
right.parent = nil;
root = right;
}
}
void rotateRight(RBNode node) {
if (node.parent != nil) {
if (node == node.parent.left) {
node.parent.left = node.left;
} else {
node.parent.right = node.left;
}

node.left.parent = node.parent;
node.parent = node.left;
if (node.left.right != nil) {
node.left.right.parent = node;
}
node.left = node.left.right;
node.parent.right = node;
} else {//Need to rotate root
RBNode left = root.left;
root.left = root.left.right;
left.right.parent = root;
root.parent = left;
left.right = root;
left.parent = nil;
root = left;
}
}
//Deletes whole tree
void deleteTree() {
root = nil;
}
/**
* Deletion
* @param target
* @param with

*/
void transplant(RBNode target, RBNode with) {
if (target.parent == nil) {
root = with;
} else if (target == target.parent.left) {
target.parent.left = with;
} else {
target.parent.right = with;
}
with.parent = target.parent;
}
/**
* Delete the
* @param z
* @return
*/
boolean delete(RBNode z) {
if ((z = searchNode(z, root)) == null) {
return false;
}
RBNode x;
RBNode y = z; // temporary reference y
int y_original_color = y.color;
if (z.left == nil) {
x = z.right;

transplant(z, z.right);
} else if (z.right == nil) {
x = z.left;
transplant(z, z.left);
} else {
y = treeMinimum(z.right);
y_original_color = y.color;
x = y.right;
if (y.parent == z) {
x.parent = y;
} else {
transplant(y, y.right);
y.right = z.right;
y.right.parent = y;
}
transplant(z, y);
y.left = z.left;
y.left.parent = y;
y.color = z.color;
}
if (y_original_color == BLACK) {
deleteFixup(x);
}
return true;
}
void deleteFixup(RBNode x) {

while (x != root && x.color == BLACK) {
if (x == x.parent.left) {
RBNode w = x.parent.right;
if (w.color == RED) {
w.color = BLACK;
x.parent.color = RED;
rotateLeft(x.parent);
w = x.parent.right;
}
if (w.left.color == BLACK && w.right.color == BLACK) {
w.color = RED;
x = x.parent;
continue;
} else if (w.right.color == BLACK) {
w.left.color = BLACK;
w.color = RED;
rotateRight(w);
w = x.parent.right;
}
if (w.right.color == RED) {
w.color = x.parent.color;
x.parent.color = BLACK;
w.right.color = BLACK;
rotateLeft(x.parent);
x = root;
}
} else {

RBNode w = x.parent.left;
if (w.color == RED) {
w.color = BLACK;
x.parent.color = RED;
rotateRight(x.parent);
w = x.parent.left;
}
if (w.right.color == BLACK && w.left.color == BLACK) {
w.color = RED;
x = x.parent;
continue;
} else if (w.left.color == BLACK) {
w.right.color = BLACK;
w.color = RED;
rotateLeft(w);
w = x.parent.left;
}
if (w.left.color == RED) {
w.color = x.parent.color;
x.parent.color = BLACK;
w.left.color = BLACK;
rotateRight(x.parent);
x = root;
}
}
}
x.color = BLACK;

}
RBNode treeMinimum(RBNode subTreeRoot) {
while (subTreeRoot.left != nil) {
subTreeRoot = subTreeRoot.left;
}
return subTreeRoot;
}
/**
* Search Function
*
* @param data
* @return
* @Input: data - the searched value
* @Output: RBNode when found, null when not-found
*/
public RBNode search(int data) {
RBNode r = root;
while (r != null) {
if (data < r.data) {
r = r.left;
} else if (data > r.data) {
r = r.right;
} else {
return r;
}

}
return null;
}
/**
* This function is called by the main method
* It displays the console interface where a user
* can input the filename and where the output is
* to be printed out.
*/
public void run() {
//Read user Input for the filename
System.out.println("Data Structure");
// input from file
Scanner scan = new Scanner(System.in);
System.out.print("Enter your input file name: ");
String fileName = scan.nextLine();
String s = ""; // file -> string s
try {
InputStreamReader reader = new InputStreamReader(
new FileInputStream(fileName));
BufferedReader br = new BufferedReader(reader);
s = br.readLine();
} catch (Exception e) {
System.out.println("Invalid file.");
return;
}

RBNode node;
String[] select = s.split(" ");
for (int i = 0; i < select.length; i++) {
String tmp = select[i];
int data = Integer.parseInt(tmp.substring(0, tmp.indexOf('.')));
String opt = tmp.substring(tmp.indexOf('.') + 1, tmp.length());
System.out.println(data + " " + opt);
if (opt.equals("in")) {
node = new RBNode(data);
if (searchNode(node, root) == null) {
insert(node);
} else {
System.out.println("Duplicate.");
// continue;
}
} else if (opt.equals("del")) {
node = new RBNode(data);
delete(node);
}
System.out.print("Display after this operation: ");
//st.inorder(st.root);
printInorder(root);

System.out.println("");
}
}
/**
* The entry point for the program
* @param args
*/
public static void main(String[] args) {
RedBlackTree redBlack = new RedBlackTree();
redBlack.run();
}
}