Name
Tree::Multi - Multi-way tree in Pure Perl with an even or odd number of keys per node.
Synopsis
Construct and query a multi-way tree in 100% Pure Perl with the choice of an odd or an even numbers of keys per node:
local $numberOfKeysPerNode = 4; # Number of keys per node - can be even
my $t = new; # Construct tree
$t = insert($t, $_, 2 * $_) for reverse 1..32; # Load tree with even numbers
is_deeply $t->print, <<END; # Print tree
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
is_deeply $t->height, 3; # Height
is_deeply $t->find (16), 32; # Find by key
$t->delete(16); # Delete a key
ok !defined $t->find (16); # Key no longer presentDescription
Multi-way tree in Pure Perl with an even or odd number of keys per node.
Version "20210601".
The following sections describe the methods in each functional area of this module. For an alphabetic listing of all methods by name see Index.
Multi-way Tree
Create and use a multi-way tree.
root($tree)
Return the root node of a tree.
Parameter Description
1 $tree TreeExample:
local $numberOfKeysPerNode = 3; my $N = 13; my $t = new;
for my $n(1..$N)
{$t = insert($t, $n, $n);
}
is_deeply $t->leftMost ->keys, [1, 2];
is_deeply $t->rightMost->keys, [13];
ok $t->leftMost ->leaf;
ok $t->rightMost->leaf;
ok $t->root; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
ok T($t, <<END);
6
3
1 2
4 5
9 12
7 8
10 11
13
ENDleaf($tree)
Confirm that the tree is a leaf.
Parameter Description
1 $tree TreeExample:
local $numberOfKeysPerNode = 3; my $N = 13; my $t = new;
for my $n(1..$N)
{$t = insert($t, $n, $n);
}
is_deeply $t->leftMost ->keys, [1, 2];
is_deeply $t->rightMost->keys, [13];
ok $t->leftMost ->leaf; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
ok $t->rightMost->leaf; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
ok $t->root;
ok T($t, <<END);
6
3
1 2
4 5
9 12
7 8
10 11
13
ENDfind($tree, $key)
Find a key in a tree returning its associated data or undef if the key does not exist
Parameter Description
1 $tree Tree
2 $key KeyExample:
local $numberOfKeysPerNode = 4; # Number of keys per node - can be even
my $t = new; # Construct tree
$t = insert($t, $_, 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
is_deeply $t->height, 3; # Height
is_deeply $t->find (16), 32; # Find by key # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
$t->delete(16); # Delete a key
ok !defined $t->find (16); # Key no longer present # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲leftMost($tree)
Return the left most node below the specified one
Parameter Description
1 $tree TreeExample:
local $numberOfKeysPerNode = 3; my $N = 13; my $t = new;
for my $n(1..$N)
{$t = insert($t, $n, $n);
}
is_deeply $t->leftMost ->keys, [1, 2]; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
is_deeply $t->rightMost->keys, [13];
ok $t->leftMost ->leaf; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
ok $t->rightMost->leaf;
ok $t->root;
ok T($t, <<END);
6
3
1 2
4 5
9 12
7 8
10 11
13
ENDrightMost($tree)
Return the right most node below the specified one
Parameter Description
1 $tree TreeExample:
local $numberOfKeysPerNode = 3; my $N = 13; my $t = new;
for my $n(1..$N)
{$t = insert($t, $n, $n);
}
is_deeply $t->leftMost ->keys, [1, 2];
is_deeply $t->rightMost->keys, [13]; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
ok $t->leftMost ->leaf;
ok $t->rightMost->leaf; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
ok $t->root;
ok T($t, <<END);
6
3
1 2
4 5
9 12
7 8
10 11
13
ENDheight($tree)
Return the height of the tree
Parameter Description
1 $tree TreeExample:
local $numberOfKeysPerNode = 4; # Number of keys per node - can be even
my $t = new; # Construct tree
$t = insert($t, $_, 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
is_deeply $t->height, 3; # Height # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
is_deeply $t->find (16), 32; # Find by key
$t->delete(16); # Delete a key
ok !defined $t->find (16); # Key no longer presentdelete($tree, $key)
Find a key in a tree, delete it, return the new tree
Parameter Description
1 $tree Tree
2 $key KeyExample:
local $numberOfKeysPerNode = 4; # Number of keys per node - can be even
my $t = new; # Construct tree
$t = insert($t, $_, 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
is_deeply $t->height, 3; # Height
is_deeply $t->find (16), 32; # Find by key
$t->delete(16); # Delete a key # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
ok !defined $t->find (16); # Key no longer presentinsert($tree, $key, $data)
Insert a key and data into a tree
Parameter Description
1 $tree Tree
2 $key Key
3 $data DataExample:
local $numberOfKeysPerNode = 4; # Number of keys per node - can be even
my $t = new; # Construct tree
$t = insert($t, $_, 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
is_deeply $t->height, 3; # Height
is_deeply $t->find (16), 32; # Find by key
$t->delete(16); # Delete a key
ok !defined $t->find (16); # Key no longer presentiterator($tree)
Make an iterator for a tree
Parameter Description
1 $tree TreeExample:
local $numberOfKeysPerNode = 3; my $N = 256; my $e = 0; my $t = new;
for my $n(0..$N)
{$t = insert($t, $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;Tree::Multi::Iterator::next($iter)
Find the next key
Parameter Description
1 $iter IteratorExample:
local $numberOfKeysPerNode = 3; my $N = 256; my $e = 0; my $t = new;
for my $n(0..$N)
{$t = insert($t, $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;print($tree, $i)
Print the keys in a tree optionally marking the active key
Parameter Description
1 $tree Tree
2 $i Optional index of active keyExample:
local $numberOfKeysPerNode = 4; # Number of keys per node - can be even
my $t = new; # Construct tree
$t = insert($t, $_, 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
is_deeply $t->height, 3; # Height
is_deeply $t->find (16), 32; # Find by key
$t->delete(16); # Delete a key
ok !defined $t->find (16); # Key no longer presentTree::Multi Definition
Iterator
Output fields
count
Counter
data
Data at this position
key
Key at this position
keys
Array of key items for this node
more
Iteration not yet finished
node
Current node within tree
number
Number of the node for debugging purposes
pos
Current position within node
tree
Tree we are iterating over
up
Parent node
Private Methods
new()
Create a new multi-way tree node.
Example:
local $numberOfKeysPerNode = 4; # Number of keys per node - can be even
my $t = new; # Construct tree # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
$t = insert($t, $_, 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
is_deeply $t->height, 3; # Height
is_deeply $t->find (16), 32; # Find by key
$t->delete(16); # Delete a key
ok !defined $t->find (16); # Key no longer presentminimumNumberOfKeys()
Minimum number of keys per node.
maximumNumberOfKeys()
Maximum number of keys per node.
maximumNumberOfNodes()
Maximum number of children per parent.
full($tree)
Confirm that a node is full.
Parameter Description
1 $tree TreehalfFull($tree)
Confirm that a node is half full.
Parameter Description
1 $tree TreeseparateKeys($node)
Return ([lower], center, [upper]) keys.
Parameter Description
1 $node Node to splitseparateData($node)
Return ([lower], center, [upper]) data
Parameter Description
1 $node Node to splitseparateNode($node)
Return ([lower], [upper]) children
Parameter Description
1 $node Node to splitreUp($node, @children)
Reconnect the children to their new parent
Parameter Description
1 $node Node
2 @children ChildrensplitNode($node)
Split a full node in half assuming it has a non full parent
Parameter Description
1 $node Node to splitsplitRootNode($node)
Split a full root
Parameter Description
1 $node Node to splitsplitFullNode($node)
Split a full node and return the new parent or return the existing node if it does not need to be split
Parameter Description
1 $node Node to splitsplitLeafNode($node)
Split a full leaf node in assuming it has a non full parent
Parameter Description
1 $node Node to splitsplitRootLeafNode($node)
Split a full root that is also a leaf
Parameter Description
1 $node Node to splitfindAndSplit($tree, $key)
Find a key in a tree splitting full nodes along the path to the key
Parameter Description
1 $tree Tree
2 $key KeyindexInParent($tree)
Get the index of a node in its parent
Parameter Description
1 $tree TreefillFromLeftOrRight($n, $dir)
Fill a node from the specified sibling
Parameter Description
1 $n Node to fill
2 $dir Node to fill from 0 for left or 1 for rightmergeWithLeftOrRight($n, $dir)
Merge two adjacent nodes
Parameter Description
1 $n Node to merge into
2 $dir Node to merge is on right if 1 else leftmergeRoot($tree, $child)
Merge the root node
Parameter Description
1 $tree Tree
2 $child The child to merge intomergeOrFill($tree)
make a node larger than a half node
Parameter Description
1 $tree TreedeleteElement($tree, $i)
Delete an element in a node
Parameter Description
1 $tree Tree
2 $i Index to delete atT($tree, $expected)
Write a result to the log file
Parameter Description
1 $tree Tree
2 $expected Expected printdisordered($n, $N)
Disordered insertions
Parameter Description
1 $n Keys per node
2 $N NodesdisorderedCheck($t, $n, $N)
Check disordered insertions
Parameter Description
1 $t Tree to check
2 $n Keys per node
3 $N NodesIndex
1 delete - Find a key in a tree, delete it, return the new tree
2 deleteElement - Delete an element in a node
3 disordered - Disordered insertions
4 disorderedCheck - Check disordered insertions
5 fillFromLeftOrRight - Fill a node from the specified sibling
6 find - Find a key in a tree returning its associated data or undef if the key does not exist
7 findAndSplit - Find a key in a tree splitting full nodes along the path to the key
8 full - Confirm that a node is full.
9 halfFull - Confirm that a node is half full.
10 height - Return the height of the tree
11 indexInParent - Get the index of a node in its parent
12 insert - Insert a key and data into a tree
13 iterator - Make an iterator for a tree
14 leaf - Confirm that the tree is a leaf.
15 leftMost - Return the left most node below the specified one
16 maximumNumberOfKeys - Maximum number of keys per node.
17 maximumNumberOfNodes - Maximum number of children per parent.
18 mergeOrFill - make a node larger than a half node
19 mergeRoot - Merge the root node
20 mergeWithLeftOrRight - Merge two adjacent nodes
21 minimumNumberOfKeys - Minimum number of keys per node.
22 new - Create a new multi-way tree node.
23 print - Print the keys in a tree optionally marking the active key
24 reUp - Reconnect the children to their new parent
25 rightMost - Return the right most node below the specified one
26 root - Return the root node of a tree.
27 separateData - Return ([lower], center, [upper]) data
28 separateKeys - Return ([lower], center, [upper]) keys.
29 separateNode - Return ([lower], [upper]) children
30 splitFullNode - Split a full node and return the new parent or return the existing node if it does not need to be split
31 splitLeafNode - Split a full leaf node in assuming it has a non full parent
32 splitNode - Split a full node in half assuming it has a non full parent
33 splitRootLeafNode - Split a full root that is also a leaf
34 splitRootNode - Split a full root
35 T - Write a result to the log file
36 Tree::Multi::Iterator::next - Find the next key
Installation
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::MultiAuthor
Copyright
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.