Binary search tree ?

[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 =)

[JosAH]

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

[santa]

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

[JosAH]

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

[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

[JosAH]

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