Java Red-Black Tree

[asmit]

I have a bit of a problem! I need to insert keys from a text input file (string tokens) into a red-black tree, however, I don't know how many keys there will be in the input file. I was thinking of creating an array of node objects to hold things such as (element_key, colour, parent, left_branch, right_branch) but I don't know how many objects to create in order to hold all of the keys.

I have attached a sample input file (the keys will be plucked right out of the file).

Is there any way that I can read through the file and determine how many tokens, and hence how many objects will need to be created?

BTW: The assignment has to be written in Java

Thanks!

[azcodemonkey]

Why not read through the file twice; once to ascertain the amount of keys, and once to extract your info?

[turbowrx]

An option would be to forget about using an array, and use an arraylist instead. This way you can always add more node objects. Check out arraylist in the api.

You could probably count the number of tokens, but I think using a resizing data structure makes more sense in this situation.

Hope I helped. Good luck. Bring on more questions if you have them.

[turbowrx]

An option would be to forget about using an array, and use an arraylist instead. This way you can always add more node objects. Check out arraylist in the api.

You could probably count the number of tokens, but I think using a resizing data structure makes more sense in this situation.

Hope I helped. Good luck. Bring on more questions if you have them.

Sorry about the double post. Neowin was struggling with my first submit, but evidently it worked.

[asmit]

Thanks for your ideas,

but now that I think about, i don't think I can use an array at all!

As I create the tree, if the same key is read more than once, the key's frequency count should increase. Because of this, (im sure the prof will have lots of repeats) even if I store every key in a llist, there will be duplicates that I will need to go thru and delete anyways!

I need to keep thinking!

Thanks tho!

[karma_police]

first check if you have read the key

[Winston]

Thanks for your ideas,

but now that I think about, i don't think I can use an array at all!

As I create the tree, if the same key is read more than once, the key's frequency count should increase.  Because of this, (im sure the prof will have lots of repeats) even if I store every key in a llist, there will be duplicates that I will need to go thru and delete anyways!

I need to keep thinking!

Thanks tho!

584981243[/snapback]

Hmmm have a look into Sets, sets is a collection which has no repeated elements.

[karma_police]

If you use an ArrayList you can check first if the element you are inserting is already in the Array using the Contains Method.

[Hummer]

just give a hashset a shot if you're not worried about memory usage.