MAN page from Old RedHat 6.X perl-Tree-RedBlack-0.3-6.i386.rpm

Node

Section: User Contributed Perl Documentation (3)
Updated: perl 5.005, patch 03
Index

NAME

Tree::RedBlack::Node - Node class for Perl implementation of Red/Black tree

SYNOPSIS

use Tree::RedBlack;my $t = new Tree::RedBlack;$t->insert(3, `dog');my $node = $t->node(3);$animal = $node->val;

DESCRIPTION

A Tree::RedBlack::Node object supports the following methods:

key (): Key of the node. This is what the nodes are sorted by in the tree.
val ($): Value of the node. Can be any perl scalar, so it could be a hash-ref,f'rinstance. This can be set directly.
color (): Color of the node. 1 for ``red'', 0 or undef for ``black''.
parent (): Parent node of this one. Returns undef for root node.
left (): Left child node of this one. Returns undef for leaf nodes.
right (): Right child node of this one. Returns undef for leaf nodes.
min (): Returns the node with the minimal key starting from this node.
max (): Returns the node with the maximal key starting from this node.
successor (): Returns the node with the smallest key larger than this node's key, or thisnode if it is the node with the maximal key.
predecessor (): Similar to successor. WARNING: NOT YET IMPLEMENTED!!

You can use these methods to write utility routines for actions on red/blacktrees. For instance, here's a routine which writes a tree out to disk, puttingthe byte offsets of the left and right child records in the record for eachnode.

    sub dump {      my($node, $fh) = @_;      my($left, $right);      my $pos = tell $fh;      print $fh $node->color ? 'R' : 'B';      seek($fh, 8, 1);      print $fh $node->val;      if ($node->left) {        $left = dump($node->left,$fh);      }      if ($node->right) {         $right = dump($node->right,$fh);      }      my $end = tell $fh;      seek($fh, $pos+1, 0);      print $fh pack('NN', $left, $right);      seek($fh, $end, 0);      $pos;    }

You would call it like this:

    my $t = new Tree::RedBlack;    ...    open(FILE, ">tree.dump");    dump($t->root,\*FILE);    close FILE;

As another example, here's a simple routine to print a human-readable dump ofthe tree:

    sub pretty_print {      my($node, $fh, $lvl) = @_;      if ($node->right) {        pretty_print($node->right, $fh, $lvl+1);      }      print $fh ' 'x($lvl*3),'[', $node->color ? 'R' : 'B', ']', $node->key, "\n";      if ($node->left) {        pretty_print($this->left, $fh, $lvl+1);      }    }

A cleaner way of doing this kind of thing is probably to allow sub-classing ofTree::RedBlack::Node, and then allow the Tree::RedBlack constructor to take anargument saying what class of node it should be made up out of. Hmmm...

AUTHOR

Benjamin Holzman <bholzmanAATTearthlink.net>

This document was created byman2html,using the manual pages.