Results 1 to 6 of 6
Thread: Binary search tree ?
 06072011, 01:52 PM #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 =)
 06072011, 02:42 PM #2
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,532
 Blog Entries
 7
 Rep Power
 20
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 subtrees 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,
Joscenosillicaphobia: the fear for an empty beer glass
 06072011, 02:44 PM #3
Thanks ... how would i build a unsorted tree then?
 06072011, 02:52 PM #4
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,532
 Blog Entries
 7
 Rep Power
 20
If you want the resulting tree to be a balanced, sorted tree and the input is random, check AVL trees or redblack trees; note that the TreeSet class implements a redblack 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,
Joscenosillicaphobia: the fear for an empty beer glass
 06072011, 03:09 PM #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
 06072011, 03:22 PM #6
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,532
 Blog Entries
 7
 Rep Power
 20
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 redblack construction algorithm. Both of these algorithms keep the tree (more or less) balanced while preserving the BST properties.
kind regards,
Joscenosillicaphobia: the fear for an empty beer glass
Similar Threads

Binary search tree
By hansmoolman in forum New To JavaReplies: 2Last Post: 10282010, 01:59 PM 
Data Structures(Binary Search Tree to AVL Tree)ASAP pls
By jfAdik in forum Forum LobbyReplies: 0Last Post: 04042010, 07:40 AM 
Binary search tree search method
By chopo1980 in forum New To JavaReplies: 2Last Post: 12102009, 01:42 AM 
Binary Search Tree
By anmadie in forum New To JavaReplies: 5Last Post: 11172009, 02:39 AM 
Binary Search Tree
By Goo in forum New To JavaReplies: 0Last Post: 03062009, 04:46 PM
Bookmarks