creating a binary tree

Popping mad

unread,

Nov 20, 2016, 2:24:40 AM11/20/16

to

I know someone must have solved this problem at some point.

Lets say I have an array with 500 randon ints between 0-9999

I want to build a binary tree from the data in the array. Each node has
pointers to children nodes, a value and a point to a parent node, just
incase you want to look up.

How can you build this? A recursive function goes straight down the left
side.

Alf P. Steinbach

unread,

Nov 20, 2016, 6:16:01 AM11/20/16

to

Well that's the degenerate case of sorted input. But you say it's random.

I'd build the tree first and worry about balancing it after.

Cheers!,

- Alf

Alf P. Steinbach

unread,

Nov 20, 2016, 8:16:58 AM11/20/16

to

On 20.11.2016 12:23, Stefan Ram wrote:

> I cannot find a requirement in the OP that say that the
> binary tree needs to be balanced.
>
> Implementing functionality that is not required might have
> disadvantages:
>
> - might increase the project duration
> - might increase the product costs
> - might offer more surface for bugs and attacks
> - the additional work might be multiplied when
> documentation, tests and reviews are to be done
> for the added functionality
>

Are you for real?

Cheers!,

- Alf

ruben safir

unread,

Nov 20, 2016, 9:17:07 AM11/20/16

to

On 11/20/2016 05:13 AM, Stefan Ram wrote:
> for_each( array.begin(), array.end(), insert_into_tree );

/dev/null - bye

Jerry Stuckle

unread,

Nov 20, 2016, 5:47:32 PM11/20/16

to

https://www.tutorialspoint.com/data_structures_algorithms/avl_tree_algorithm.htm
has a good example of algorithms It's not too hard to balance one once
you understand the rotations. And the overhead of maintaining balance
is pretty low.

I did it in C, but that's been probably 25 years ago and I don't have
that code any more. But the code wasn't that big.

--
==================
Remove the "x" from my email address
Jerry Stuckle
jstu...@attglobal.net
==================

ruben safir

unread,

Nov 21, 2016, 3:58:19 PM11/21/16

to

On 11/20/2016 05:47 PM, Jerry Stuckle wrote:
> On 11/20/2016 2:24 AM, Popping mad wrote:
>> I know someone must have solved this problem at some point.
>>
>> Lets say I have an array with 500 randon ints between 0-9999
>>
>> I want to build a binary tree from the data in the array. Each node has
>> pointers to children nodes, a value and a point to a parent node, just
>> incase you want to look up.
>>
>> How can you build this? A recursive function goes straight down the left
>> side.
>>
>
> https://www.tutorialspoint.com/data_structures_algorithms/avl_tree_algorithm.htm
> has a good example of algorithms It's not too hard to balance one once
> you understand the rotations. And the overhead of maintaining balance
> is pretty low.
>
> I did it in C, but that's been probably 25 years ago and I don't have
> that code any more. But the code wasn't that big.
>

FWIW

makefile

main.cpp

maxpath.cpp

maxpath.h

Ike Naar

unread,

Nov 22, 2016, 2:23:15 AM11/22/16

to

That's strange, if the ints in the array are random.
Can you show the code of the recursive function?

Tim Rentsch

unread,

Nov 22, 2016, 10:39:14 AM11/22/16

to

Sort the array, then build a balanced tree recursively based on
an array parameter. Here is pseudocode written in a C-like
language to do the tree building:

Tree
balanced_tree_from_sorted_array( Size n, signed values[n] ){
if( n == 0 ) return 0;

if( n == 1 ) return new_tree_node( values[0] );

if( n == 2 ){
Tree a = new_tree_node( values[0] );
Tree b = new_tree_node( values[1] );
a->right = b, b->parent = a;
return a;
}

Tree a = balanced_tree_from_sorted_array( n/2, values );
Tree b = new_tree_node( values[n/2] );
Tree c = balanced_tree_from_sorted_array( (n-1)/2, values + (n/2+1) );
assert( n/2 + 1 + (n-1)/2 == n );
a->parent = b, b->left = a;
c->parent = b, b->right = c;
return b;
}