GSP
Quick Navigator

Search Site

Unix VPS
A - Starter
B - Basic
C - Preferred
D - Commercial
MPS - Dedicated
Previous VPSs
* Sign Up! *

Support
Contact Us
Online Help
Handbooks
Domain Status
Man Pages

FAQ
Virtual Servers
Pricing
Billing
Technical

Network
Facilities
Connectivity
Topology Map

Miscellaneous
Server Agreement
Year 2038
Credits
 

USA Flag

 

 

Man Pages


Manual Reference Pages  -  TREE::NODE (3)

.ds Aq ’

NAME

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

CONTENTS

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

AUTHOR

Benjamin Holzman <bholzman@earthlink.net>

SEE ALSO

Tree::RedBlack
Search for    or go to Top of page |  Section 3 |  Main Index


perl v5.20.3 NODE (3) 2008-07-31

Powered by GSP Visit the GSP FreeBSD Man Page Interface.
Output converted with manServer 1.07.