Help with Red Black Trees

Helllo Everyone.

I'm writing a program for a school assignment, and here's my scenario:

I have a txt file that has words delimited by punctuation marks on various lines, and I need to take in these words, insert them into a Red Black Tree, then produce an outputfile that prints each word in the file, followed by it's line number, and if the word appears more than once, have each subsequent line number printed seperated by commas, so for instance:

java 1, 3, 5

meaning that the word "java" appeared on lines 1, 3 and 5 of the txt file.

Ok, so I can read in the words, insert them into the RedBlack tree just fine, I just can't come up with a method of retrieving the line numbers that each word appears on and somehow storing it in a collection to keep track of it.

I thought about possibly having a Red Black Tree that would store 2 strings per node, the word and a list of line numbers it appeared on but I can't find any source code for a Red Black tree class that allows this function, and I can't figure out how to re-write the RB tree class i have so it does this.  This is the class file i'm using:

http://www.cs.fiu.edu/~weiss/dsj2/code/weiss/nonstandard/RedBlackTree.java

to make it compile w/o using the package, i commented out the package name at the top and i changed line 72 from:

throw new DuplicateItemException( item.toString( ) );

to simply: return;

I saw another site online that did this, and the class worked fine.

ANy ideas?

Thanks in advance

-Taylor
NeedlessKaneAsked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

CodingExpertsCommented:
0
delphi3Commented:
Hi NeedlessKane,

This is not a solution,

I am merely looking at this demo similar named demo
http://gauss.ececs.uc.edu/RedBlackTester/redblack.html
Parts included:
RedBlack.java   Stream.java    TokenObject.java    
 
I am not familiar with RedBlack. Is there a link that I can view.
You said above that you saw this elsewhere?
Thanks,

Delphi3
0
NeedlessKaneAuthor Commented:
Delphi3:

The link to the java file that CE posted is the one that I was referring to that commented out those two lines, and the class still compiled and worked.

I'm not strictly bound to Red Black trees, i can use any self balancing binary search tree, such as AVL, or AA, but i just chose to use Red black. So if you know a solution using AVL or any other balancing tree, please, let me know. This goes for everyone reading

-Taylor
0
Cloud Class® Course: Amazon Web Services - Basic

Are you thinking about creating an Amazon Web Services account for your business? Not sure where to start? In this course you’ll get an overview of the history of AWS and take a tour of their user interface.

CodingExpertsCommented:
Look what i feel is that you can read the file (I would suggest you to use StreamTokenzer ) and you can use a HashMap to store the key value pairs, where the key can be that of the string ,say Java as the key and the value can again be an ArrayList with all the position objects stored in the ArrayList and the position object would have the occurance position  (lineNo,positionInLine).

Key->Java,Value->(2,3)|(4,6)|(8,4)

this would imply that the String Java occurs at position (lineNo=2,positionInLine=3) and (lineNo=4,positionInLine=6) and so on.

Hope this solves your problem..
CE
0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
delphi3Commented:
Hi.
This is a cluttered solution not very well done in the
tradition of Java experts.
My appologies, I am a beginner on this topic:  AVL Tree


  Delphi3


// source:  http://www.cs.arizona.edu/azapcs/java.htm

/**
 * Grant D Hawkes
 * AVLTree.java
 * 7-7-02
 * This file implements and AVL Tree including a modified version of lazy deletion.
 * Much of the code in this file is from Mark Alan Weiss' Data Structures and Algorithms
 * book and it's accompaning website.
 */
/*
 *
 Test text Saved with title :  testStrings.txt
 
 Java is a very interesting evolving language.
 My study includes Delphi Pascal and Java
 I can see some of  Delphi Pascal in Java.
 Probably not a whole lot others would say.
 */

import java.util.*;
import java.io.*;

public class AVLTree
{
  private AVLNode root;
 
  public AVLTree()
  {
    root = null;
  }
 
 
  /**
   * public method to print the tree and then the names of the children in the tree
   * in alphabetical order (by first name).
   */
  public void printTeams()
  {
    printTree(root, "");
    System.out.println();
    printNames(root);
  } // end printTeams
 
  /**
   * Given the root of a tree and an initial buffer (indent) String this method
   * will print a AVL tree sideways to the console.  Imagine a handdrawn tree
   * and flip it 90 degrees counter-clockwise.  This is what this method will print.
   * Format is the name of the node then a colon then the frequency of people with that
   * first name, example: Grant:2
   */
  private void printTree(AVLNode curr, String buffer)
  {
    if(curr != null)
    {
      printTree(curr.right, buffer + "   ");
      System.out.println(buffer + curr.name + ":" + curr.freq);
      printTree(curr.left, buffer + "   ");
    }
  } // end printTree
 
