---
name: "Tree::Node"
section: "3pm"
platform: "linux"
package: "libtree-redblack-perl"
version: "0.5-4"
release: "Debian 13 (Trixie)"
platforms: ["linux"]
url: "https://new.carta.tech/Tree::Node"
---

# Tree::Node(3pm)

Node class for Perl implementation of Red/Black tree

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