Velocity Reviews > Java > Binary search Tree:Help

Binary search Tree:Help

brianm
Guest
Posts: n/a

 01-10-2005
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

klynn47@comcast.net
Guest
Posts: n/a

 01-10-2005
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.

Mike Schilling
Guest
Posts: n/a

 01-10-2005

"brianm" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed) ups.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.

Lee Weiner
Guest
Posts: n/a

 01-10-2005
In article <(E-Mail Removed). com>, "brianm" <(E-Mail Removed)> 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
Guest
Posts: n/a

 01-10-2005
Here it is again...

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

Bjorn Abelli
Guest
Posts: n/a

 01-10-2005

"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;
}

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

public int getValue() { return value; }
}

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

// Bjorn A