Binary search Tree:Help

Discussion in 'Java' started by brianm, Jan 10, 2005.

  1. brianm

    brianm Guest

    Is this implementation of a binary search tree correct ?

    numbers from 0 to 14 arranged in a binary tree (binary search tree). Is
    this correct ? (left node is less, right node is greater than the
    current node)


    7
    6 8
    5 9 2 12
    4 10 3 11 1 13 0 14
     
    brianm, Jan 10, 2005
    #1
    1. Advertising

  2. brianm

    Guest

    I'm not able to follow where the numbers lie in your tree, but there is
    no one binary search tree of those numbers. You can make up different
    trees based on when you insert numbers into the tree. But you have the
    basic premise right. All elements to the right are larger than the
    root. All elements to the left are smaller than the root.
    You could also include equality with the root in one of them.
     
    , Jan 10, 2005
    #2
    1. Advertising

  3. "brianm" <> wrote in message
    news:...
    > Is this implementation of a binary search tree correct ?
    >
    > numbers from 0 to 14 arranged in a binary tree (binary search tree). Is
    > this correct ? (left node is less, right node is greater than the
    > current node)
    >
    >
    > 7
    > 6 8
    > 5 9 2 12
    > 4 10 3 11 1 13 0 14


    The formatting make this difficult to read, but if 7 is the root, 6 and 8
    its children, and 9 the right child of 6, this is incorrect. Every member of
    a node's left subtree needs to be less than every member of its right
    subtree.
     
    Mike Schilling, Jan 10, 2005
    #3
  4. brianm

    Lee Weiner Guest

    In article <>, "brianm" <> wrote:
    >Is this implementation of a binary search tree correct ?
    >
    >numbers from 0 to 14 arranged in a binary tree (binary search tree). Is
    >this correct ? (left node is less, right node is greater than the
    >current node)
    >
    >
    >7
    >6 8
    >5 9 2 12
    >4 10 3 11 1 13 0 14
    >

    Your diagram is a little hard to read, but if 7 is your root node, and 6 and 8
    are the children off the root, then your diagram is not correct. For
    starters, the nodes containing 0, 1 and 2 should all be children of the 6
    node, not the 8 node. There are other mistakes.

    Lee Weiner
     
    Lee Weiner, Jan 10, 2005
    #4
  5. brianm

    brianm Guest

    Here it is again...

    7
    6 8
    5 9 2 12
    4 10 3 11 1 13 0 14
     
    brianm, Jan 10, 2005
    #5
  6. brianm

    Bjorn Abelli Guest

    "brianm" wrote...
    > Here it is again...


    And it's still difficult to comprehend...

    > 7
    > 6 8
    > 5 9 2 12
    > 4 10 3 11 1 13 0 14



    Binary tree roots doesn't have "middle nodes", only left and right nodes
    ("binary" means "two").

    My guess is that you try to show that, and you just don't know how to
    replace tabs with spaces?


    So if we reformat your tree accordingly...

    7
    6 8
    5 9 2 12
    4 10 3 11 1 13 0 14

    ....we find several mistakes in the tree.

    As Mike wrote, *every* node to the left, *including* subnodes, must be less
    than the root.


    To show a small example:

    8
    3 11
    1 5 9 13


    Look closely to the tree, and you see that *every* number on the right of
    *any* other number in the tree is higher. If we *flatten* the tree, it would
    look like:

    1 3 5 8 9 11 13

    I hope you see the logic. Note that an implementation of a binary tree in
    many cases contains "empty" nodes, as it's difficult to predict how the
    nodes to be inserted are distributed.

    This is also a valid binary tree, though "unbalanced" (x stands for empty
    nodes).

    7
    2 x
    x 5


    To implement a balanced tree "cost" more upon insertion, as it includes
    moving already inserted nodes to new places. The tree above would after
    balancing look like:

    5
    2 7

    In *both* cases you can see it flattened like:

    2 5 7

    ----------------------

    public class Node
    {
    private Node left = null;
    private Node right = null;
    private int value;

    Node(int i)
    {
    value = i;
    }

    public add(int i)
    {
    if (i > value)
    {
    if (right == null) right = new Node(i);
    else right.add(i);
    }
    else if (i < value)
    {
    if (left == null) left = new Node(i);
    else left.add(i);
    }
    }

    public int getValue() { return value; }
    }

    -------------------------

    // Bjorn A
     
    Bjorn Abelli, Jan 10, 2005
    #6
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Stub

    B tree, B+ tree and B* tree

    Stub, Nov 12, 2003, in forum: C Programming
    Replies:
    3
    Views:
    10,204
  2. Tarique Jawed

    binary search tree removal - stuck - HELP!!

    Tarique Jawed, Dec 6, 2003, in forum: C Programming
    Replies:
    4
    Views:
    426
    Ben Pfaff
    Dec 7, 2003
  3. tsunami
    Replies:
    3
    Views:
    352
    Mark P
    Aug 6, 2005
  4. bushido
    Replies:
    2
    Views:
    383
    sassa
    Jan 23, 2008
  5. Bogdan

    Binary tree search vs Binary search

    Bogdan, Oct 18, 2010, in forum: C Programming
    Replies:
    22
    Views:
    3,204
    Michael Angelo Ravera
    Oct 21, 2010
Loading...

Share This Page