Tree::RB(3pm)

💖 Tree::RB 💖

okay bestie, sit down, hydrate, because we're about to talk about Tree::RB — a Perl implementation of the Red/Black tree, which is a type of balanced binary search tree. yes. a whole balanced binary search tree. in Perl. we ate. 💅

---

✨ NAME ✨

Tree::RB — Perl implementation of the Red/Black tree, a type of balanced binary search tree. iconic behavior honestly 🌈

---

🌸 SYNOPSIS 🌸

here's the whole vibe in one go, no cap:

use Tree::RB;

my $tree = Tree::RB->new;
$tree->put('France'  => 'Paris');
$tree->put('England' => 'London');
$tree->put('Hungary' => 'Budapest');
$tree->put('Ireland' => 'Dublin');
$tree->put('Egypt'   => 'Cairo');
$tree->put('Germany' => 'Berlin');

$tree->put('Alaska' => 'Anchorage'); # D'oh! Alaska isn't a Country
$tree->delete('Alaska');

print scalar $tree->get('Ireland'); # 'Dublin'

print $tree->size; # 6
print $tree->min->key; # 'Egypt'
print $tree->max->key; # 'Ireland'

print $tree->nth(0)->key;  # 'Egypt'
print $tree->nth(-1)->key; # 'Ireland'

# print items, ordered by key
my $it = $tree->iter;

while(my $node = $it->next) {
    printf "key = %s, value = %s\n", $node->key, $node->val;
}

# print items in reverse order
$it = $tree->rev_iter;

while(my $node = $it->next) {
    printf "key = %s, value = %s\n", $node->key, $node->val;
}

# Hash interface
tie my %capital, 'Tree::RB';

# or do this to store items in descending order
tie my %capital, 'Tree::RB', sub { $_[1] cmp $_[0] };

$capital{'France'}  = 'Paris';
$capital{'England'} = 'London';
$capital{'Hungary'} = 'Budapest';
$capital{'Ireland'} = 'Dublin';
$capital{'Egypt'}   = 'Cairo';
$capital{'Germany'} = 'Berlin';

# print items in order
while(my ($key, $val) = each %capital) {
    printf "key = $key, value = $val\n";
}

not the Alaska moment 💀 — she really put a whole US state in a countries list and then had to delete it. we've all been there bestie.

---

🦋 DESCRIPTION 🦋

This is a Perl implementation of the Red/Black tree, a type of balanced binary search tree.

A tied hash interface is also provided to allow ordered hashes to be used. yes queen, ordered hashes, the dream 🎀

See the Wikipedia article at <http://en.wikipedia.org/wiki/Red-black_tree> for further information about Red/Black trees. go read it. expand your mind. 🧚

---

👑 INTERFACE 👑

🌟 new([CODEREF]) 🌟

Creates and returns a new tree. If a reference to a subroutine is passed to new(), the subroutine will be used to override the tree's default lexical ordering and provide a user a defined ordering.

This subroutine should be just like a comparator subroutine used with sort, except that it doesn't do the $a, $b trick.

For example, to get a case insensitive ordering:

my $tree = Tree::RB->new(sub { lc $_[0] cmp lc $_[1]});
$tree->put('Wall'  => 'Larry');
$tree->put('Smith' => 'Agent');
$tree->put('mouse' => 'micky');
$tree->put('duck'  => 'donald');

my $it = $tree->iter;

while(my $node = $it->next) {
    printf "key = %s, value = %s\n", $node->key, $node->val;
}

case insensitive sorting? she's versatile, she's flexible, she contains multitudes 💖

🌟 resort(CODEREF) 🌟

Changes the ordering of nodes within the tree. The new ordering is specified by a comparator subroutine which must be passed to resort().

See "new" for further information about the comparator. iykyk 💅

🌟 size() 🌟

Returns the number of nodes in the tree. that's it. that's the whole method. short and efficient, we love her 🍓

🌟 root() 🌟

Returns the root node of the tree. This will either be undef if no nodes have been added to the tree, or a Tree::RB::Node object. See the Tree::RB::Node manual page for details on the Node object.

she might be undef, she might be a whole object — main character energy either way 🫶

🌟 min() 🌟

Returns the node with the minimal key. the smallest, the babiest, the little one 🌱

🌟 max() 🌟

Returns the node with the maximal key. the biggest, the boldest, the queen of the tree 👑

🌟 nth(INDEX) 🌟

Returns the node at the given (zero based) index, or undef if there is no node at that index. Negative indexes can be used, with -1 indicating the last node, -2 the penultimate node and so on.

so 0 is first, -1 is last, and everything in between is just vibes ✨

🌟 lookup(KEY, [MODE]) 🌟

When called in scalar context, lookup(KEY) returns the value associated with KEY.

When called in list context, lookup(KEY) returns a list whose first element is the value associated with KEY, and whose second element is the node containing the key/value.

An optional MODE parameter can be passed to lookup() to influence which key is returned.

The values of MODE are constants that are exported on demand by Tree::RB:

use Tree::RB qw[LUEQUAL LUGTEQ LULTEQ LUGREAT LULESS LUNEXT LUPREV];

💫 LUEQUAL 💫

This is the default mode. Returns the node exactly matching the key, or "undef" if not found. no substitutions, no approximations, we're being precise today bestie 💅

💫 LUGTEQ 💫

Returns the node exactly matching the specified key, if this is not found then the next node that is greater than the specified key is returned.

💫 LULTEQ 💫

