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

Description

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.

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($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;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

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($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($root, $key)

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

Example:

  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

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($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;

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($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;

height($tree)

Return the height of the tree.

   Parameter  Description
1  $tree      Tree

Example:

  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

depth($tree)

Return the depth of a node within a tree.

   Parameter  Description
1  $tree      Tree

Example:

  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

delete($root, $key)

Find a key in a tree, delete it and return any associated data.

   Parameter  Description
1  $root      Tree root
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->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($tree, $key, $data)

Insert the specified 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->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

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

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($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;

reverseIterator($tree)

Create a reverse iterator for a tree.

   Parameter  Description
1  $tree      Tree

Example:

  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;

Tree::Multi::ReverseIterator::prev($iter)

Find the previous key.

   Parameter  Description
1  $iter      Iterator

Example:

  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;

flat($tree, @title)

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

Example:

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

size($tree)

Count the number of keys in a tree.

   Parameter  Description
1  $tree      Tree

Example:

  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

Hash Definitions

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

less

Iteration not yet finished

node

Current node within tree

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

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

reUp($tree, $children)

Reconnect the children to their new parent.

   Parameter  Description
1  $tree      Tree
2  $children  Children

splitFullNode($isRoot, $isLeaf, $node)

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

findAndSplit($root, $key)

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

   Parameter  Description
1  $root      Root of tree
2  $key       Key

indexInParent($tree)

Get the index of a node in its parent.

   Parameter  Description
1  $tree      Tree

fillFromLeftOrRight($node, $dir)

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

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

merge($tree)

Merge the current node with its sibling.

   Parameter  Description
1  $tree      Tree

mergeOrFill($tree)

Make a node larger than a half node.

   Parameter  Description
1  $tree      Tree

deleteLeafKey($tree, $i)

Delete a key in a leaf.

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

deleteKey($tree, $i)

Delete a key.

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

T($tree, $expected, $flat)

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

F($tree, $expected)

Print a tree flatly to the log file and check its result

   Parameter  Description
1  $tree      Tree
2  $expected  Expected print

disordered($n, $N)

Disordered but stable 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

randomCheck($n, $N, $T)

Random insertions

   Parameter  Description
1  $n         Keys per node
2  $N         Log 10 nodes
3  $T         Log 10 number of tests

Index

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.

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

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.

	Global
`s`	Focus search bar
`?`	Bring up this help dialog

	GitHub
`g` `p`	Go to pull requests
`g` `i`	go to github issues (only if github is preferred repository)

	POD
`g` `a`	Go to author
`g` `c`	Go to changes
`g` `i`	Go to issues
`g` `d`	Go to dist
`g` `r`	Go to repository/SCM
`g` `s`	Go to source
`g` `b`	Go to file browse

	Search terms
module: (e.g. module:Plugin)
distribution: (e.g. distribution:Dancer auth)
author: (e.g. author:SONGMU Redis)
version: (e.g. version:1.00)

Name

Synopsis

Description

Multi-way Tree

root($tree)

leaf($tree)

find($root, $key)

leftMost($tree)

rightMost($tree)

height($tree)

depth($tree)

delete($root, $key)

insert($tree, $key, $data)

iterator($tree)

Tree::Multi::Iterator::next($iter)

reverseIterator($tree)

Tree::Multi::ReverseIterator::prev($iter)

flat($tree, @title)

print($tree, $i)

size($tree)

Hash Definitions

Tree::Multi Definition

Output fields

count

data

key

keys

less

more

node

pos

tree

up

Private Methods

new()

minimumNumberOfKeys()

maximumNumberOfKeys()

maximumNumberOfNodes()

full($tree)

halfFull($tree)

reUp($tree, $children)

splitFullNode($isRoot, $isLeaf, $node)

findAndSplit($root, $key)

indexInParent($tree)

fillFromLeftOrRight($node, $dir)

mergeWithLeftOrRight($n, $dir)

merge($tree)

mergeOrFill($tree)

deleteLeafKey($tree, $i)

deleteKey($tree, $i)

T($tree, $expected, $flat)

F($tree, $expected)

disordered($n, $N)

disorderedCheck($t, $n, $N)

randomCheck($n, $N, $T)

Index

Installation

Author

Copyright

Module Install Instructions