Node(3pm)

✨ NAME ✨

okay so bestie, this is Node(3pm) from the User Contributed Perl Documentation — aka Tree::RedBlack::Node — Node class for Perl implementation of Red/Black tree. she's literally the building block of the whole tree, no cap 🫶💖

✨ 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 () — the key of the node. this is what the nodes are sorted by in the tree, so it's the main character of the ordering vibe 👑
• val ($) — the value of the node. can be any perl scalar, so it could be a hash-ref, for example. this can be set directly. yes bestie, direct set, we love a mutable moment 💅
• color () — the color of the node. 1 for "red", 0 or undef for "black". that's the whole red/black thing, periodt 🎀
• parent () — parent node of this one. returns undef for the root node. root has no parent, she's independent ✨
• left () — left child node of this one. returns undef for leaf nodes. leaf means no left baby, okay? 🍓
• right () — right child node of this one. returns undef for leaf nodes. same energy on the right side 🦋
• min () — returns the node with the minimal key starting from this node. go find the smallest, bestie 🔥
• max () — returns the node with the maximal key starting from this node. go find the biggest, slay 💖
• 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. so if you're already maxxed out, you get yourself back, iconic 🌈
• predecessor () — similar to successor. WARNING: NOT YET IMPLEMENTED!! do not come for her, she is not ready 😭💀

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... noted, bestie 🧚💅

✨ AUTHOR ✨

Benjamin Holzman <bholzman@earthlink.net> — the author of this whole vibe, give her a follow or whatever 💖

✨ SEE ALSO ✨

Tree::RedBlack — go check out the main tree module, iykyk 🌈

---

kisses bestie, this page is from perl v5.36.0, dated 2022-10-22, and it's literally Node(3pm) — periodt 💅✨