I've been told that the java class TreeMap uses an implementation of a RB tree. If this is the case, how does one do an inorder, preorder and postorder tree-walk on a TreeMap?
Or is this not possible?
Add a comment
|
3 Answers
You wouldn't be able to do this with the TreeMap implemented in the Collections library. Here's an implementation of a Red-Black Tree in Java that you can look at though. Check out the printTree() methods to see how they walk the tree in sorted order.
/**
* Print all items.
*/
public void printTree( ) {
printTree( header.right );
}
/**
* Internal method to print a subtree in sorted order.
* @param t the node that roots the tree.
*/
private void printTree( RedBlackNode t ) {
if( t != nullNode ) {
printTree( t.left );
System.out.println( t.element );
printTree( t.right );
}
}
From that maybe you can write your own methods to traverse the tree in all three orders.
Comments
AFAIK the TreeSet/TreeMap classes don't actually expose any of their internals and merely conform to the Set/Map interface. The iterator is only guaranteed to go in an ascending order.
I am a little perplexed as to why you would want to scan these nodes in an inorder since the goal of these trees is not to represent relations between objects (e.g., math formulae) but rather just to store all of them and retrieve them efficiently.
2 Comments
kylex
It's more a question of theory than application.
NedStarkOfWinterfell
Hi @Uri, RB Trees always maintain the balance whatever order the keys are inserted in, right? So is it right to assume that if we insert keys into the TreeMap in a degenerate fashion, the search and insert times will be
O(log N)?You can at least do the inorder walk using the iterator and a for each loop:
void inOrderWalk(TreeMap<K,V> treeMap) {
//this will loop through the values in the map in sorted order (inorder traversal)
for (Map.Entry<K,V> entry : treeMap.entrySet() {
V value = entry.getValue();
K key = entry.getKey()
}
}
However, the other posters are right: Java doesn't expose any of the tree mechanics, so a preorder or postorder isn't possible at this view.
