Build Balanced Tree

Discussion in 'Perl Misc' started by alexbarham@yahoo.ca, Nov 6, 2005.

  1. Guest

    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!
     
    , Nov 6, 2005
    #1
    1. Advertising

  2. Guest

    wrote:
    > 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

    --
    -------------------- http://NewsReader.Com/ --------------------
    Usenet Newsgroup Service $9.95/Month 30GB
     
    , Nov 6, 2005
    #2
    1. Advertising

  3. wrote:
    > 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::Dumper to see the structure.

    die Data::Dumper $tree;
     
    Andrew McGregor, Nov 8, 2005
    #3
    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. Luc The Perverse

    Balanced Tree

    Luc The Perverse, Feb 20, 2006, in forum: Java
    Replies:
    8
    Views:
    784
    Chris Uppal
    Feb 22, 2006
  2. Kenneth McDonald

    Balanced tree type coming in next Python?

    Kenneth McDonald, Jun 7, 2004, in forum: Python
    Replies:
    6
    Views:
    443
    Christos TZOTZIOY Georgiou
    Jun 8, 2004
  3. Replies:
    7
    Views:
    901
  4. Replies:
    1
    Views:
    338
  5. cgirl
    Replies:
    1
    Views:
    369
    red floyd
    Jun 26, 2009
Loading...

Share This Page