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 $Tree::Multi::numberOfKeysPerNode = 4;      # Number of keys per node - can be even

  my $t = Tree::Multi::new;                         # Construct tree
     $t = $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

Description

Multi-way tree in Pure Perl with an even or odd number of keys per node.

Version "20210602".

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      Tree

Example:

    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
  END
  

leaf($tree)

Confirm that the tree is a leaf.

     Parameter  Description
  1  $tree      Tree

Example:

    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
  END
  

find($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       Key

Example:

    local $Tree::Multi::numberOfKeysPerNode = 4;                                  # Number of keys per node - can be even
  
    my $t = Tree::Multi::new;                                                     # Construct tree
       $t = $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  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

  

leftMost($tree)

Return the left most node below the specified one

     Parameter  Description
  1  $tree      Tree

Example:

    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
  END
  

rightMost($tree)

Return the right most node below the specified one

     Parameter  Description
  1  $tree      Tree

Example:

    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
  END
  

height($tree)

Return the height of the tree

     Parameter  Description
  1  $tree      Tree

Example:

    local $Tree::Multi::numberOfKeysPerNode = 4;                                  # Number of keys per node - can be even
  
    my $t = Tree::Multi::new;                                                     # Construct tree
       $t = $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
  

delete($tree, $key)

Find a key in a tree, delete it, return the new tree

     Parameter  Description
  1  $tree      Tree
  2  $key       Key

Example:

    local $Tree::Multi::numberOfKeysPerNode = 4;                                  # Number of keys per node - can be even
  
    my $t = Tree::Multi::new;                                                     # Construct tree
       $t = $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
  

insert($tree, $key, $data)

Insert a key and data into a tree

     Parameter  Description
  1  $tree      Tree
  2  $key       Key
  3  $data      Data

Example:

    local $Tree::Multi::numberOfKeysPerNode = 4;                                  # Number of keys per node - can be even
  
    my $t = Tree::Multi::new;                                                     # Construct tree
  
       $t = $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
  

iterator($tree)

Make an iterator for a tree

     Parameter  Description
  1  $tree      Tree

Example:

    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      Iterator

Example:

    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 key

Example:

    local $Tree::Multi::numberOfKeysPerNode = 4;                                  # Number of keys per node - can be even
  
    my $t = Tree::Multi::new;                                                     # Construct tree
       $t = $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
  

Tree::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 $Tree::Multi::numberOfKeysPerNode = 4;                                  # Number of keys per node - can be even
  
  
    my $t = Tree::Multi::new;                                                     # Construct tree  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

       $t = $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
  

minimumNumberOfKeys()

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      Tree

halfFull($tree)

Confirm that a node is half full.

     Parameter  Description
  1  $tree      Tree

separateKeys($node)

Return ([lower], center, [upper]) keys.

     Parameter  Description
  1  $node      Node to split

separateData($node)

Return ([lower], center, [upper]) data

     Parameter  Description
  1  $node      Node to split

separateNode($node)

Return ([lower], [upper]) children

     Parameter  Description
  1  $node      Node to split

reUp($node, @children)

Reconnect the children to their new parent

     Parameter  Description
  1  $node      Node
  2  @children  Children

splitNode($node)

Split a full node in half assuming it has a non full parent

     Parameter  Description
  1  $node      Node to split

splitRootNode($node)

Split a full root

     Parameter  Description
  1  $node      Node to split

splitFullNode($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 split

splitLeafNode($node)

Split a full leaf node in assuming it has a non full parent

     Parameter  Description
  1  $node      Node to split

splitRootLeafNode($node)

Split a full root that is also a leaf

     Parameter  Description
  1  $node      Node to split

findAndSplit($tree, $key)

Find a key in a tree splitting full nodes along the path to the key

     Parameter  Description
  1  $tree      Tree
  2  $key       Key

indexInParent($tree)

Get the index of a node in its parent

     Parameter  Description
  1  $tree      Tree

fillFromLeftOrRight($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 right

mergeWithLeftOrRight($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 left

mergeRoot($tree, $child)

Merge the root node

     Parameter  Description
  1  $tree      Tree
  2  $child     The child to merge into

mergeOrFill($tree)

make a node larger than a half node

     Parameter  Description
  1  $tree      Tree

deleteElement($tree, $i)

Delete an element in a node

     Parameter  Description
  1  $tree      Tree
  2  $i         Index to delete at

T($tree, $expected)

Write a result to the log file

     Parameter  Description
  1  $tree      Tree
  2  $expected  Expected print

disordered($n, $N)

Disordered insertions

     Parameter  Description
  1  $n         Keys per node
  2  $N         Nodes

disorderedCheck($t, $n, $N)

Check disordered insertions

     Parameter  Description
  1  $t         Tree to check
  2  $n         Keys per node
  3  $N         Nodes

Index

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::Multi

Author

philiprbrenan@gmail.com

http://www.appaapps.com

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.