[Webinar] Learn how to a build a cloud-first strategyRegister Now

x
?
Solved

Help with Red Black Trees

Posted on 2004-11-23
6
Medium Priority
?
567 Views
Last Modified: 2008-03-03
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
0
Comment
Question by:NeedlessKane
  • 3
  • 2
6 Comments
 
LVL 6

Expert Comment

by:CodingExperts
ID: 12662689
0
 
LVL 4

Expert Comment

by:delphi3
ID: 12662852
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
 

Author Comment

by:NeedlessKane
ID: 12668476
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
Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

 
LVL 6

Accepted Solution

by:
CodingExperts earned 135 total points
ID: 12671710
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
 
LVL 4

Assisted Solution

by:delphi3
delphi3 earned 150 total points
ID: 12679599
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
 
LVL 4

Expert Comment

by:delphi3
ID: 12699461
Hi NeedlessKane,
Thanks for the points and grade. I appreciate it.

Delphi3
0

Featured Post

Prep for the ITIL® Foundation Certification Exam

December’s Course of the Month is now available! Enroll to learn ITIL® Foundation best practices for delivering IT services effectively and efficiently.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

After being asked a question last year, I went into one of my moods where I did some research and code just for the fun and learning of it all.  Subsequently, from this journey, I put together this article on "Range Searching Using Visual Basic.NET …
By the end of 1980s, object oriented programming using languages like C++, Simula69 and ObjectPascal gained momentum. It looked like programmers finally found the perfect language. C++ successfully combined the object oriented principles of Simula w…
Viewers learn how to read error messages and identify possible mistakes that could cause hours of frustration. Coding is as much about debugging your code as it is about writing it. Define Error Message: Line Numbers: Type of Error: Break Down…
This video teaches viewers about errors in exception handling.
Suggested Courses
Course of the Month20 days, 13 hours left to enroll

864 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question