Tree's and the likes...

damnyanks

Howdy,

Just reading up for an assignment. Basically we've been told to use a balanced tree. I want to find an alternative (Just to be different )

Well the tree has to take in a book's text and count the frequency of how often certain words appear next to each other.

The only alternative I've been able to think up so far was 2 linked lists which cross paths, in effect making a hash map. But I don't think it would be very effienct. Since the text taken in will be so large I can't really risk having massive nodes so I guess a b-tree would be the best option. However that said my knowledge of data structures doesn't extend very far

Can anyone offer me some tips / advice? I'm leaning towards a standard AVL Tree as currently seems the easiest to implement but I'm sure just about everyone else has had the same idea. Would like to learn something new…

kenmc

if you were told to use a Balanced tree then you better do so....
call it the requirements spec of the project.

damnyanks

Nah its not a requirment Its a reccomendation. It's probably reccomended because from what I've seen its the best way to go about doing things... but then again I only really know what he's taught us

Capt'n Midnight

You could use a B-tree and optimise every so often to get the branches roughly equal.

If the book has N words then you could optimise the tree at Sqrt(N) words and again at Sqrt(Sqrt(N)) , some waffle about assuming that the word distribution in English won't differ a huge lot between a book / chapter / page / paragraph.

If you want pain then you could use a pigeon sort too..

rsynnott

That SOUNDS like a compression algorithm is going to make an appearance. Stick with the tree, I'd say.