Tree::Multi - Multi-way tree in Pure Perl with an even or odd number of keys per node.
Construct and query a multi-way tree in 100% Pure Perl with a choice of an odd or an even numbers of keys per node:
local $Tree::Multi::numberOfKeysPerNode = 4; # Number of keys per node - can be even my $t = Tree::Multi::new; # Construct tree $t->insert($_, 2 * $_) for reverse 1..32; # Load tree in reverse is_deeply $t->print, <<END; 15 21 27 3 6 9 12 1 2 4 5 7 8 10 11 13 14 18 16 17 19 20 24 22 23 25 26 30 28 29 31 32 END ok $t->height == 3; # Height ok $t->find (16) == 32; # Find by key $t->delete(16); # Delete a key ok !$t->find (16); # Key no longer present ok $t->find (17) == 34; # Find by key my @k; for(my $i = $t->iterator; $i->more; $i->next) # Iterator {push @k, $i->key unless $i->key == 17; } $t->delete($_) for @k; # Delete ok $t->find(17) == 34 && $t->size == 1; # Size
Multi-way tree in Pure Perl with an even or odd number of keys per node.
Version "20210629".
The following sections describe the methods in each functional area of this module. For an alphabetic listing of all methods by name see Index.
Create and use a multi-way tree.
Return the root node of a tree.
Parameter Description 1 $tree Tree
Example:
local $numberOfKeysPerNode = 3; my $N = 13; my $t = new; for my $n(1..$N) {$t->insert($n, $n); } ok T($t, <<END); 4 8 2 1 3 6 5 7 10 12 9 11 13 END is_deeply $t->leftMost ->keys, [1]; is_deeply $t->rightMost->keys, [13]; ok $t->leftMost ->leaf; ok $t->rightMost->leaf; ok $t->root == $t; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
Confirm that the tree is a leaf.
local $numberOfKeysPerNode = 3; my $N = 13; my $t = new; for my $n(1..$N) {$t->insert($n, $n); } ok T($t, <<END); 4 8 2 1 3 6 5 7 10 12 9 11 13 END is_deeply $t->leftMost ->keys, [1]; is_deeply $t->rightMost->keys, [13]; ok $t->leftMost ->leaf; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 ok $t->rightMost->leaf; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 ok $t->root == $t;
Find a key in a tree returning its associated data or undef if the key does not exist.
Parameter Description 1 $root Root of tree 2 $key Key
local $Tree::Multi::numberOfKeysPerNode = 4; # Number of keys per node - can be even my $t = Tree::Multi::new; # Construct tree $t->insert($_, 2 * $_) for reverse 1..32; # Load tree in reverse T($t, <<END); 17 25 9 13 3 5 7 1 2 4 6 8 11 10 12 15 14 16 21 19 18 20 23 22 24 29 27 26 28 31 30 32 END ok $t->size == 32; # Size ok $t->height == 4; # Height ok $t->delete(16) == 2 * 16; # Delete a key ok !$t->find (16); # Key no longer present # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 ok $t->find (17) == 34; # Find by key # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 my @k; for(my $i = $t->iterator; $i->more; $i->next) # Iterator {push @k, $i->key unless $i->key == 17; } ok $t->delete($_) == 2 * $_ for @k; # Delete ok $t->find(17) == 34 && $t->size == 1; # Size # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 local $Tree::Multi::numberOfKeysPerNode = 3; # Number of keys per node - can be even my $t = Tree::Multi::new; # Construct tree $t->insert($_, $_) for 1..8; T($t, <<END, 1); 4 2 6 1 3 5 7 8 END local $Tree::Multi::numberOfKeysPerNode = 14; # Number of keys per node - can be even my $t = Tree::Multi::new; # Construct tree $t->insert($_, $_) for 1..15; T($t, <<END, 1); 8 1 2 3 4 5 6 7 9 10 11 12 13 14 15 END
Return the left most node below the specified one.
local $numberOfKeysPerNode = 3; my $N = 13; my $t = new; for my $n(1..$N) {$t->insert($n, $n); } ok T($t, <<END); 4 8 2 1 3 6 5 7 10 12 9 11 13 END is_deeply $t->leftMost ->keys, [1]; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 is_deeply $t->rightMost->keys, [13]; ok $t->leftMost ->leaf; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 ok $t->rightMost->leaf; ok $t->root == $t;
Return the right most node below the specified one.
local $numberOfKeysPerNode = 3; my $N = 13; my $t = new; for my $n(1..$N) {$t->insert($n, $n); } ok T($t, <<END); 4 8 2 1 3 6 5 7 10 12 9 11 13 END is_deeply $t->leftMost ->keys, [1]; is_deeply $t->rightMost->keys, [13]; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 ok $t->leftMost ->leaf; ok $t->rightMost->leaf; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 ok $t->root == $t;
Return the height of the tree.
local $Tree::Multi::numberOfKeysPerNode = 3; my $t = new; ok $t->height == 0; ok $t->leftMost->depth == 0; ok $t->size == 0; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 $t->insert(1, 1); ok $t->height == 1; ok $t->leftMost->depth == 1; ok $t->size == 1; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 $t->insert(2, 2); ok $t->height == 1; ok $t->leftMost->depth == 1; ok $t->size == 2; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 $t->insert(3, 3); ok $t->height == 1; ok $t->leftMost->depth == 1; ok $t->size == 3; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 $t->insert(4, 4); ok $t->height == 2; ok $t->leftMost->depth == 2; ok $t->size == 4; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 $t->insert(5, 5); ok $t->height == 2; ok $t->leftMost->depth == 2; ok $t->size == 5; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 $t->insert(6, 6); ok $t->height == 2; ok $t->leftMost->depth == 2; ok $t->size == 6; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 $t->insert(7, 7); ok $t->height == 2; ok $t->leftMost->depth == 2; ok $t->size == 7; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 $t->insert(8, 8); ok $t->height == 3; ok $t->leftMost->depth == 3; ok $t->size == 8; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 T($t, <<END, 1); 4 2 6 1 3 5 7 8 END
Return the depth of a node within a tree.
Find a key in a tree, delete it and return any associated data.
Parameter Description 1 $root Tree root 2 $key Key
local $Tree::Multi::numberOfKeysPerNode = 4; # Number of keys per node - can be even my $t = Tree::Multi::new; # Construct tree $t->insert($_, 2 * $_) for reverse 1..32; # Load tree in reverse T($t, <<END); 17 25 9 13 3 5 7 1 2 4 6 8 11 10 12 15 14 16 21 19 18 20 23 22 24 29 27 26 28 31 30 32 END ok $t->size == 32; # Size ok $t->height == 4; # Height ok $t->delete(16) == 2 * 16; # Delete a key # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 ok !$t->find (16); # Key no longer present ok $t->find (17) == 34; # Find by key my @k; for(my $i = $t->iterator; $i->more; $i->next) # Iterator {push @k, $i->key unless $i->key == 17; } ok $t->delete($_) == 2 * $_ for @k; # Delete # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 ok $t->find(17) == 34 && $t->size == 1; # Size local $Tree::Multi::numberOfKeysPerNode = 3; # Number of keys per node - can be even my $t = Tree::Multi::new; # Construct tree $t->insert($_, $_) for 1..8; T($t, <<END, 1); 4 2 6 1 3 5 7 8 END local $Tree::Multi::numberOfKeysPerNode = 14; # Number of keys per node - can be even my $t = Tree::Multi::new; # Construct tree $t->insert($_, $_) for 1..15; T($t, <<END, 1); 8 1 2 3 4 5 6 7 9 10 11 12 13 14 15 END
Insert the specified key and data into a tree.
Parameter Description 1 $tree Tree 2 $key Key 3 $data Data
local $Tree::Multi::numberOfKeysPerNode = 4; # Number of keys per node - can be even my $t = Tree::Multi::new; # Construct tree $t->insert($_, 2 * $_) for reverse 1..32; # Load tree in reverse # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 T($t, <<END); 17 25 9 13 3 5 7 1 2 4 6 8 11 10 12 15 14 16 21 19 18 20 23 22 24 29 27 26 28 31 30 32 END ok $t->size == 32; # Size ok $t->height == 4; # Height ok $t->delete(16) == 2 * 16; # Delete a key ok !$t->find (16); # Key no longer present ok $t->find (17) == 34; # Find by key my @k; for(my $i = $t->iterator; $i->more; $i->next) # Iterator {push @k, $i->key unless $i->key == 17; } ok $t->delete($_) == 2 * $_ for @k; # Delete ok $t->find(17) == 34 && $t->size == 1; # Size local $Tree::Multi::numberOfKeysPerNode = 3; # Number of keys per node - can be even my $t = Tree::Multi::new; # Construct tree $t->insert($_, $_) for 1..8; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 T($t, <<END, 1); 4 2 6 1 3 5 7 8 END local $Tree::Multi::numberOfKeysPerNode = 14; # Number of keys per node - can be even my $t = Tree::Multi::new; # Construct tree $t->insert($_, $_) for 1..15; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 T($t, <<END, 1); 8 1 2 3 4 5 6 7 9 10 11 12 13 14 15 END
Make an iterator for a tree.
local $numberOfKeysPerNode = 3; my $N = 256; my $e = 0; my $t = new; for my $n(0..$N) {$t->insert($n, $n); my @n; for(my $i = $t->iterator; $i->more; $i->next) {push @n, $i->key} # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 ++$e unless dump(\@n) eq dump [0..$n]; } is_deeply $e, 0; local $Tree::Multi::numberOfKeysPerNode = 4; # Number of keys per node - can be even my $t = Tree::Multi::new; # Construct tree $t->insert($_, 2 * $_) for reverse 1..32; # Load tree in reverse T($t, <<END); 17 25 9 13 3 5 7 1 2 4 6 8 11 10 12 15 14 16 21 19 18 20 23 22 24 29 27 26 28 31 30 32 END ok $t->size == 32; # Size ok $t->height == 4; # Height ok $t->delete(16) == 2 * 16; # Delete a key ok !$t->find (16); # Key no longer present ok $t->find (17) == 34; # Find by key my @k; for(my $i = $t->iterator; $i->more; $i->next) # Iterator # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 {push @k, $i->key unless $i->key == 17; } ok $t->delete($_) == 2 * $_ for @k; # Delete ok $t->find(17) == 34 && $t->size == 1; # Size local $Tree::Multi::numberOfKeysPerNode = 3; # Number of keys per node - can be even my $t = Tree::Multi::new; # Construct tree $t->insert($_, $_) for 1..8; T($t, <<END, 1); 4 2 6 1 3 5 7 8 END local $Tree::Multi::numberOfKeysPerNode = 14; # Number of keys per node - can be even my $t = Tree::Multi::new; # Construct tree $t->insert($_, $_) for 1..15; T($t, <<END, 1); 8 1 2 3 4 5 6 7 9 10 11 12 13 14 15 END
Find the next key.
Parameter Description 1 $iter Iterator
local $numberOfKeysPerNode = 3; my $N = 256; my $e = 0; my $t = new; for my $n(0..$N) {$t->insert($n, $n); my @n; for(my $i = $t->iterator; $i->more; $i->next) {push @n, $i->key} ++$e unless dump(\@n) eq dump [0..$n]; } is_deeply $e, 0;
Create a reverse iterator for a tree.
local $numberOfKeysPerNode = 3; my $N = 64; my $e = 0; for my $n(0..$N) {my $t = new; for my $i(0..$n) {$t->insert($i, $i); } my @n; for(my $i = $t->reverseIterator; $i->less; $i->prev) # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 {push @n, $i->key; } ++$e unless dump(\@n) eq dump [reverse 0..$n]; } is_deeply $e, 0;
Find the previous key.
local $numberOfKeysPerNode = 3; my $N = 64; my $e = 0; for my $n(0..$N) {my $t = new; for my $i(0..$n) {$t->insert($i, $i); } my @n; for(my $i = $t->reverseIterator; $i->less; $i->prev) {push @n, $i->key; } ++$e unless dump(\@n) eq dump [reverse 0..$n]; } is_deeply $e, 0;
Print the keys in a tree from left right to make it easier to visualize the structure of the tree.
Parameter Description 1 $tree Tree 2 @title Title
local $Tree::Multi::numberOfKeysPerNode = 3; my $t = new; ok $t->height == 0; ok $t->leftMost->depth == 0; ok $t->size == 0; $t->insert(1, 1); ok $t->height == 1; ok $t->leftMost->depth == 1; ok $t->size == 1; $t->insert(2, 2); ok $t->height == 1; ok $t->leftMost->depth == 1; ok $t->size == 2; $t->insert(3, 3); ok $t->height == 1; ok $t->leftMost->depth == 1; ok $t->size == 3; $t->insert(4, 4); ok $t->height == 2; ok $t->leftMost->depth == 2; ok $t->size == 4; $t->insert(5, 5); ok $t->height == 2; ok $t->leftMost->depth == 2; ok $t->size == 5; $t->insert(6, 6); ok $t->height == 2; ok $t->leftMost->depth == 2; ok $t->size == 6; $t->insert(7, 7); ok $t->height == 2; ok $t->leftMost->depth == 2; ok $t->size == 7; $t->insert(8, 8); ok $t->height == 3; ok $t->leftMost->depth == 3; ok $t->size == 8; T($t, <<END, 1); 4 2 6 1 3 5 7 8 END
Print the keys in a tree optionally marking the active key.
Parameter Description 1 $tree Tree 2 $i Optional index of active key
local $Tree::Multi::numberOfKeysPerNode = 4; # Number of keys per node - can be even my $t = Tree::Multi::new; # Construct tree $t->insert($_, 2 * $_) for reverse 1..32; # Load tree in reverse T($t, <<END); 17 25 9 13 3 5 7 1 2 4 6 8 11 10 12 15 14 16 21 19 18 20 23 22 24 29 27 26 28 31 30 32 END ok $t->size == 32; # Size ok $t->height == 4; # Height ok $t->delete(16) == 2 * 16; # Delete a key ok !$t->find (16); # Key no longer present ok $t->find (17) == 34; # Find by key my @k; for(my $i = $t->iterator; $i->more; $i->next) # Iterator {push @k, $i->key unless $i->key == 17; } ok $t->delete($_) == 2 * $_ for @k; # Delete ok $t->find(17) == 34 && $t->size == 1; # Size local $Tree::Multi::numberOfKeysPerNode = 3; # Number of keys per node - can be even my $t = Tree::Multi::new; # Construct tree $t->insert($_, $_) for 1..8; T($t, <<END, 1); 4 2 6 1 3 5 7 8 END local $Tree::Multi::numberOfKeysPerNode = 14; # Number of keys per node - can be even my $t = Tree::Multi::new; # Construct tree $t->insert($_, $_) for 1..15; T($t, <<END, 1); 8 1 2 3 4 5 6 7 9 10 11 12 13 14 15 END
Count the number of keys in a tree.
Iterator
Counter
Data at this position
Key at this position
Array of key items for this node
Iteration not yet finished
Current node within tree
Current position within node
Tree we are iterating over
Parent node
Create a new multi-way tree node.
local $Tree::Multi::numberOfKeysPerNode = 4; # Number of keys per node - can be even my $t = Tree::Multi::new; # Construct tree # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 $t->insert($_, 2 * $_) for reverse 1..32; # Load tree in reverse T($t, <<END); 17 25 9 13 3 5 7 1 2 4 6 8 11 10 12 15 14 16 21 19 18 20 23 22 24 29 27 26 28 31 30 32 END ok $t->size == 32; # Size ok $t->height == 4; # Height ok $t->delete(16) == 2 * 16; # Delete a key ok !$t->find (16); # Key no longer present ok $t->find (17) == 34; # Find by key my @k; for(my $i = $t->iterator; $i->more; $i->next) # Iterator {push @k, $i->key unless $i->key == 17; } ok $t->delete($_) == 2 * $_ for @k; # Delete ok $t->find(17) == 34 && $t->size == 1; # Size local $Tree::Multi::numberOfKeysPerNode = 3; # Number of keys per node - can be even my $t = Tree::Multi::new; # Construct tree # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 $t->insert($_, $_) for 1..8; T($t, <<END, 1); 4 2 6 1 3 5 7 8 END local $Tree::Multi::numberOfKeysPerNode = 14; # Number of keys per node - can be even my $t = Tree::Multi::new; # Construct tree # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 $t->insert($_, $_) for 1..15; T($t, <<END, 1); 8 1 2 3 4 5 6 7 9 10 11 12 13 14 15 END
Minimum number of keys per node.
Maximum number of keys per node.
Maximum number of children per parent.
Confirm that a node is full.
Confirm that a node is half full.
Reconnect the children to their new parent.
Parameter Description 1 $tree Tree 2 $children Children
Split a node if it is full.
Parameter Description 1 $isRoot Known to be the root if true 2 $isLeaf Known to be a leaf if true 3 $node Node to split
Find a key in a tree splitting full nodes along the path to the key.
Get the index of a node in its parent.
Fill a node from the specified sibling.
Parameter Description 1 $node Node to fill 2 $dir Node to fill from 0 for left or 1 for right
Merge two adjacent nodes.
Parameter Description 1 $n Node to merge into 2 $dir Node to merge is on right if 1 else left
Merge the current node with its sibling.
Make a node larger than a half node.
Delete a key in a leaf.
Parameter Description 1 $tree Tree 2 $i Index to delete at
Delete a key.
Print a tree to the log file and check it against the expected result
Parameter Description 1 $tree Tree 2 $expected Expected print 3 $flat Optionally print in flat mode if true
Print a tree flatly to the log file and check its result
Parameter Description 1 $tree Tree 2 $expected Expected print
Disordered but stable insertions
Parameter Description 1 $n Keys per node 2 $N Nodes
Check disordered insertions
Parameter Description 1 $t Tree to check 2 $n Keys per node 3 $N Nodes
Random insertions
Parameter Description 1 $n Keys per node 2 $N Log 10 nodes 3 $T Log 10 number of tests
1 delete - Find a key in a tree, delete it and return any associated data.
2 deleteKey - Delete a key.
3 deleteLeafKey - Delete a key in a leaf.
4 depth - Return the depth of a node within a tree.
5 disordered - Disordered but stable insertions
6 disorderedCheck - Check disordered insertions
7 F - Print a tree flatly to the log file and check its result
8 fillFromLeftOrRight - Fill a node from the specified sibling.
9 find - Find a key in a tree returning its associated data or undef if the key does not exist.
10 findAndSplit - Find a key in a tree splitting full nodes along the path to the key.
11 flat - Print the keys in a tree from left right to make it easier to visualize the structure of the tree.
12 full - Confirm that a node is full.
13 halfFull - Confirm that a node is half full.
14 height - Return the height of the tree.
15 indexInParent - Get the index of a node in its parent.
16 insert - Insert the specified key and data into a tree.
17 iterator - Make an iterator for a tree.
18 leaf - Confirm that the tree is a leaf.
19 leftMost - Return the left most node below the specified one.
20 maximumNumberOfKeys - Maximum number of keys per node.
21 maximumNumberOfNodes - Maximum number of children per parent.
22 merge - Merge the current node with its sibling.
23 mergeOrFill - Make a node larger than a half node.
24 mergeWithLeftOrRight - Merge two adjacent nodes.
25 minimumNumberOfKeys - Minimum number of keys per node.
26 new - Create a new multi-way tree node.
27 print - Print the keys in a tree optionally marking the active key.
28 randomCheck - Random insertions
29 reUp - Reconnect the children to their new parent.
30 reverseIterator - Create a reverse iterator for a tree.
31 rightMost - Return the right most node below the specified one.
32 root - Return the root node of a tree.
33 size - Count the number of keys in a tree.
34 splitFullNode - Split a node if it is full.
35 T - Print a tree to the log file and check it against the expected result
36 Tree::Multi::Iterator::next - Find the next key.
37 Tree::Multi::ReverseIterator::prev - Find the previous key.
This module is written in 100% Pure Perl and, thus, it is easy to read, comprehend, use, modify and install via cpan:
sudo cpan install Tree::Multi
philiprbrenan@gmail.com
http://www.appaapps.com
Copyright (c) 2016-2021 Philip R Brenan.
This module is free software. It may be used, redistributed and/or modified under the same terms as Perl itself.
To install Tree::Multi, copy and paste the appropriate command in to your terminal.
cpanm
cpanm Tree::Multi
CPAN shell
perl -MCPAN -e shell install Tree::Multi
For more information on module installation, please visit the detailed CPAN module installation guide.