Skip site navigation (1)Skip section navigation (2)

FreeBSD Manual Pages


home | help
Node(3)		      User Contributed Perl Documentation	       Node(3)

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

       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);

       You would call it like this:

	   my $t = new Tree::RedBlack;
	   open(FILE, ">tree.dump");
	   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	<>


perl v5.32.0			  2008-07-31			       Node(3)


Want to link to this manual page? Use this URL:

home | help