# Binary search tree ?

• 06-07-2011, 01:52 PM
santa
Binary search tree ?
I don't know if its really java ... but its in the java book =P And i dont know if i get it ?

if you have a array with ints {1,2,3,4,5,6,7,8,9} how to you decide with one will be the root? just by taking the middle value ? Then how do you decide how the next branch will look like ... I know that the smallest number should be to the left at all time ... but i dont understand how you should "create " this tree ... just by splitting in half each branch?

And the largets height a tree of 100 integers can have is 100 right? if its really unbalanced? and how do i decide on the smallest height(well balanced)?

Thanks =)
• 06-07-2011, 02:42 PM
JosAH
Quote:

Originally Posted by santa
I don't know if its really java ... but its in the java book =P And i dont know if i get it ?

if you have a array with ints {1,2,3,4,5,6,7,8,9} how to you decide with one will be the root? just by taking the middle value ? Then how do you decide how the next branch will look like ... I know that the smallest number should be to the left at all time ... but i dont understand how you should "create " this tree ... just by splitting in half each branch?

And the largets height a tree of 100 integers can have is 100 right? if its really unbalanced? and how do i decide on the smallest height(well balanced)?

Thanks =)

Yep, if the list is ordered just take the element in the middle (or near the middle) as the root of the tree; recursively apply this choice to the two subsets to the left and right of this element for the two sub-trees of the root element.

The number of nodes on each level of a balanced and complete tree is 1, 2, 4, 8 etc. (check this). So if the total depth of the tree is n there are 1+2+4+ ... +2^n nodes in the tree which equals 2^(n+1)-1 nodes in total. Given a number of nodes N, the depth of the tree equals +- 2log(N)

kind regards,

Jos
• 06-07-2011, 02:44 PM
santa
Thanks ... how would i build a unsorted tree then?
• 06-07-2011, 02:52 PM
JosAH
Quote:

Originally Posted by santa
Thanks ... how would i build a unsorted tree then?

If you want the resulting tree to be a balanced, sorted tree and the input is random, check AVL trees or red-black trees; note that the TreeSet class implements a red-black tree. For an unsorted tree use the same trick as I described in my previous reply (you do have to know the size of the input in advance).

kind regards,

Jos
• 06-07-2011, 03:09 PM
santa
Okey so for example if you didént do it by java and got an unsorted array with {10, 4, 20, 2, 8, 18, 23} and wanted to create a binary tree would you sort it first ? how would the tree look like and why? sorry for my (dumb?) questions I just want to learn =) Thank you
• 06-07-2011, 03:22 PM
JosAH
Quote:

Originally Posted by santa
Okey so for example if you didént do it by java and got an unsorted array with {10, 4, 20, 2, 8, 18, 23} and wanted to create a binary tree would you sort it first ? how would the tree look like and why? sorry for my (dumb?) questions I just want to learn =) Thank you

No, normally the input set isn't sorted first (you don't know its size and it can be huge). A balanced complete BST can be effectively and efficiently constructed by applying the AVL or red-black construction algorithm. Both of these algorithms keep the tree (more or less) balanced while preserving the BST properties.

kind regards,

Jos