TreeSet - TreeMap: What is Balenced Tree

[Sandeep Mukherji]

I am going through the topic TreeSet and Tree Map where I found the following line:

Searching in a HashSet or HashMap can be faster than in a TreeSet or TerrMap, as hashing algorithm usually offer better performance than the search algorithms for balenced tree

My query is "What is a balenced tree?"

[Eugene Wee]

The NIST Dictionary of Algorithms and Data Structures defines a balanced tree as: A tree where no leaf is much farther away from the root than any other leaf. Different balancing schemes allow different definitions of "much farther" and different amounts of work to keep them balanced.

In other words, a balanced tree is guaranteed not to degenerate into a linked list. As such, a search will take time proportional to the height of the tree (effectively O(log n)) instead of proportional to the number of elements (O(n)).
[ May 09, 2008: Message edited by: Eugene Wee ]

[Guido Sautter]

Check this out and try to figure out the complexity of lookup operations.