Red Black tree insertion

[unicorn]

Hello,
I'm having a problem with insertion. My Java code works fine until inserting 300 with it's uncle is null. I try to fix it by adding condition if (uncle != null) but still does not work.

I have class Node with attributes data (int), color (int), parent (Node), lchild (Node) and rchild (Node)
My RBinsert(Node [] rbTree, int key) will create a Node with key as its data, and color it RED originally.
First it is inserted into a tree as binary search tree ignoring color. I have treeInsert(Node [] tree, Node k) to do that (worked).
My RBinsert method will fix insertion violation (red-red bonding) using left-rotate and right-rotate and re-coloring. I have leftRotate(Node [] tree, Node y) and rightRotate(Node [] tree, Node x) working.

Everything works fine except this method:

   static void RBinsert(Node [] rbTree, int key)
    {
        Node k = new Node();
        k.data = key;
        k.color = 0; // color new key RED
        treeInsert(rbTree, k);
        while (k != rbTree[0] & k.parent.color == 0)
        {
            // case k's parent is left child
            if (k.parent == k.parent.parent.lchild)
            {
                Node uncle = k.parent.parent.rchild;
                System.out.println(uncle.data);
                // case 1: k's uncle is RED and k is left child
                if (uncle != null & uncle.color == 0)
                {
                    k.parent.color = 1; // new key's parent becomes BLACK
                    uncle.color = 1;
                    k.parent.parent.color = 0;
                    k = k.parent.parent;
                }
                else
                {
                    // case 2: k's uncle is BLACK and k is right child
                    if (k == k.parent.rchild)
                    {
                        k = k.parent;
                        leftRotate(rbTree, k);
                    }
                    // case 3: k's uncle is BLACK and k is left child
                    k.parent.color = 1;
                    k.parent.parent.color = 0;
                    rightRotate(rbTree, k.parent.parent);
                }
            }
            // case k's parent is right child
            else
            {
                Node uncle = k.parent.parent.lchild;
                System.out.println(uncle);
                // case 1: k's uncle is RED and k is left child
                if (uncle != null & uncle.color == 0)         -----> crash here
                {
                    k.parent.color = 1;
                    uncle.color = 1;
                    k.parent.parent.color = 0;
                    k = k.parent.parent;
                }
                else
                {
                    // case 2: k's uncle is BLACK and k is left child
                    if (k == k.parent.lchild)
                    {
                        k = k.parent;
                        rightRotate(rbTree, k);
                    }
                    // case 3: k's uncle is BLACK and k is right child
                    k.parent.color = 1;
                    k.parent.parent.color = 0;
                    leftRotate(rbTree, k.parent.parent);
                }
            }
        }
        rbTree[0].color = 1;
    }

[FatalError]

I think I'm in the same class as you. I haven't quite gotten mine complete. If I get my insert to work I'll let you know, but my question to you is how did you do your accessor and mutator methods for class Node and judging by your code did you keep everything in the same file?

[FatalError]

Sorry, I left out what accessor and mutator methods I was referring to. Specifically how did you do it for parent and left/right child?

[unicorn]

I have everything in one file. In case you have class Node in different file, they should be something like this:

		public Node getParent()
		{
			return parent;
		}

mutator:

		public void setParent(Node n)
		{
			parent = n;
		}

I have my insert works. But I haven't passed testcase2 yet. My RBread is having problem now.

[FatalError]

And if I was to do it in the same file, what would be different?

[unicorn]

Then you don't need accessors. Instead, you can use:

int i = aNode.data; // equivalent to i = aNode.getData()
int c = aNode.color;

Those lines above work only if you have class Node in the same file.

If you still use accessors even if you have class Node in the same file, no problem, just extra typing.

[FatalError]

So in your code for insert you have

k.parent.parent.color = 0;

If I keep my class Node in a separate file I should write

k.getParent.getParent.getColor = 0;

Correct?

[FatalError]

I mean k.getParent().getParent().getColor() = 0;

[unicorn]

yes...........

[FatalError]

How are you doing RBread? Are you using Scanner and then putting the values in an array of some sort? Second, what did you end up fixing in your insert? Mine is very similar but uses accessors.

[unicorn]

Just got done. No Scanner used. You should take the first argument args[0] for input file name as user will be entering when running your program.

java RBTree testcase1.txt

You can go to Blackboard to read more about it.

About insertion, I created a global Node nil_node with color black, and use this instead of NULL. That fixed the problem when uncle is null

[FatalError]

Can you perhaps clarify this. I'm looking at Blackboard and I'm still confused. I never used args before but that seems to be the way that they want it.

[unicorn]

input data is a String array that the main method take as its argument

static void main (String [] args) // we often use args as the name of the array

Following the run command (java nameClass), input data starts counting into the args array. So "testcase1.txt" will be stored in args[0] as the command above.

Basically,

String fileName = args[0]; // fileName will be your input file

[FatalError]

So fileName now contains all of my integer values in one long string. How do I then extract each integer individually to integer so that I can make node assignments?

[FatalError]

Sorry for the grammar. I didn't get any sleep. What I meant was

How do I then extract each integer individually so that I can make node assignments?

[unicorn]

You should read line by line in the file. Each line you should break down into an integer using split(" ") since space is between integers in a line.

You should have a for while loop to read each line until the line is null.
In the loop you break down the line into a small array. Try to store each integer in a big array.

This is an example I wrote to test split()

import java.io.*;
public class TryRW
{
	public static void main (String [] args)
	{
		String inputFile = "input.txt";
		String line = "";
		int size = 0;
		try
		{
			FileReader fr = new FileReader(inputFile);
			BufferedReader br = new BufferedReader(fr);
			PrintWriter pw = new PrintWriter("out.txt");

			while ((line = br.readLine()) != null)
			{
				String [] words = line.split(" ");
				for (int i = 0; i < words.length; i++)
				{
					System.out.println(words[i]);
					size++;

					pw.println(words[i]);
				}
			}
			br.close();
			pw.close();

		}
		catch (IOException ex) {}

		System.out.println(size);
	}
}

[FatalError]

Well I did not finish it in time, but I'm sure I'll get a better grade than I would have thanks to you unicorn.