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

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

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

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 this node 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/black trees. For instance, here's a routine which writes a tree out to disk, putting the byte offsets of the left and right child records in the record for each node.

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 of the 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 of Tree::RedBlack::Node, and then allow the Tree::RedBlack constructor to take an argument saying what class of node it should be made up out of. Hmmm...

Benjamin Holzman <bholzman@earthlink.net>

Tree::RedBlack

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