Basic tree - compare question

Cristoforo has asked for the wisdom of the Perl Monks concerning the following question:

I'm reading the Mastering Algorithms with Perl book (O'Reilly) and am wondering if someone could enlighten me on a part of a function where a compare is done. The code is:

sub basic_tree_find {
    my ($tree_link, $target, $cmp) = @_;
    my $node;

    # $tree_link is the next pointer to be followed.
    # It will be undef if we reach the bottom of the tree.
    while ( $node = $$tree_link ) {
        local $^W = 0;      # no warnings, we expect undef values

        my $relation = ( defined $cmp
                    ? $cmp->( $target, $node->{val} )
                    : $target <=> $node->{val} );

        # If we found it, return the answer.
        return ($tree_link, $node) if $relation == 0;

        # Nope - prepare to descend further - decide which way we go.
        $tree_link = $relation > 0 ? \$node->{left} : \$node->{right};
    }

    # We fell off the bottom, so the element isn't there, but we
    # tell caller where to create a new element (if desired).
    return ($tree_link, undef);
}
[download]

The line that I'm questioning is
$tree_link = $relation > 0 ? \$node->{left} : \$node->{right};

$relation will be greater than 0 (read = 1) if $target is greater than $node->{val}. And this is where I'm confused. If that is the case wouldn't you want to traverse down $node->{right} instead of $node->{left}?

Thanks for any help given here :-)

Chris

Comment on Basic tree - compare question Select or Download Code

Replies are listed 'Best First'.
Re: Basic tree - compare question by dragonchild (Archbishop) on Oct 09, 2007 at 03:06 UTC
If you're talking about a tree where smaller values are to the left and larger values are to the right, then yes - you've found a typo. Now, personally, I would never write tree code that way (and I didn't - I wrote Tree and help maintain Tree::Simple). This is C code translated to Perl. It doesn't take advantage of Perl's specialnesses. My criteria for good software: Does it work? Can someone else come in, make a change, and be reasonably certain no bugs were introduced?	[reply]
Re: Basic tree - compare question by GrandFather (Saint) on Oct 09, 2007 at 02:30 UTC
Depends which way you build the tree I guess. The important thing is that you are consistent when building and traversing the tree. Note that this sub can be used to traverse the tree while adding and also later on while searching so as far as a user of the tree is concerned they might not ever need to know. Perl is environmentally friendly - it saves trees	[reply]
Re: Basic tree - compare question by Cristoforo (Curate) on Oct 09, 2007 at 03:31 UTC
I was assuming that greater values went to the right and lesser to the left (as all the pictures of sample trees in the book showed). Also made this assumtion when learning trees in one of my Data structure courses - and thats the order we built them. But as Grandfather says, either way would be ok as its hidden from the user. I did build a tree just now (using the code from the book), and reversed the order to put greater values to the right and Data::Dumper showed me the structure I was looking for. Thanks for the tip on the Tree modules, Dragonchild. I'll give them a closer look tomorrow. If I do need to use them I will consider looking at these modules. I imagine being written in C, it may be faster and they have many features. However, I'm trying to re-learn what I had in school 8 years ago (water under the bridge :-) ). Thanks for the input everyone.	[reply]
Re^2: Basic tree - compare question by dragonchild (Archbishop) on Oct 09, 2007 at 12:08 UTC
Tree and Tree::Simple aren't written in C - they're written in Perl. Very fast optimized Perl, but Perl nonetheless. THe C I was referring to was how the example code was structured. My criteria for good software: Does it work? Can someone else come in, make a change, and be reasonably certain no bugs were introduced?	[reply]