I am trying to implement Red Black tree after studying about it but getting error while printing the Red Black tree. Can you please have a look and suggest whether there is anything wrong in the implementation of the Red Black Tree insertion. It shows only root and it's first left and right child recursively and then shows the following error :
Exception in thread "main" java.lang.StackOverflowError
at java.io.FileOutputStream.write(FileOutputStream.java:326)
at java.io.BufferedOutputStream.flushBuffer(BufferedOutputStream.java:82)
at java.io.BufferedOutputStream.flush(BufferedOutputStream.java:140)
at java.io.PrintStream.write(PrintStream.java:482)
at sun.nio.cs.StreamEncoder.writeBytes(StreamEncoder.java:221)
at sun.nio.cs.StreamEncoder.implFlushBuffer(StreamEncoder.java:291)
at sun.nio.cs.StreamEncoder.flushBuffer(StreamEncoder.java:104)
at java.io.OutputStreamWriter.flushBuffer(OutputStreamWriter.java:185)
at java.io.PrintStream.write(PrintStream.java:527)
at java.io.PrintStream.print(PrintStream.java:669)
at java.io.PrintStream.println(PrintStream.java:806)
at RedBlackTree.preOrder(RedBlackTree.java:161)
at RedBlackTree.preOrder(RedBlackTree.java:162)
at RedBlackTree.preOrder(RedBlackTree.java:162)
at RedBlackTree.preOrder(RedBlackTree.java:163)
Last two lines of error is repeated many times.
For print command I am using simple Pre-Order recursive code. Following is the code :
public class RedBlackTree {
public RBNode root;
void leftRotate(RBNode node)
{
RBNode y;
y = node.right;
if(y.left != null)y.left.parent = node;
y.parent = node.parent;
if(node.parent == null)root = y;
else
{
if(node == node.parent.left)node.parent.left = y;
else node.parent.right =y;
}
y.left = node;
node.parent = y;
}
void rightRotate(RBNode node)
{
RBNode y;
y = node.left;
if(y.right != null)y.right.parent = node;
y.parent = node.parent;
if(node.parent == null)root = y;
else
{
if(node == node.parent.right)node.parent.right = y;
else node.parent.left =y;
}
y.right = node;
node.parent = y;
}
void insertNode(RBNode node, RBNode data)
{
// INSERT IN ROOT
if(node == null)
{
node = new RBNode(data.key);
root = node;
root.color = 0;
System.out.println("Root " + root.key);
}
else if (data.key < node.key && node.left == null)
{
node.left = data;
data.parent = node;
}
else if(data.key >node.key && node.right == null)
{
node.right = data;
data.parent = node;
}
else{
if(data.key < node.key)insertNode(node.left, data);
else insertNode(node.right, data);
}
data.color = 1;
RBNode uncle;
//Check REB BLACK PROPERTIES
while(data.parent != null && data.parent.color ==1 && data != root && data.color != 0)
{
System.out.println("Data " + data.key + " Parent " + data.parent.key);
//PARENT IS RIGHT CHILD
if(data.parent == data.parent.parent.right)
{
System.out.println("Parent RIGHT");
uncle = data.parent.parent.left;
if(uncle == null) System.out.println("Uncle is null");
//UNCLE IS BLACK OR NULL
if(uncle == null || uncle.color == 0)
{
System.out.println("Uncle BLACK or NULL");
if(data == data.parent.left)
{
System.out.println("Node is LEFT");
data = data.parent;
rightRotate(data);
}
data.parent.color = 0;
if(data.parent.parent.key != root.key)data.parent.parent.color = 1;
leftRotate(data.parent.parent);
}
//UNCLE IS RED
else
{
System.out.println("Uncle RED");
data.parent.parent.left.color = 0;
data.parent.color = 0;
if(data.parent.parent.key != root.key)data.parent.parent.color = 1;
data = data.parent;
}
}
// PARENT IS LEFT CHILD
else
{
System.out.println("Parent LEFT");
uncle = data.parent.parent.right;
//UNCLE IS NULL OR BLACK
if(uncle ==null || uncle.color == 0)
{
System.out.println("Uncle BLACK or NULL");
System.out.println("");
if(data == data.parent.right)
{
System.out.println("Node is RIGHT");
data = data.parent;
leftRotate(data);
}
data.parent.color = 0;
if(data.parent.parent.key != root.key)data.parent.parent.color = 1;
rightRotate(data.parent.parent);
}
//UNCLE IS RED
else
{
System.out.println("Uncle RED");
data.parent.parent.right.color = 0;
data.parent.color = 0;
if(data.parent.parent.key != root.key)data.parent.parent.color= 1;
data = data.parent;
}
}
}
root.color = 0;
}
void preOrder(RBNode node)
{
if(node != null)
{
System.out.println("Value : " + node.key + "Color: " + node.color);
preOrder(node.left);
preOrder(node.right);
}
}
public static void main(String args[])
{
RedBlackTree tree = new RedBlackTree();
tree.insertNode(tree.root, new RBNode(2));
tree.insertNode(tree.root, new RBNode(1));
tree.insertNode(tree.root, new RBNode(4));
tree.insertNode(tree.root, new RBNode(5));
tree.insertNode(tree.root, new RBNode(9));
tree.insertNode(tree.root, new RBNode(3));
tree.insertNode(tree.root, new RBNode(6));
tree.insertNode(tree.root, new RBNode(7));
tree.preOrder(tree.root);
}
}
class RBNode
{
int key;
RBNode parent;
RBNode left;
RBNode right;
int color; // 1 = RED , 0 = BLACK
public RBNode(int key)
{
this.key = key;
this.parent = null;
this.left = null;
this.right = null;
}
}
Is the insertion implementation wrong?
