# Thread: Binary search tree ?

1. ## 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 =)

2. 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

3. Thanks ... how would i build a unsorted tree then?

4. 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

5. 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

6. 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

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•