Results 1 to 17 of 17
  1. #1
    unicorn is offline Member
    Join Date
    Oct 2009
    Posts
    9
    Rep Power
    0

    Default Red Black tree insertion

    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:
    Java Code:
       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;
        }
    Last edited by unicorn; 11-03-2009 at 11:02 AM.

  2. #2
    FatalError is offline Member
    Join Date
    Nov 2009
    Posts
    10
    Rep Power
    0

    Default

    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?

  3. #3
    FatalError is offline Member
    Join Date
    Nov 2009
    Posts
    10
    Rep Power
    0

    Default

    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?

  4. #4
    unicorn is offline Member
    Join Date
    Oct 2009
    Posts
    9
    Rep Power
    0

    Default

    I have everything in one file. In case you have class Node in different file, they should be something like this:
    Java Code:
    		public Node getParent()
    		{
    			return parent;
    		}
    mutator:
    Java Code:
    		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.

  5. #5
    FatalError is offline Member
    Join Date
    Nov 2009
    Posts
    10
    Rep Power
    0

    Default

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

  6. #6
    unicorn is offline Member
    Join Date
    Oct 2009
    Posts
    9
    Rep Power
    0

    Default

    Then you don't need accessors. Instead, you can use:
    Java Code:
    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.

  7. #7
    FatalError is offline Member
    Join Date
    Nov 2009
    Posts
    10
    Rep Power
    0

    Default

    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?

  8. #8
    FatalError is offline Member
    Join Date
    Nov 2009
    Posts
    10
    Rep Power
    0

    Default

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

  9. #9
    unicorn is offline Member
    Join Date
    Oct 2009
    Posts
    9
    Rep Power
    0

    Default

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

  10. #10
    FatalError is offline Member
    Join Date
    Nov 2009
    Posts
    10
    Rep Power
    0

    Default

    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.

  11. #11
    unicorn is offline Member
    Join Date
    Oct 2009
    Posts
    9
    Rep Power
    0

    Default

    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 Code:
    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

  12. #12
    FatalError is offline Member
    Join Date
    Nov 2009
    Posts
    10
    Rep Power
    0

    Default

    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.

  13. #13
    unicorn is offline Member
    Join Date
    Oct 2009
    Posts
    9
    Rep Power
    0

    Default

    input data is a String array that the main method take as its argument
    Java Code:
    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,
    Java Code:
    String fileName = args[0]; // fileName will be your input file

  14. #14
    FatalError is offline Member
    Join Date
    Nov 2009
    Posts
    10
    Rep Power
    0

    Default

    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?

  15. #15
    FatalError is offline Member
    Join Date
    Nov 2009
    Posts
    10
    Rep Power
    0

    Default

    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?

  16. #16
    unicorn is offline Member
    Join Date
    Oct 2009
    Posts
    9
    Rep Power
    0

    Default

    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()
    Java Code:
    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);
    	}
    }

  17. #17
    FatalError is offline Member
    Join Date
    Nov 2009
    Posts
    10
    Rep Power
    0

    Default

    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.

Similar Threads

  1. Creating a Tree and then saving the Tree
    By jackmatt2 in forum New To Java
    Replies: 0
    Last Post: 08-22-2009, 01:51 PM
  2. Regarding Data Insertion
    By adeeb in forum JDBC
    Replies: 1
    Last Post: 06-22-2008, 06:26 AM
  3. Using PreparedStatement for insertion
    By Java Tip in forum Java Tip
    Replies: 0
    Last Post: 02-06-2008, 10:30 AM
  4. Why this image background is black ?
    By samson in forum Java 2D
    Replies: 1
    Last Post: 07-17-2007, 05:24 AM
  5. Implementing a red-black tree in java
    By baltazar in forum New To Java
    Replies: 1
    Last Post: 07-13-2007, 09:37 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •