Implementing insert in RedBlackTree in java

Question

I am trying to implement the CLRS Red Black Tree pseudo code. When I try to run the program, it throws NullPointerException. Browse through the code and look for something wrong in it. Any additional suggestions are welcome.

public class RedBlackTree {

Node nil;
Node root;
String RED = "red";
String BLACK = "black";

public void left_rotate(RedBlackTree T, Node x) {
    Node y = x.right;
    x.right = y.left;
    if (y.left != T.nil)
        y.left.parent = x;
    y.parent = x.parent;
    if (x.parent == T.nil)
        T.root = y;
    else if (x == x.parent.left)
        x.parent.left = y;
    else
        x.parent.right = y;
    y.left = x;
    x.parent = y;
}

public void right_rotate(RedBlackTree T, Node x) {
    Node y = x.left;
    x.left = y.right;
    if (y.right != T.nil)
        y.right.parent = x;
    y.parent = x.parent;
    if (x.parent == T.nil)
        T.root = y;
    else if (x == x.parent.right)
        x.parent.right = y;
    else
        x.parent.left = y;
    y.right = x;
    x.parent = y;
}

public void rb_insert_fixup(RedBlackTree T, Node z) {

    while (z.parent.color == RED) {
        if (z.parent == z.parent.parent.left) {
            Node y = z.parent.parent.right;
            if (y.color == RED) {
                z.parent.color = BLACK;
                y.color = BLACK;
                z.parent.parent.color = RED;
                z = z.parent.parent;
            } else {
                if (z == z.parent.right) {
                    z = z.parent;
                    left_rotate(T, z);
                }
                z.parent.color = BLACK;
                z.parent.parent.color = RED;
                right_rotate(T, z.parent.parent);
            }
        } else {
            Node y = z.parent.parent.left;
            if (y.color == RED) {
                z.parent.color = BLACK;
                y.color = BLACK;
                z.parent.parent.color = RED;
                z = z.parent.parent;
            } else {
                if (z == z.parent.left) {

                    z = z.parent;
                    right_rotate(T, z);
                }
                z.parent.color = BLACK;
                z.parent.parent.color = RED;
                left_rotate(T, z.parent.parent);
            }
        }

    }
    T.root.color = BLACK;
}

public void insert(RedBlackTree T, Node z) {
    Node y = T.nil;
    Node x = T.root;
    while (x != T.nil) {
        y = x;
        if (z.key < x.key)
            x = x.left;
        else
            x = x.right;
    }
    z.parent = y;
    if (y == T.nil)
        T.root = z;
    else if (z.key < y.key)
        y.left = z;
    else
        y.right = z;
    z.left = T.nil;
    z.right = T.nil;
    z.color = RED;
    rb_insert_fixup(T, z);
}

public void inorder_tree_walk(Node x) {
    if (x != null) {
        inorder_tree_walk(x.left);
        System.out.println(x.key + ":" + x.color + " ");
        inorder_tree_walk(x.right);
    }
}

public static void main(String[] args) {
    RedBlackTree rbt = new RedBlackTree();

    Node a = new Node(12, "a");
    rbt.insert(rbt, a);
    Node b = new Node(5, "b");
    rbt.insert(rbt, b);
    Node c = new Node(18, "c");
    rbt.insert(rbt, c);
    Node d = new Node(2, "d");
    rbt.insert(rbt, d);
    Node e = new Node(9, "e");
    rbt.insert(rbt, e);

    rbt.inorder_tree_walk(rbt.root);
    }

}

class Node {
int key;
String data;
String color;
Node left, right, parent;

public Node(int key, String data) {
    this.key = key;
    this.data = data;
    }
}

Stacktrace:

An exception was thrown in the main thread java.lang.NullPointerException in RedBlackTree.rb_insert_fixup (RedBlackTree.java:42) in RedBlackTree.insert (RedBlackTree.java:102) in RedBlackTree.main (RedBlackTree.java:117)

Answer 1

You must initialize niland root:

public class RedBlackTree {

Node nil;  <-- is null
Node root; <-- is null

Otherwise, it is also null:

while (z.parent.color == RED) { <-- z.parent is null