Tree::RB::Node(3) A node class for implementing Red/Black trees

VERSION

This document describes Tree::RB::Node version 0.0.1

SYNOPSIS


use Tree::RB;
my $tree = Tree::RB->new;
$tree->put('France' => 'Paris');
$tree->put('England' => 'London');
my $node = $tree->delete('France'); # $node is a Tree::RB::Node object
print $node->key; # 'France'
print $node->val; # 'Paris'

DESCRIPTION

A Tree::RB tree is made up of nodes that are objects of type Tree::RB::Node

INTERFACE

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

new()

Creates and returns a new node.

key([KEY])

Get/set the key of the node. This is what the nodes are sorted by in the tree.

val([VALUE])

Get/set the value of the node. This can be any scalar.

color([COLOR])

Get/set the color of the node. Valid colors are the constants RED and BLACK which are exported by Tree::RB::Node::_Constants

parent([PARENT])

Get/set the parent of the node, which must be another Tree::RB::Node object.

left([NODE])

Get/set the left child node of the node, which must be another Tree::RB::Node object.

right([NODE])

Get/set the right child node of the node, which must be another Tree::RB::Node object.

min()

Returns the node with the minimal key starting from this node.

max()

Returns the node with the maximal key starting from this node.

leaf()

Returns the first leaf node found starting from this node, using a depth first, left to right search.

successor()

Returns the node with the smallest key larger than this node's key, or "undef" if it is the node with the maximal key.

predecessor()

Returns the node with the greatest key smaller than this node's key, or "undef" if it is the node with the minimal key.

as_lol([NODE])

Returns a list of lists representing the tree whose root is either NODE if NODE is specified, or this node otherwise.

This could be used for printing a tree, as the following snippet shows (this assumes that Tree::DAG_Node is also installed)

    use strict;
    use Tree::DAG_Node;
    use Tree::RB;
    my $t = Tree::RB->new;
    foreach (qw/the rain in spain falls mainly in the plains/) {
        $t->put($_, "${_} val");
    }
    my $tree = Tree::DAG_Node->lol_to_tree( $t->root->as_lol );
    $, = "\n";
    print @{ $tree->draw_ascii_tree };

This will print

                      |
                   <B:rain>
               /-------------------\
               |                   |
             <R:in>             <B:the>
        /-----------\            /------\
        |           |            |      |
    <B:falls>   <B:mainly>   <R:spain> <*>
      /---\    /------\        /---\
      |   |    |      |        |   |
     <*> <*>  <*> <R:plains>  <*> <*>
                    /---\
                    |   |
                   <*> <*>

strip([$callback])

Strips off all nodes under this node. If a callback is specified, it will be called once for each node that is detached, with the detached node as its sole argument.

DEPENDENCIES

None.

INCOMPATIBILITIES

None reported.

BUGS AND LIMITATIONS

Please report any bugs or feature requests to "[email protected]", or through the web interface at <http://rt.cpan.org>.

AUTHOR

Arun Prasad "<[email protected]>"

Some documentation has been borrowed from Benjamin Holzman's Tree::RedBlack::Node

LICENCE AND COPYRIGHT

Copyright (c) 2007, Arun Prasad "<[email protected]>". All rights reserved.

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

DISCLAIMER OF WARRANTY

BECAUSE THIS SOFTWARE IS LICENSED FREE OF CHARGE, THERE IS NO WARRANTY FOR THE SOFTWARE, TO THE EXTENT PERMITTED BY APPLICABLE LAW. EXCEPT WHEN OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR OTHER PARTIES PROVIDE THE SOFTWARE ``AS IS'' WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE SOFTWARE IS WITH YOU. SHOULD THE SOFTWARE PROVE DEFECTIVE, YOU ASSUME THE COST OF ALL NECESSARY SERVICING, REPAIR, OR CORRECTION.

IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN WRITING WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY AND/OR REDISTRIBUTE THE SOFTWARE AS PERMITTED BY THE ABOVE LICENCE, BE LIABLE TO YOU FOR DAMAGES, INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OR INABILITY TO USE THE SOFTWARE (INCLUDING BUT NOT LIMITED TO LOSS OF DATA OR DATA BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY YOU OR THIRD PARTIES OR A FAILURE OF THE SOFTWARE TO OPERATE WITH ANY OTHER SOFTWARE), EVEN IF SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES.