• Post Reply Bookmark Topic Watch Topic
  • New Topic

TreeSet - TreeMap: What is Balenced Tree  RSS feed

 
Sandeep Mukherji
Ranch Hand
Posts: 46
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Greenhorn
Posts: 5
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Ranch Hand
Posts: 142
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Check this out and try to figure out the complexity of lookup operations.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!