Link to home
Start Free TrialLog in
Avatar of NeedlessKane
NeedlessKane

asked on

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
Avatar of CodingExperts
CodingExperts

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
Avatar of NeedlessKane

ASKER

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
ASKER CERTIFIED SOLUTION
Avatar of CodingExperts
CodingExperts

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
SOLUTION
Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
Hi NeedlessKane,
Thanks for the points and grade. I appreciate it.

Delphi3