  /**
   * Prints the names of the children in the tree (1 per line) sorted by first name.
   */
  private void printNames(AVLNode curr)
  {
    if(curr != null)
    {
      printNames(curr.left);
     
      for(int i = 0; i < curr.freq; i++)
        System.out.println(curr.nameList.get(i));
     
      printNames(curr.right);
    }
  } // end printNames
 
  /** Does lazy deletion on the String wholeName in the AVL tree. */
  public void remove(String wholeName)
  {
    StringTokenizer st = new StringTokenizer(wholeName);
    String name = st.nextToken(); // pulls the first token (first name) out of the wholeName
   
    AVLNode temp = find(name, root);
   
    if(temp != null)
    {
      if(temp.nameList.contains(wholeName))
      {
        temp.nameList.remove(wholeName);
        temp.freq--;
      }
    }
  }// end remove
 
 
  /** Makes the tree empty by setting the root to null */
  public void makeEmpty()
  {
    root = null;
  }
 
  /** Finds the String wholeName in the tree and returns it.  Returns null if not found. */
  public String find(String wholeName)
  {
    StringTokenizer st = new StringTokenizer(wholeName);
    String name = st.nextToken(); // pulls the first token (first name) out of the wholeName
   
    // temp is the node with the same FIRST name as the person we are searching for
    AVLNode temp = find(name,root);
    if(temp != null)
    {
      if(temp.nameList.contains(wholeName))
        return wholeName;
      else
        return null;
    }
    return null;
  } // end find
 
  /**
   * Internal method to find an item in a subtree.
   * @param x is item to search for.
   * @param t the node that roots the tree.
   * @return node containing the matched item.
   * Code from Mark Alan Weiss' data structures and alogorithms book.
   */
  private AVLNode find(String name, AVLNode curr)
  {
    while(curr != null)
      if(name.compareTo(curr.name) < 0)
      curr = curr.left;
    else if(name.compareTo(curr.name) > 0)
      curr = curr.right;
    else
      return curr;    // Match on the node level
   
    return null;   // No match
  }
 
  public AVLNode insert(String wholeName)
  {
    StringTokenizer st = new StringTokenizer(wholeName);
    String name = st.nextToken(); // pulls the first token (first name) out of the wholeName
    root = insert(name, wholeName, root);
    return root;
  }
 
  /**
   * Internal method to insert into a subtree.
   * @param x the item to insert.
   * @param t the node that roots the tree.
   * @return the new root.
   * Code from Mark Alan Weiss' data structures and alogorithms book.
   */
  private AVLNode insert(String name, String wholeName, AVLNode curr)
  {
    if( curr == null ) // the node is null
      curr = new AVLNode(name,wholeName,null,null);
    else if(name.compareTo(curr.name) < 0) // it is less than curr
    {
      curr.left = insert(name,wholeName,curr.left);
      if(height(curr.left) - height(curr.right) == 2) // there is an imbalance
        if(name.compareTo( curr.left.name ) < 0) // see what kind of imbalance it is
        curr = rotateWithLeftChild(curr);
      else
        curr = doubleWithLeftChild(curr);
    }
    else if( name.compareTo(curr.name) > 0) // it is more than curr
    {
      curr.right = insert(name,wholeName,curr.right);
      if(height(curr.right) - height(curr.left) == 2) // there is an imbalance
        if(name.compareTo(curr.right.name) > 0 ) // see what kind of imbalance it is
        curr = rotateWithRightChild(curr);
      else
        curr = doubleWithRightChild(curr);
    }
    else // it is a duplicate, increase freq and insert name into linked list
    {
      curr.nameList.add(wholeName);
      curr.freq++;
    }
    // finally update the height as we go
    curr.height = Math.max(height(curr.left), height(curr.right)) + 1;
    return curr;
  } // end insert
 
 
  /**
   * Return the height of node t, or -1, if null.
   * Code from Mark Alan Weiss' data structures and alogorithms book.
   */
  private static int height(AVLNode curr)
  {
    return curr == null ? -1 : curr.height;
  }
 
 
  /***** ROTATION CODE *****/
  /**
   * Code from Mark Alan Weiss' data structures and alogorithms book.
   */
 
  /**
   * Rotate binary tree node with left child.
   * For AVL trees, this is a single rotation for case 1.
   * Update heights, then return new root.
   * Code from Mark Alan Weiss' data structures and alogorithms book.
   */
  private AVLNode rotateWithLeftChild( AVLNode k2 )
  {
    AVLNode k1 = k2.left;
    k2.left = k1.right;
    k1.right = k2;
    k2.height = Math.max( height( k2.left ), height( k2.right ) ) + 1;
    k1.height = Math.max( height( k1.left ), k2.height ) + 1;
    return k1;
  }
 
