Binary search Tree:Help  
Index ‹ java-programmer
Author Message
brianm
PostPosted: 2005-1-10 8:36:00 Top
java-programmer, Binary search Tree:Help 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

 
Mike Schilling
PostPosted: 2005-1-10 9:32:00 Top
java-programmer >> Binary search Tree:Help
"brianm" <email***@***.com> wrote in message
news:email***@***.com...
> 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.


 
klynn47
PostPosted: 2005-1-10 9:32:00 Top
java-programmer >> Binary search Tree:Help 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.

 
 
lee
PostPosted: 2005-1-10 9:38:00 Top
java-programmer >> Binary search Tree:Help In article <email***@***.com>, "brianm" <email***@***.com> 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
 
 
brianm
PostPosted: 2005-1-10 9:41:00 Top
java-programmer >> Binary search Tree:Help Here it is again...

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

 
 
Bjorn Abelli
PostPosted: 2005-1-10 19:42:00 Top
java-programmer >> Binary search Tree:Help
"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



 
 
 
Index ‹ java-programmer