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 ]