Build Balanced Tree

[alexbarham]

Hello,

I am working through Mastering Algorithms with PERL. I am reading about
binary trees and how to keep them balanced. The example code shows tree
manipulation but doesn't show how to build the tree. I would like to
try out the sample code. However, I don't quite understand how to build
a binary tree. If I wanted to build a tree with one left node having a
value of 1 and a right node with a value of 2, how would I do it? Is it
a hash of hashes as in?:

my %tree = {
{left=>0,
right=>1,
val=>1}
left=>1,
right=>0,
val=>2}
};
Is it an array of array?
my @tree = [[0,0,1],[1,0,2]];

Or is it more flexible than this. Any help would be greatly appreciated!

 

[xhoster]

Hello,

I am working through Mastering Algorithms with PERL. I am reading about
binary trees and how to keep them balanced. The example code shows tree
manipulation but doesn't show how to build the tree. I would like to
try out the sample code.

What sample code? From what I can tell through Google, that book appears
to have several pieces of sample code.

However, I don't quite understand how to build
a binary tree.

You create an empty tree, and then you insert thing into it. Do they
provide the code for doing these two thing?

If I wanted to build a tree with one left node having a
value of 1 and a right node with a value of 2, how would I do it?

Generally, you wouldn't. You insert a 1 and 2 into the tree, and they
get placed where the algorithm places them. (Aside from which, you have a
3 node tree but only specified the values of 2 of the nodes.)

Is it
a hash of hashes as in?:

It could be a hash of hashes.

my %tree = {
{left=>0,
right=>1,
val=>1}
left=>1,
right=>0,
val=>2}
};

That is wrong on so many levels. It has syntax errors, and you are
confusing {} with ().

Somehting more like this:
my $tree_ref = {
val => 'unknown',
left => {
val => '1',
},
right => {
val => '2',
}
};

Is it an array of array?

It could also be that.

my @tree = [[0,0,1],[1,0,2]];

This is wrong on less levels, but still wrong. You need three nodes (root,
left, right), but you only have two.

Anyway, if you look at the specific piece of sample code that you are
interested in, it should be obvious what the representation is.

Or is it more flexible than this.

If they are to be balanced, they probably have to be more flexible than
this.

Xho

 

[Andrew McGregor]

I am working through Mastering Algorithms with PERL. I am reading about
binary trees and how to keep them balanced. The example code shows tree
manipulation but doesn't show how to build the tree. I would like to
try out the sample code. However, I don't quite understand how to build
a binary tree. If I wanted to build a tree with one left node having a
value of 1 and a right node with a value of 2, how would I do it? Is it
a hash of hashes as in?:

Use sub basic_tree_add to build the tree, page 77.

my %tree = {

If you want to pre-declare the tree, again build it as above, then use
Data:umper to see the structure.

die Data:umper $tree;