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,
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.
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
Hello there, Thanks Donotalo, I know Red Black tree. By that I means except all RedBlack Tree, AVL tree and 2-3, 2-3-4 trees, is there a 'Balance Binary Tree Search'? I think my professor made a mistake, I don't think there's such a tree like this. By reading from a file into an array, I can sort it and then use middle points algorithm to build a Balance Tree but this tree is indeed Binary Tree, just the matter of the number you insert it. And he said that this 'Balance Binary Search Tree' has worst case is O( N ), which I think it is also a mistake. From what I understand, a tree called 'Balanced' must have worst case O( logN ).