So, I am trying to implement insertion for a red black tree, using sentinels as described in the "Introduction to Algorithms".
I've created a Generic class for a red black node, which has type parameter as its data attribute and the other attributes: parent(node type), leftchild(node type), rightchild(node type) and a color(enum type having red and black values).
Red-Back Node Class:-
public class RedBlackTreeNode<T extends Comparable<T>> {
enum color{
RED,
BLACK
}
private T data;
private color color;
private RedBlackTreeNode<T> leftChild;
private RedBlackTreeNode<T> rightChild;
private RedBlackTreeNode<T> parent;
public RedBlackTreeNode(T data) {
this.data = data;
leftChild = null;
rightChild = null;
parent = null;
color = null;
}
public T getData() {
return data;
}
public void setData(T data) {
this.data = data;
}
public color getColor() {
return color;
}
public void setColor(color color) {
this.color = color;
}
public RedBlackTreeNode<T> getLeftChild() {
return leftChild;
}
public void setLeftChild(RedBlackTreeNode<T> leftChild) {
this.leftChild = leftChild;
}
public RedBlackTreeNode<T> getRightChild() {
return rightChild;
}
public void setRightChild(RedBlackTreeNode<T> rightChild) {
this.rightChild = rightChild;
}
public RedBlackTreeNode<T> getParent() {
return parent;
}
public void setParent(RedBlackTreeNode<T> parent) {
this.parent = parent;
}
}
Red Black Tree Class:
import redBlackTree.RedBlackTreeNode.color;
public class RedBlackTree<T extends Comparable<T>> {
private RedBlackTreeNode<T> sentinel
;
private RedBlackTreeNode<T> root;
public RedBlackTree() {
sentinel = new RedBlackTreeNode<>(null);
sentinel.setColor(color.BLACK);
root = null;
}
public void redBlackInsert(RedBlackTreeNode<T> z) {
RedBlackTreeNode<T> y, x;
int temp;
y = sentinel;
x = this.root;
//Getting NullPointerException in the below while loop condition
while ((x.getData()) != null) {
y = x;
temp = z.getData().compareTo(x.getData());
if (temp < 0) {
x = x.getLeftChild();
} else {
x = x.getRightChild();
System.out.println("Right child of X: " + x);
System.out.println("Sentinel: " + x);
}
}
z.setParent(y);
if (y.getData() != null) {
temp = z.getData().compareTo(y.getData());
if (temp < 0) {
y.setLeftChild(z);
} else {
y.setRightChild(z);
}
} else {
root = z;
}
z.setLeftChild(sentinel);
z.setRightChild(sentinel);
z.setColor(color.RED);
redBlackInsertFix(z);
System.out.println("First node inserted");
}
private void redBlackInsertFix(RedBlackTreeNode<T> z) {
while (z.getParent().getColor() == color.RED) {
if (z.getParent() == z.getParent().getParent().getLeftChild()) {
RedBlackTreeNode<T> y;
y = z.getParent().getParent().getRightChild();
if (y.getColor() == color.RED) {
z.getParent().setColor(color.BLACK);
y.setColor(color.BLACK);
z.getParent().getParent().setColor(color.RED);
z = z.getParent().getParent();
} else if (z == z.getParent().getRightChild()) {
z = z.getParent();
leftRotate(z);
}
z.getParent().setColor(color.BLACK);
z.getParent().getParent().setColor(color.RED);
rightRotate(z.getParent().getParent());
} else {
RedBlackTreeNode<T> y;
y = z.getParent().getParent().getLeftChild();
if (y.getColor() == color.RED) {
z.getParent().setColor(color.BLACK);
y.setColor(color.BLACK);
z.getParent().getParent().setColor(color.RED);
z = z.getParent().getParent();
} else if (z == z.getParent().getLeftChild()) {
z = z.getParent();
rightRotate(z);
}
z.getParent().setColor(color.BLACK);
z.getParent().getParent().setColor(color.RED);
leftRotate(z.getParent().getParent());
}
}
root.setColor(color.BLACK);
}
private void rightRotate(RedBlackTreeNode<T> y) {
RedBlackTreeNode<T> x;
x = y.getLeftChild();
y.setLeftChild(x.getRightChild());
if (x.getRightChild() != sentinel) {
x.getRightChild().setParent(y);
}
x.setParent(y.getParent());
if (y.getParent() == sentinel) {
root = x;
} else if (y == y.getParent().getLeftChild()) {
y.getParent().setLeftChild(x);
} else {
y.getParent().setRightChild(x);
}
x.setRightChild(y);
y.setParent(x);
}
private void leftRotate(RedBlackTreeNode<T> x) {
RedBlackTreeNode<T> y;
y = x.getRightChild();
x.setRightChild(y.getLeftChild());
if (y.getLeftChild() != sentinel) {
y.getLeftChild().setParent(x);
}
y.setParent(x.getParent());
if (x.getParent() == sentinel) {
root = y;
} else if (x == x.getParent().getLeftChild()) {
x.getParent().setLeftChild(y);
} else {
x.getParent().setRightChild(y);
}
y.setLeftChild(x);
x.setParent(y);
}
public void inOrderTraversal(RedBlackTreeNode<T> x) {
if (x.getData() != sentinel.getData()) {
inOrderTraversal(x.getLeftChild());
System.out.println(x.getData());
inOrderTraversal(x.getRightChild());
}
}
public RedBlackTreeNode<T> getRoot() {
return root;
}
}
And here is the class having the main method:
public class RedBlackTreeDriver {
public static void main(String[] args) {
RedBlackTreeNode<Integer> one = new RedBlackTreeNode<>(50);
RedBlackTreeNode<Integer> two = new RedBlackTreeNode<>(55);
RedBlackTreeNode<Integer> three = new RedBlackTreeNode<>(48);
RedBlackTree<Integer> rbt = new RedBlackTree<>();
//System.out.println(rbt.getRoot());
//NullPointerException
rbt.redBlackInsert(one);
System.out.println("ROOT: "+ rbt.getRoot());
rbt.redBlackInsert(two);
rbt.redBlackInsert(three);
System.out.println(rbt.getRoot());
rbt.inOrderTraversal(rbt.getRoot());
}
}
I am trying to add a sentinel node(having the data attribute set as "null") after inserting every node with value. So, after adding the first node, I should be able to go down the tree(looking for sentinel) and add the new node to the parent of the sentinel.
I'm getting a null pointer exception in the Red Black Tree class. So far,I've tried almost everything I know. Can someone guide me through this?
