Results 1 to 6 of 6
  1. #1
    santa's Avatar
    santa is offline Senior Member
    Join Date
    Nov 2009
    Location
    Sweden
    Posts
    208
    Rep Power
    6

    Default 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. #2
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    14,043
    Blog Entries
    7
    Rep Power
    23

    Default

    Quote Originally Posted by santa View Post
    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
    The only person who got everything done by Friday was Robinson Crusoe.

  3. #3
    santa's Avatar
    santa is offline Senior Member
    Join Date
    Nov 2009
    Location
    Sweden
    Posts
    208
    Rep Power
    6

    Default

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

  4. #4
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    14,043
    Blog Entries
    7
    Rep Power
    23

    Default

    Quote Originally Posted by santa View Post
    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
    The only person who got everything done by Friday was Robinson Crusoe.

  5. #5
    santa's Avatar
    santa is offline Senior Member
    Join Date
    Nov 2009
    Location
    Sweden
    Posts
    208
    Rep Power
    6

    Default

    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. #6
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    14,043
    Blog Entries
    7
    Rep Power
    23

    Default

    Quote Originally Posted by santa View Post
    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
    The only person who got everything done by Friday was Robinson Crusoe.

Similar Threads

  1. Binary search tree
    By hansmoolman in forum New To Java
    Replies: 2
    Last Post: 10-28-2010, 01:59 PM
  2. Replies: 0
    Last Post: 04-04-2010, 07:40 AM
  3. Binary search tree search method
    By chopo1980 in forum New To Java
    Replies: 2
    Last Post: 12-10-2009, 02:42 AM
  4. Binary Search Tree
    By anmadie in forum New To Java
    Replies: 5
    Last Post: 11-17-2009, 03:39 AM
  5. Binary Search Tree
    By Goo in forum New To Java
    Replies: 0
    Last Post: 03-06-2009, 05:46 PM

Posting Permissions

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