  /**
   * Rotate binary tree node with right child.
   * For AVL trees, this is a single rotation for case 4.
   * Update heights, then return new root.
   * Code from Mark Alan Weiss' data structures and alogorithms book.
   */
  private AVLNode rotateWithRightChild( AVLNode k1 )
  {
    AVLNode k2 = k1.right;
    k1.right = k2.left;
    k2.left = k1;
    k1.height = Math.max( height( k1.left ), height( k1.right ) ) + 1;
    k2.height = Math.max( height( k2.right ), k1.height ) + 1;
    return k2;
  }
 
  /**
   * Double rotate binary tree node: first left child
   * with its right child; then node k3 with new left child.
   * For AVL trees, this is a double rotation for case 2.
   * Update heights, then return new root.
   * Code from Mark Alan Weiss' data structures and alogorithms book.
   */
  private AVLNode doubleWithLeftChild( AVLNode k3 )
  {
    k3.left = rotateWithRightChild( k3.left );
    return rotateWithLeftChild( k3 );
  }
 
  /**
   * Double rotate binary tree node: first right child
   * with its left child; then node k1 with new right child.
   * For AVL trees, this is a double rotation for case 3.
   * Update heights, then return new root.
   * Code from Mark Alan Weiss' data structures and alogorithms book.
   */
  private AVLNode doubleWithRightChild( AVLNode k1 )
  {
    k1.right = rotateWithLeftChild( k1.right );
    return rotateWithRightChild( k1 );
  }
 
  public static void main(String[] args) throws java.io.IOException
  {
    AVLTree avl = new AVLTree();
    String[] retainWrdLineNum = new String[100];
   
    int ic = 0;
    String delims = " ";
    StringTokenizer st = null;
   
    BufferedReader br = new BufferedReader(new FileReader("testStrings.txt"));
   
   
    String sx;
    int i = 0;
    int j = 0;    
    // new
    Vector temprecords = new Vector(0);
   
    while((sx=br.readLine()) != null)
    {
      j = 0;
      st = new StringTokenizer(sx,delims);
      String[] line_records = new String[9];// now 9 to accomodate lines of equal membership?
      while(st.hasMoreTokens())
      {
        line_records[j] = st.nextToken();
        j++;
      }      
      // New
      temprecords.add (line_records);
      i++;
    }
   
   
    for(i=0; i < temprecords.size(); i++)
    {
      String[] curr = (String[])temprecords.elementAt (i);
     
      // Go through fields
      for(j=0; j < curr.length; j++)
      {
       
        // Output field
        System.out.print (curr[j] + " ");
        retainWrdLineNum [ic] = curr[j] + " "+ (i+1);
        //System.out.println("Insert and Delete TEST1");
        avl.insert(curr[j] + " ");
       
        ++ic;
        //avl.printTeams();  // test1  
      }
      // move down a line
      System.out.println ();
      avl.printTeams();  // test1
     
     
    }
    String temp3;
    System.out.println(ic);
    System.out.println("Sorting");
    for (int ia = 0; ia < ic-1; ++ia) {  
      for (int ib = 0; ib <ic-1; ++ib) {    
        if (retainWrdLineNum[ib].compareTo(retainWrdLineNum[ib + 1]) > 0) {
          temp3 = retainWrdLineNum[ib];
          retainWrdLineNum[ib] = retainWrdLineNum[ib + 1];
          retainWrdLineNum[ib + 1] = temp3;
        }
      }
    }
    System.out.println("Sorted");
    System.out.println(" ");
    System.out.println("WrdCnt  Wrd  LocInLine# ");
    for(int id= 0;id < ic;++id){
      System.out.println(id  + ". " + retainWrdLineNum[id]);                                                                      
    }
  }
}

import java.util.LinkedList;

public class AVLNode
{
  public int freq;
  public int height;
  public String name;
  public AVLNode right;
  public AVLNode left;
  public LinkedList nameList;
 
  public AVLNode(String xname, String xwholeName)
  {
    this(xname, xwholeName, null, null);
  }
 
  public AVLNode(String xname, String xwholeName, AVLNode xleft, AVLNode xright)
  {
    name = xname;
    left = xleft;
    right = xright;
    height = -1; // this line is not needed, just an initialization
    nameList = new LinkedList();
    nameList.add(xwholeName);
    freq = 1; // freq is one because 1 name was just added
  }
}

0
delphi3Commented:
Hi NeedlessKane,
Thanks for the points and grade. I appreciate it.

Delphi3
0
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Java

From novice to tech pro — start learning today.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.