tree::node(3pm) [debian man page]

Node(3pm)						User Contributed Perl Documentation						 Node(3pm)

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 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, "
";
	     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...

AUTHOR

       Benjamin Holzman <bholzman@earthlink.net>

SEE ALSO

       Tree::RedBlack

perl v5.10.0							    2008-07-31								 Node(3pm)

Check Out this Related Man Page

RedBlack(3pm)						User Contributed Perl Documentation					     RedBlack(3pm)

NAME

       Tree::RedBlack - Perl implementation of Red/Black tree, a type of balanced tree.

SYNOPSIS

	 use Tree::RedBlack;

	 my $t = new Tree::RedBlack;
	 $t->insert(3, 'cat');
	 $t->insert(4, 'dog');
	 my $v = $t->find(4);
	 my $min = $t->min;
	 my $max = $t->max;
	 $t->delete(3);
	 $t->print;

DESCRIPTION

       This is a perl implementation of the Red/Black tree algorithm found in the book "Algorithms", by Cormen, Leiserson & Rivest (more commonly
       known as "CLR" or "The White Book").  A Red/Black tree is a binary tree which remains "balanced"- that is, the longest length from root to
       a node is at most one more than the shortest such length.  It is fairly efficient; no operation takes more than O(lg(n)) time.

       A Tree::RedBlack object supports the following methods:

       new ()
	   Creates a new RedBlack tree object.

       root ()
	   Returns the root node of the tree.  Note that this will either be undef if no nodes have been added to the tree, or a
	   Tree::RedBlack::Node object.  See the Tree::RedBlack::Node manual page for details on the Node object.

       cmp (&)
	   Use this method to set a comparator subroutine.  The tree defaults to lexical comparisons.  This subroutine should be just like a
	   comparator subroutine to sort, except that it doesn't do the $a, $b trick; the two elements to compare will just be the first two items
	   on the stack.

       insert ($;$)
	   Adds a new node to the tree.  The first argument is the key of the node, the second is its value.  If a node with that key already
	   exists, its value is replaced with the given value and the old value is returned.  Otherwise, undef is returned.

       delete ($)
	   The argument should be either a node object to delete or the key of a node object to delete. WARNING!!! THIS STILL HAS BUGS!!!

       find ($)
	   Searches the tree to find the node with the given key.  Returns the value of that node, or undef if a node with that key isn't found.
	   Note, in particular, that you can't tell the difference between finding a node with value undef and not finding a node at all.  If you
	   want to determine if a node with a given key exists, use the node method, below.

       node ($)
	   Searches the tree to find the node with the given key.  Returns that node object if it is found, undef otherwise.  The node object is a
	   Tree::RedBlack::Node object.

       min ()
	   Returns the node with the minimal key.

       max ()
	   Returns the node with the maximal key.

AUTHOR

       Benjamin Holzman <bholzman@earthlink.net>

SEE ALSO

       Tree::RedBlack::Node

perl v5.10.0							    2008-07-31							     RedBlack(3pm)

Linux and UNIX Man Pages

tree::node(3pm) [debian man page]

Check Out this Related Man Page