Question about Binary Search Tree?

Question

Today, in class my professors said there's a balance binary search tree which I never heard of it before. I would like to know is there a Balance Binary Search tree without rotation? From my understanding, Balance Binary Search Tree is AVL tree. Besides that I don't think it's possible to build a 'Balance Binary Search Tree'. But if in case there's a data structure like that, how could I build a 'Balance Binary Search Tree' from a series of random numbers?

Thanks,

Answer 1

The idea behind populating balanced binary search tree using random numbers is like you will be adding nodes to the tree, whose keys are random numbers. When you'll implement a balanced binary search tree, populate it with 100s or 1000s of nodes with random number. The height should be as small as possible - which is the key feature of balanced binary search tree.

There exists balanced binary search trees other than AVL trees (like Red-Black Tree). Search google with balanced binary search tree.

Answer 2

Wikipedia has a nice list of trees at the bottom of any tree related article such as http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree