I'm working on red and black trees and I'm trying to figure out what's giving me this null pointer exception and how can I fix it. If anyone could help me fix it, it will be highly appreciated
I'm trying to insert 1000 random numbers into the RB Tree and trying to output the time it takes to insert it, size of the tree, height of the tree and printing them using different traversal methods. I've spent 2 hours trying to fix this error but so far I haven't found any solution to it.
Please skip to the "Insert" method to see where I'm getting the error
This is my Red/Black tree code
package SearchTrees;
import SearchTrees.RBNode.RBColor;
public class RedBlackTree<T extends Comparable<T>> {
private RBNode<T> root;
private RBNode<T> nil = new RBNode<>();
private int size;
public RedBlackTree() {
root = new RBNode<>(); //empty root
size = 0;
}
public int Size() {
return size;
}
/**
* ***************************************************************
*
* Height of tree
*
***************************************************************
*/
public int height() {
//TODO -> Implement here
return 0;
}
/**
* ***************************************************************
*
* Black Height of a node
*
***************************************************************
*/
public int blackHeight() {
//TODO -> Implement here
return 0;
}
/**
* ***************************************************************
*
* Finding node with minimum value
*
***************************************************************
*/
public RBNode<T> treeMin() {
return treeMin(root);
}
public RBNode<T> treeMin(RBNode<T> x) {
while (!x.left.isEmpty()) {
x = x.left;
}
return x;
}
public boolean insert(T data) {
return insert(new RBNode<T>(data));
}
/* ***************************************************************
* Insert a new node
* Returns true on successful insert otherwise false (when already present)
*****************************************************************/
private boolean insert(RBNode<T> z) {
// Create a reference to root & initialize a node to nil
RBNode<T> y = nil;
RBNode<T> x = root;
// While we haven't reached a the end of the tree keep
// tryint to figure out where z should go
while (!isNil(x)) {
y = x;
//THIS IS WHERE I'M GETTING THE NULL POINTER EXCEPTION
// if z.key is < than the current key, go left
if (z.data.compareTo(y.data) < 0) {
// Update x.numLeft as z is < than x
y = y.left;
} // else z.key >= x.key so go right.
else {
// Update x.numGreater as z is => x
y = y.right;
}
}
// y will hold z's parent
z.parent = y;
// Depending on the value of y.key, put z as the left or
// right child of y
if (isNil(y)) {
root = z;
} else if (z.data.compareTo(y.data) < 0) {
y.left = z;
} else {
y.right = z;
}
// Initialize z's children to nil and z's color to red
z.left = nil;
z.right = nil;
z.color = RBColor.RED;
// Call insertFixup(z)
insertFixup(z);
size++;
return false;
}// end insert(RedBlackNode z)
private void insertFixup(RBNode<T> z) {
RBNode<T> y = nil;
// While there is a violation of the RedBlackTree properties..
while (z.parent.color == RBColor.RED) {
// If z's parent is the the left child of it's parent.
if (z.parent == z.parent.parent.left) {
// Initialize y to z 's cousin
y = z.parent.parent.right;
// Case 1: if y is red...recolor
if (y.color == RBColor.RED) {
z.parent.color = RBColor.BLACK;
y.color = RBColor.BLACK;
z.parent.parent.color = RBColor.RED;
z = z.parent.parent;
} // Case 2: if y is black & z is a right child
else if (z == z.parent.right) {
// leftRotaet around z's parent
z = z.parent;
leftRotate(z);
} // Case 3: else y is black & z is a left child
else {
// recolor and rotate round z's grandpa
z.parent.color = RBColor.BLACK;
z.parent.parent.color = RBColor.RED;
rightRotate(z.parent.parent);
}
} // If z's parent is the right child of it's parent.
else {
// Initialize y to z's cousin
y = z.parent.parent.left;
// Case 1: if y is red...recolor
if (y.color == RBColor.RED) {
z.parent.color = RBColor.BLACK;
y.color = RBColor.BLACK;
z.parent.parent.color = RBColor.RED;
z = z.parent.parent;
} // Case 2: if y is black and z is a left child
else if (z == z.parent.left) {
// rightRotate around z's parent
z = z.parent;
rightRotate(z);
} // Case 3: if y is black and z is a right child
else {
// recolor and rotate around z's grandpa
z.parent.color = RBColor.BLACK;
z.parent.parent.color = RBColor.RED;
leftRotate(z.parent.parent);
}
}
}
// Color root black at all times
root.color = RBColor.BLACK;
}
//TODO -> implement here
private void leftRotate(RBNode<T> x) {
// Call leftRotateFixup() which updates the numLeft
// and numRight values.
leftRotateFixup(x);
// Perform the left rotate as described in the algorithm
// in the course text.
RBNode<T> y;
y = x.right;
x.right = y.left;
// Check for existence of y.left and make pointer changes
if (!isNil(y.left)) {
y.left.parent = x;
}
y.parent = x.parent;
// x's parent is nul
if (isNil(x.parent)) {
root = y;
} // x is the left child of it's parent
else if (x.parent.left == x) {
x.parent.left = y;
} // x is the right child of it's parent.
else {
x.parent.right = y;
}
// Finish of the leftRotate
y.left = x;
x.right = y.left;
}// end leftRotate(RedBlackNode x)
private void leftRotateFixup(RBNode x) {
// Case 1: Only x, x.right and x.right.right always are not nil.
if (isNil(x.left) && isNil(x.right.left)) {
x.numLeft = 0;
x.numRight = 0;
x.right.numLeft = 1;
} // Case 2: x.right.left also exists in addition to Case 1
else if (isNil(x.left) && !isNil(x.right.left)) {
x.numLeft = 0;
x.numRight = 1 + x.right.left.numLeft
+ x.right.left.numRight;
x.right.numLeft = 2 + x.right.left.numLeft
+ x.right.left.numRight;
} // Case 3: x.left also exists in addition to Case 1
else if (!isNil(x.left) && isNil(x.right.left)) {
x.numRight = 0;
x.right.numLeft = 2 + x.left.numLeft + x.left.numRight;
} // Case 4: x.left and x.right.left both exist in addtion to Case 1
else {
x.numRight = 1 + x.right.left.numLeft
+ x.right.left.numRight;
x.right.numLeft = 3 + x.left.numLeft + x.left.numRight
+ x.right.left.numLeft + x.right.left.numRight;
}
}
private void rightRotate(RBNode<T> y) {
// Call rightRotateFixup to adjust numRight and numLeft values
rightRotateFixup(y);
// Perform the rotate as described in the course text.
RBNode<T> x = y.left;
y.left = x.right;
// Check for existence of x.right
if (!isNil(x.right)) {
x.right.parent = y;
}
x.parent = y.parent;
// y.parent is nil
if (isNil(y.parent)) {
root = x;
} // y is a right child of it's parent.
else if (y.parent.right == y) {
y.parent.right = x;
} // y is a left child of it's parent.
else {
y.parent.left = x;
}
x.right = y;
y.parent = x;
}// end rightRotate(RedBlackNode y)
private void rightRotateFixup(RBNode y) {
// Case 1: Only y, y.left and y.left.left exists.
if (isNil(y.right) && isNil(y.left.right)) {
y.numRight = 0;
y.numLeft = 0;
y.left.numRight = 1;
} // Case 2: y.left.right also exists in addition to Case 1
else if (isNil(y.right) && !isNil(y.left.right)) {
y.numRight = 0;
y.numLeft = 1 + y.left.right.numRight
+ y.left.right.numLeft;
y.left.numRight = 2 + y.left.right.numRight
+ y.left.right.numLeft;
} // Case 3: y.right also exists in addition to Case 1
else if (!isNil(y.right) && isNil(y.left.right)) {
y.numLeft = 0;
y.left.numRight = 2 + y.right.numRight + y.right.numLeft;
} // Case 4: y.right & y.left.right exist in addition to Case 1
else {
y.numLeft = 1 + y.left.right.numRight
+ y.left.right.numLeft;
y.left.numRight = 3 + y.right.numRight
+ y.right.numLeft
+ y.left.right.numRight + y.left.right.numLeft;
}
}
/**
* ***************************************************************
* Delete a node Returns true on successful deletion and false otherwise
* ***************************************************************
*/
public boolean delete(T data) {
boolean found = false;
//TODO -> implement here
return found;
}
// Assigns node v to the parent of u
// useful while deletion
private void assignParent(RBNode<T> u, RBNode<T> v) {
if (u.parent == null) {
root = v;
} else if (u == u.parent.left) {
u.parent.left = v;
} else {
u.parent.right = v;
}
v.parent = u.parent;
}
private void deleteFixup(RBNode<T> x) {
//TODO -> implement here
}
/**
* **************************************************************
*
* Reset Tree
*
**************************************************************
*/
public void reset() {
root = new RBNode<>();
size = 0;
}
private boolean isNil(RBNode node) {
// return appropriate value
return node == nil;
}
/**
* ***************************************************************
* Traversal
*
*****************************************************************
*/
public void inorder() {
System.out.print("inorder BST: ");
inorder(root);
System.out.println();
}
private void inorder(BSTNode<T> root) {
if (root != null) {
inorder(root.left);
System.out.print(" " + root.data);
inorder(root.right);
}
}
public void preorder() {
System.out.print("Preorder: ");
preorder(root);
System.out.println();
}
private void preorder(BSTNode<T> root) {
if (root != null) {
System.out.print(" " + root.data);
preorder(root.left);
preorder(root.right);
}
}
public void postorder() {
System.out.print("Postorder: ");
postorder(root);
System.out.println();
}
private void postorder(BSTNode<T> root) {
if (root != null) {
postorder(root.left);
postorder(root.right);
System.out.print(" " + root.data);
}
}
}
This is my RBNode
package SearchTrees;
public class RBNode<T> extends BSTNode<T> {
public enum RBColor {
BLACK, RED;
}
public RBNode<T> left; //left child
public RBNode<T> right; //right child
public RBColor color; //Color of node
public RBNode<T> parent; // reference to parent node
public int numLeft = 0;
public int numRight = 0;
public RBNode(T data, RBNode<T> l, RBNode<T> r, RBColor col) {
super(data, l, r);
this.color = col;
parent = null;
}
public RBNode(T data, RBNode<T> l, RBNode<T> r) {
super(data, l, r);
this.color = RBColor.BLACK; // black node by default
parent = null;
}
public RBNode(T data) {
this(data, null, null, RBColor.BLACK);
parent = null;
}
public RBNode() {
this(null, null, null, RBColor.BLACK);
parent = null;
}
/**
* Tests if the data is present or not
*
* @return true if present false otherwise
*/
public boolean isEmpty() {
if (data == null) {
return true;
} else {
return false;
}
}
}
