CODEWITHSUNDEEP
perldata-structurestree
user3001803
user3001803

Reputation: 13

how to assign to a variable the reference towards a key in a hash

I need to traverse a binary tree. The values of the tree are located in a hash.

I used the Data::Dumper module to visualize the hash, but the pointer (the variable that shows where in the tree we are located when we travel) won't accept the reference to the tree.

This is a simplified version of my code

#!/usr/bin/perl
use v5.10;
use Data::Dumper;

# ID = id of the nod in the tree     
# 'v' = value of the nod  
# 'p' = id of the father nod  
# '+' = son of the nod ( bigger than father)
# '-' = son of the nod ( smaller than father)  

my $tree = {

    'id' => 0,
    'v' => 12,
    '+' => { 
            'id' => 1,
            'p' => 12,
            'v' => 18,
        }
};

my $pointer = $tree -> { '+' } -> { 'id' };      

# travel trough the tree
while(exists  ($pointer -> {'p'}))      # while $pointer will have a father
  $noeud_courant =  $noeud_courant->{'p'};  # give $pointer the value of the father i                   
}

say "value of the first father = $pointer -> { 'v' } ";

Upvotes: 1

Views: 102

Answers (1)

Mark Dominus
Mark Dominus

Reputation: 1808

When you have a node $n with $n->{p} equal to 12, you want to be able to find from this the node $p that has $p->{id} equal to 12. But your program doesn't contain anything that would allow it to easily find the node $p. You need to add this.

One way to do this is to assemble an index that maps ID numbers to tree nodes. An index is just an array where $index[$n] is the tree node whose ID number is $n. This function, run on the root of your tree, builds an index for it:

sub index_tree {
  my ($root, $index) = @_;
  $index->[$root->{id}] = $root;
  for my $sub_node (values %$root) {
    next unless ref $sub_node eq "HASH";
    index_tree($sub_node, $index);
  }
}

To use this, call:

my @index;
index_tree($tree, \@index);

Now @index is your index. Suppose you have $pointer = 1 as in your example, and you want to trace back up to the root. You could use:

while (defined $pointer) {
  my $node = $index[$pointer];
  $pointer = $node->{p};
}

At each step through the loop, $pointer is the ID of the current node and $node is the current node itself.

If the space of IDs is sparse, it would be appropriate to use a hash instead of an array for the index.

Instead of storing the index in a separate array, you could replace the p entries with pointers back to the parent nodes themselves:

sub fix_parent_pointers {
  my ($root) = @_;
  for my $sub_node (values %$root) {
    next unless ref $sub_node eq "HASH";
    $sub_node->{p} = $root;
    fix_parent_points($sub_node);
  }
}

fix_parent_pointers($tree);

After doing this, each node, except the root, has its entire parent node stored in its p element in place of the ID number. If $node is a node, you can now trace back up to the root by doing this:

while (exists $node->{p}) {
  $node = $node->{p};
}

The major drawback of this technique is that Perl will no longer be able to garbage-collect your tree when you are done with it. This can be avoided by weakening the parent reference with Scalar::Util::weaken() so it does not obstruct garbage collection:

use Scalar::Util qw/weaken/;
...
$sub_node->{p} = $root;
weaken($sub_node->{p});
...

Upvotes: 1

Related Questions