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
    13,783
    Blog Entries
    7
    Rep Power
    21

    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
    cenosillicaphobia: the fear for an empty beer glass

  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
    13,783
    Blog Entries
    7
    Rep Power
    21

    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
    cenosillicaphobia: the fear for an empty beer glass

  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
    13,783
    Blog Entries
    7
    Rep Power
    21

    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
    cenosillicaphobia: the fear for an empty beer glass

Similar Threads

  1. Binary search tree
    By hansmoolman in forum New To Java
    Replies: 2
    Last Post: 10-28-2010, 02:59 PM
  2. Replies: 0
    Last Post: 04-04-2010, 08: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
  •