tree::redblack(3pm) [debian 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)

Forest::Tree(3pm)					User Contributed Perl Documentation					 Forest::Tree(3pm)

NAME

       Forest::Tree - An n-ary tree

SYNOPSIS

	 use Forest::Tree;

	 my $t = Forest::Tree->new(
	     node     => 1,
	     children => [
		 Forest::Tree->new(
		     node     => 1.1,
		     children => [
			 Forest::Tree->new(node => 1.1.1),
			 Forest::Tree->new(node => 1.1.2),
			 Forest::Tree->new(node => 1.1.3),
		     ]
		 ),
		 Forest::Tree->new(node => 1.2),
		 Forest::Tree->new(
		     node     => 1.3,
		     children => [
			 Forest::Tree->new(node => 1.3.1),
			 Forest::Tree->new(node => 1.3.2),
		     ]
		 ),
	     ]
	 );

	 $t->traverse(sub {
	     my $t = shift;
	     print(('	 ' x $t->depth) . ($t->node || 'undef') . "
");
	 });

DESCRIPTION

       This module is a basic n-ary tree, it provides most of the functionality of Tree::Simple, whatever is missing will be added eventually.

       This class inherits from Forest::Tree::Pure>, but all shared methods and attributes are documented in both classes.

ATTRIBUTES

       node
       uid
       parent
	   parent
	   _set_parent
	   has_parent
	   clear_parent
       children
	   get_child_at ($index)
	       Return the child at this position. (zero-base index)

	   child_count
	       Returns the number of children this tree has

       size
	   size
	   has_size
	   clear_size
       height
	   height
	   has_height
	   clear_height

METHODS

       is_root
	   True if the current tree has no parent

       is_leaf
	   True if the current tree has no children

       depth
	   Return the depth of this tree. Root has a depth of -1

       add_child ($child)
       add_children (@children)
	   Add a new child. The $child must be a "Forest::Tree"

       insert_child_at ($index, $child)
	   Insert a child at this position. (zero-base index)

       remove_child_at ($index)
	   Remove the child at this position. (zero-base index)

       traverse (&func)
	   Takes a reference to a subroutine and traverses the tree applying this subroutine to every descendant.

       siblings
	   Returns an array reference of all siblings (not including us)

       to_pure_tree
	   Invokes "reconstruct_with_class" with Forest::Tree::Pure.

       to_mutable_tree
	   Returns the invocant (without cloning).

       clone
	   See "clone" in Forest::Tree::Pure.

	   This variant will not clone the parent, but return a clone of the subtree that is detached.

       get_index_in_siblings
	   Returns the index of the tree in the list of children.

	   Equivalent to calling "$tree-"parent->get_child_index($tree)>.

	   Returns -1 if the node has no parent (the root node).

BUGS

       All complex software has bugs lurking in it, and this module is no exception. If you find a bug please either email me, or add the bug to
       cpan-RT.

AUTHOR

       Stevan Little <stevan.little@iinteractive.com>

COPYRIGHT AND LICENSE

       Copyright 2008-2010 Infinity Interactive, Inc.

       <http://www.iinteractive.com>

       This library is free software; you can redistribute it and/or modify it under the same terms as Perl itself.

perl v5.10.1							    2010-09-27							 Forest::Tree(3pm)