|
|
STX B+ Tree 0.8.1 (Default branch)
01-26-2008
The STX B+ Tree package is a set of C++ template classes implementing a B+ tree key/data container in main memory. The classes are designed as drop-in replacements of the STL containers set, map, multiset, and multimap, and follow their interfaces very closely. By packing multiple value pairs into each node of the tree, the B+ tree reduces heap fragmentation and utilizes cache-line effects better than the standard red-black binary tree. The tree algorithms are based on the implementation in Cormen, Leiserson, and Rivest's Introduction into Algorithms, Jan Jannink's paper, and other algorithm resources. The classes contain extensive assertion and verification mechanisms to ensure the implementation's correctness by testing the tree invariants. License: GNU Lesser General Public License (LGPL) Changes:|
|
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)