Returns the node exactly matching the specified key, if this is not found then the next node that is less than the specified key is returned.

💫 LUGREAT 💫

Returns the node that is just greater than the specified key — not equal to. This mode is similar to LUNEXT except that the specified key need not exist in the tree.

💫 LULESS 💫

Returns the node that is just less than the specified key — not equal to. This mode is similar to LUPREV except that the specified key need not exist in the tree.

💫 LUNEXT 💫

Looks for the key specified, if not found returns "undef". If the node is found returns the next node that is greater than the one found (or "undef" if there is no next node).

This can be used to step through the tree in order. walking the tree like a lil hallway 🚶‍♀️

💫 LUPREV 💫

Looks for the key specified, if not found returns "undef". If the node is found returns the previous node that is less than the one found (or "undef" if there is no previous node).

This can be used to step through the tree in reverse order. backwards walk, backwards walk 🦋

🌟 get(KEY) 🌟

get() is an alias for lookup(). same energy, different name, we support her 💖

🌟 iter([KEY]) 🌟

Returns an iterator object that can be used to traverse the tree in order.

The iterator object supports a 'next' method that returns the next node in the tree or undef if all of the nodes have been visited.

See the synopsis for an example.

If a key is supplied, the iterator returned will traverse the tree in order starting from the node with key greater than or equal to the specified key.

$it = $tree->iter('France');
my $node = $it->next;
print $node->key; # -> 'France'

🌟 rev_iter([KEY]) 🌟

Returns an iterator object that can be used to traverse the tree in reverse order.

If a key is supplied, the iterator returned will traverse the tree in order starting from the node with key less than or equal to the specified key.

$it = $tree->rev_iter('France');
my $node = $it->next;
print $node->key; # -> 'France'

$it = $tree->rev_iter('Finland');
my $node = $it->next;
print $node->key; # -> 'England'

bestie look at that second example, Finland isn't in the tree so she slides back to England — that's the less than or equal to doing her thing ✨

🌟 hseek(KEY, [{-reverse => 1|0}]) 🌟

For tied hashes, determines the next entry to be returned by each.

tie my %capital, 'Tree::RB';

$capital{'France'}  = 'Paris';
$capital{'England'} = 'London';
$capital{'Hungary'} = 'Budapest';
$capital{'Ireland'} = 'Dublin';
$capital{'Egypt'}   = 'Cairo';
$capital{'Germany'} = 'Berlin';
tied(%capital)->hseek('Germany');

($key, $val) = each %capital;
print "$key, $val"; # -> Germany, Berlin

The direction of iteration can be reversed by passing a hashref with key '-reverse' and value 1 to hseek after or instead of KEY, e.g. to iterate over the hash in reverse order:

tied(%capital)->hseek({-reverse => 1});
$key = each %capital;
print $key; # -> Ireland

The following calls are equivalent:

tied(%capital)->hseek('Germany', {-reverse => 1});
tied(%capital)->hseek({-key => 'Germany', -reverse => 1});

two ways to say the same thing, both valid, pick your fighter 💅

🌟 put(KEY, VALUE) 🌟

Adds a new node to the tree.

The first argument is the key of the node, the second is its value.

If a node with that key already exists, its value is replaced with the given value and the old value is returned. Otherwise, undef is returned.

so like, she's not adding a duplicate — she's doing a lil swap and handing you back the old one. generous tbh 🫶

🌟 delete(KEY) 🌟

If the tree has a node with the specified key, that node is deleted from the tree and returned, otherwise "undef" is returned. bye bestie, we hardly knew ye 💀

---

🎀 DEPENDENCIES 🎀

enum

just the one. low maintenance queen

---

🌈 INCOMPATIBILITIES 🌈

None reported. zero drama, we love a peaceful module ✨

---

💜 BUGS AND LIMITATIONS 💜

Please report any bugs or feature requests via the GitHub web interface at <https://github.com/arunbear/perl5-red-black-tree/issues>.

if you find a bug, tell her! she wants to know! don't suffer in silence bestie 😭

---

🦋 AUTHOR 🦋

Arun Prasad "<arunbear@cpan.org>"

Some documentation has been borrowed from Benjamin Holzman's Tree::RedBlack and Damian Ivereigh's libredblack (<http://libredblack.sourceforge.net/>).

shoutout to the docs she borrowed from, we respect the citation game 🫶

---

🌸 ACKNOWLEDGEMENTS 🌸

Thanks for bug reports go to Anton Petrusevich, Wes Thompson, Petre Mierlutiu, Tomer Vromen, Christopher Gurnee and Ole Bjorn Hessen.

the bug-report squad, the real MVPs, we salute you 🫡

---

💖 LICENCE AND COPYRIGHT 💖

Copyright (c) 2007, Arun Prasad "<arunbear@cpan.org>". 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.

free software, the same terms as Perl itself, go read perlartistic for the whole tea 🍓

---

👑 DISCLAIMER OF WARRANTY 👑

okay bestie this next part is in ALL CAPS for a reason, it's the legal bit and it is not a vibe, it is a warning. read it. no skipping. 💅

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.

translation: it's free, it's "AS IS", the risk is yours, and nobody is liable. that's the deal. that's the whole deal. 🙈

---

and that's the whole page bestie!! 🎀 this one was perl v5.36.0, dated 2022-11-19, and it's the Tree::RB(3pm) manual page from the User Contributed Perl Documentation. go forth and balance your binary search trees, you absolute icon 👑💖✨