Programming problem

[Rui]

Is anyone here experienced in Java and Binary Trees? I got my last university programming assignment and it is a tough one. I have got to build a tree in which words of a text will be inserted. So I made a nested leaf class where each leaf/node will store a final String that is the word and an integer occurrences, as well as an infix iterator (as in, it visits nodes by order: left subtree; root; right subtree) for the main tree class (which is theoretically working).

I believe I have the insertion and structural parts figured out, but the real problem is what follows:
How to create a method that constructs a list of words starting with a set pattern? As in, find all words that start with 'are'.

Of course I could iterate through the entire tree and find out, but that is terribly inefficient and wastes unnecessary time: if I'm searching for a pattern starting with 'za', for example, the tree is going to iterate all the way down from 'a' to 'z' before it finds the words, being O(n) at worst. O(n) is sorta bad here since it is a literary text: there will be a LOT of different words.

I can't really find a pattern here: for example inserting the words 'a', 'boar', 'boat', 'c', 'botox', 'bulldog'. If I try to find words starting with 'bo'...
...I wonder if I have to climb down the tree to find the first word that starts with 'bo', add the left subtree for iteration and then climb down to the right until I have found a word that doesn't start with 'bo', but add all the nodes to the left of that for iteration?

 

[Zakamutt]

I think you just answered your own question

However, you make a valid point if your btree is not balanced. Implement a balanced binary tree and you'll have a maximum search time of O(ln(n)) afaik.

If you're too lazy to do that, I advise you to at least start off with a node in the middle of the alphabet, not a. If there isn't any in the text, just make it a dummy node or something.

 

[Dr Super Good]

Use an AVL tree (it is a standard algorithm) to handle tree balance. Guarantees that each layer of the tree is full before allowing the next layer to be created.

 

[Rui]

I was having a sorta ridiculous problem. It appears I can't jump to a node.left and then create the node, I have to make sure node.left = new Node(), else it doesn't attach T.T
My problem right now is that I'm repeating a lot of code, I should make a method to find a specific node but usually I also need to keep a track of its parent or just do different things for two node pathways.

New challenge, find every word between 2 given words...

 

[Zakamutt]

Well that challenge should be easy, really. Maybe even somewhat fun

 

[Dr Super Good]

find every word between 2 given words...

I am failing to see what this has to do with binary search trees... Unless you are after creating a new tree that handles the words before and after a word and uses those to navigate with.

 

[Rui]

Well that challenge should be easy, really. Maybe even somewhat fun

Yes I ended up solving it pretty easily 5 minutes thereafter.

Anyhow, now I think I really have a problem. Is it impossible to implement an Iterator for two different types? My nested class Node holds the word as well as the number of times it occurs. I initially implemented it for Strings but now I need to iterate through the nodes and get the other attribute as well. Unfortunately, Java will not accept multiple iterator() methods even if they hold different types and it will not accept typecasts anywhere either. Any clever way to solve this?

Part of the problem is that I have my next() method returning the word, but I'd need to detect the type of data being used by the client class and return data accordingly.

P.S. — I am given a client class that is immutable, so making my class generic is not a good idea since it is creating an instance of my class without any generic parameters.

 

[Dr Super Good]

You implement multiple iterator types as sub classes. You could then do something like GetXIterator and GetYIterator.

You can use implied classes (I think that is the name...) which are only a couple of lines long to do this.

 

[Rui]

I'm not sure how that would go. How would a client class select which data type to have if the iterator() does not allow arguments?

 

[Dr Super Good]

A method returns the iiterable class.

Eg...

Iterable<String> GetStringIterable()
Iterable<Integer> GetIntegerIterable()