• Name
• Synopsis
• Description
• Multi-way Tree
  • root($tree)
  • leaf($tree)
  • find($tree, $key)
  • leftMost($tree)
  • rightMost($tree)
  • height($tree)
  • delete($tree, $key)
  • insert($tree, $key, $data)
  • iterator($tree)
  • Tree::Multi::Iterator::next($iter)
  • printKeys($tree, $i)
  • Tree::Multi Definition
    • Output fields
      • count
      • data
      • key
      • keys
      • more
      • node
      • number
      • pos
      • tree
      • up
• Attributes
  • Replaceable Attribute List
  • maximumNumberOfKeys
  • maximumNumberOfNodes
  • minimumNumberOfKeys
• Private Methods
  • new()
  • full($tree)
  • halfFull($tree)
  • separateKeys($node)
  • separateData($node)
  • separateNode($node)
  • reUp($node, @children)
  • splitNode($node)
  • splitRootNode($node)
  • splitFullNode($node)
  • splitLeafNode($node)
  • splitRootLeafNode($node)
  • splitFullLeafNode($node)
  • findAndSplit($tree, $key)
  • indexInParent($tree)
  • fillFromLeftOrRight($n, $dir)
  • mergeWithLeftOrRight($n, $dir)
  • mergeRoot($tree, $child)
  • mergeOrFill($tree)
  • deleteElement($tree, $i)
  • T($tree, $expected)
• Index
• Installation
• Author
• Copyright

Name

Tree::Multi - Multi-way tree in Pure Perl

Synopsis

Description

Multi-way tree in Pure Perl

Version "20210528".

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 $keysPerNode = 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 $keysPerNode = 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:

    if (1)
     {my $n = 0;
      for my $i(1..$N)

       {my $ii = $t->find($i);  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲


         ++$n if $t->find($i) eq 2 * $i;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

       }
      ok $n == $N;
     }

    local $keysPerNode = 15;

    my $t = new; my $N = 256;

    $t = insert($t, $_, 2 * $_) for reverse map{scalar reverse} 1..$N;

    is_deeply $t->printKeys, <<END;
   371
     09 18 032 48 061 75 86 99 132 202 252 322
       001 002 03 04 05 06 07 08
       011 012 13 14 15 16 17
       19 021 022 23 24 25 26 27 28 29 031
       33 34 35 36 37 38 39 041 042 43 44 45 46 47
       49 051 052 53 54 55 56 57 58 59
       62 63 64 65 66 67 68 69 071 72 73 74
       76 77 78 79 081 82 83 84 85
       87 88 89 091 92 93 94 95 96 97 98
       101 102 111 112 121 122 131
       141 142 151 152 161 171 181 191 201
       211 212 221 222 231 232 241 242 251
       261 271 281 291 301 302 311 312 321
       331 332 341 342 351 352 361
     452 542 622 681 732 822 891
       381 391 401 402 411 412 421 422 431 432 441 442 451
       461 471 481 491 501 502 511 512 521 522 531 532 541
       551 552 561 571 581 591 601 602 611 612 621
       631 632 641 642 651 652 661 671
       691 701 702 711 712 721 722 731
       741 742 751 761 771 781 791 801 802 811 812 821
       831 832 841 842 851 861 871 881
       901 902 911 912 921 922 931 932 941 942 951 961 971 981 991
  END

    if (1)
     {my $n = 0;
      for my $i(map {scalar reverse} 1..$N)

       {my $ii = $t->find($i);  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲


         ++$n if $t->find($i) eq 2 * $i;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

       }
      ok $n == $N;
     }

leftMost($tree)

Return the left most node below the specified one

     Parameter  Description
  1  $tree      Tree

Example:

    local $keysPerNode = 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 $keysPerNode = 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 $keysPerNode = 7;

    my $t = new; my $N = 256;

    my %t = map {$_=>2*$_} my @t = map{$_ = scalar reverse $_; s/\A0+//r} 1..$N;

    $t = insert($t, $_, $t{$_}) for @t;

    ok T($t, <<END);
   201
     32 61 81
       5 11 16 22 27
         1 2 3 4
         6 7 8 9
         12 13 14 15
         17 18 19 21
         23 24 25 26
         28 29 31
       37 43 52
         33 34 35 36
         38 39 41 42
         44 45 46 47 48 49 51
         53 54 55 56 57 58 59
       66 71 76
         62 63 64 65
         67 68 69
         72 73 74 75
         77 78 79
       86 91 96 111 132 161
         82 83 84 85
         87 88 89
         92 93 94 95
         97 98 99 101 102
         112 121 122 131
         141 142 151 152
         171 181 191
     401 601 801
       222 251 301 322 351
         202 211 212 221
         231 232 241 242
         252 261 271 281 291
         302 311 312 321
         331 332 341 342
         352 361 371 381 391
       422 451 501 522 551
         402 411 412 421
         431 432 441 442
         452 461 471 481 491
         502 511 512 521
         531 532 541 542
         552 561 571 581 591
       622 651 701 722 751
         602 611 612 621
         631 632 641 642
         652 661 671 681 691
         702 711 712 721
         731 732 741 742
         761 771 781 791
       822 851 901 922 951
         802 811 812 821
         831 832 841 842
         861 871 881 891
         902 911 912 921
         931 932 941 942
         961 971 981 991
  END

    if (1)                                                                        # Perform insertions and deletions and track the expected results in a Perl hash.
     {my $e = 0;

      is_deeply $t->height, my $h = 4;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

      for my $k(sort {reverse($a) cmp reverse($b)} keys %t)
       {for my $K(sort keys %t)
         {++$e unless $t->find($K) == $t{$K};
         }
          ++$e unless $t->find($k) == $t{$k};  $t->delete($k); delete $t{$k};
          ++$e if     $t->find($k);

          ++$e if     $t->height > $h;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

       }

      is_deeply $t->height, 0;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

      ok !$e;
     }

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 $keysPerNode = 3;

    my $t = new; my $N = 16;

    $t = insert($t, $_, 2 * $_) for 1..$N;

    ok T($t, <<END);
   6
     3
       1 2
       4 5
     9 12 15
       7 8
       10 11
       13 14
       16
  END


    ok $t->find(16); $t = $t->delete(16);  ok !$t->find(16); ok T($t, <<END);  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

   6
     3
       1 2
       4 5
     9 12 14
       7 8
       10 11
       13
       15
  END


    ok $t->find(15); $t = $t->delete(15);  ok !$t->find(15); ok T($t, <<END);  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

   6
     3
       1 2
       4 5
     9 12
       7 8
       10 11
       13 14
  END


    ok $t->find(14); $t = $t->delete(14);  ok !$t->find(14); ok T($t, <<END);  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

   6
     3
       1 2
       4 5
     9 12
       7 8
       10 11
       13
  END


    ok $t->find(13); $t = $t->delete(13);  ok !$t->find(13); ok T($t, <<END);  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

   6
     3
       1 2
       4 5
     9 11
       7 8
       10
       12
  END


    ok $t->find(12); $t = $t->delete(12);  ok !$t->find(12); ok T($t, <<END);  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

   6
     3
       1 2
       4 5
     9
       7 8
       10 11
  END


    ok $t->find(11); $t = $t->delete(11);  ok !$t->find(11); ok T($t, <<END);  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

   6
     3
       1 2
       4 5
     9
       7 8
       10
  END


    ok $t->find(10); $t = $t->delete(10);  ok !$t->find(10); ok T($t, <<END);  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

   3 6 8
     1 2
     4 5
     7
     9
  END


    ok $t->find(9);  $t = $t->delete(9);   ok !$t->find(9);  ok T($t, <<END);  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

   3 6
     1 2
     4 5
     7 8
  END


    ok $t->find(8);  $t = $t->delete(8);   ok !$t->find(8);  ok T($t, <<END);  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

   3 6
     1 2
     4 5
     7
  END


    ok $t->find(7);  $t = $t->delete(7);   ok !$t->find(7);  ok T($t, <<END);  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

   3 5
     1 2
     4
     6
  END


    ok $t->find(6);  $t = $t->delete(6);   ok !$t->find(6);  ok T($t, <<END);  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

   3
     1 2
     4 5
  END


    ok $t->find(5);  $t = $t->delete(5);   ok !$t->find(5);  ok T($t, <<END);  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

   3
     1 2
     4
  END


    ok $t->find(4);  $t = $t->delete(4);   ok !$t->find(4);  ok T($t, <<END);  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

   2
     1
     3
  END

    ok $t->find(3);

    $t = $t->delete(3);  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

    ok !$t->find(3);

    ok T($t, <<END);
   1 2
  END


    ok $t->find(2);  $t = $t->delete(2);   ok !$t->find(2);  ok T($t, <<END);  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

   1
  END


    ok $t->find(1);  $t = $t->delete(1);   ok !$t->find(1);  ok T($t, <<END);  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

  END

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 $keysPerNode = 15;

    my $t = new; my $N = 256;


    $t = insert($t, $_, 2 * $_) for 1..$N;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲


    is_deeply $t->printKeys, <<END;
   72 144
     9 18 27 36 45 54 63
       1 2 3 4 5 6 7 8
       10 11 12 13 14 15 16 17
       19 20 21 22 23 24 25 26
       28 29 30 31 32 33 34 35
       37 38 39 40 41 42 43 44
       46 47 48 49 50 51 52 53
       55 56 57 58 59 60 61 62
       64 65 66 67 68 69 70 71
     81 90 99 108 117 126 135
       73 74 75 76 77 78 79 80
       82 83 84 85 86 87 88 89
       91 92 93 94 95 96 97 98
       100 101 102 103 104 105 106 107
       109 110 111 112 113 114 115 116
       118 119 120 121 122 123 124 125
       127 128 129 130 131 132 133 134
       136 137 138 139 140 141 142 143
     153 162 171 180 189 198 207 216 225 234 243
       145 146 147 148 149 150 151 152
       154 155 156 157 158 159 160 161
       163 164 165 166 167 168 169 170
       172 173 174 175 176 177 178 179
       181 182 183 184 185 186 187 188
       190 191 192 193 194 195 196 197
       199 200 201 202 203 204 205 206
       208 209 210 211 212 213 214 215
       217 218 219 220 221 222 223 224
       226 227 228 229 230 231 232 233
       235 236 237 238 239 240 241 242
       244 245 246 247 248 249 250 251 252 253 254 255 256
  END

    if (1)
     {my $n = 0;
      for my $i(1..$N)
       {my $ii = $t->find($i);
         ++$n if $t->find($i) eq 2 * $i;
       }
      ok $n == $N;
     }

    local $keysPerNode = 15;

    my $t = new; my $N = 256;


    $t = insert($t, $_, 2 * $_) for reverse map{scalar reverse} 1..$N;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲


    is_deeply $t->printKeys, <<END;
   371
     09 18 032 48 061 75 86 99 132 202 252 322
       001 002 03 04 05 06 07 08
       011 012 13 14 15 16 17
       19 021 022 23 24 25 26 27 28 29 031
       33 34 35 36 37 38 39 041 042 43 44 45 46 47
       49 051 052 53 54 55 56 57 58 59
       62 63 64 65 66 67 68 69 071 72 73 74
       76 77 78 79 081 82 83 84 85
       87 88 89 091 92 93 94 95 96 97 98
       101 102 111 112 121 122 131
       141 142 151 152 161 171 181 191 201
       211 212 221 222 231 232 241 242 251
       261 271 281 291 301 302 311 312 321
       331 332 341 342 351 352 361
     452 542 622 681 732 822 891
       381 391 401 402 411 412 421 422 431 432 441 442 451
       461 471 481 491 501 502 511 512 521 522 531 532 541
       551 552 561 571 581 591 601 602 611 612 621
       631 632 641 642 651 652 661 671
       691 701 702 711 712 721 722 731
       741 742 751 761 771 781 791 801 802 811 812 821
       831 832 841 842 851 861 871 881
       901 902 911 912 921 922 931 932 941 942 951 961 971 981 991
  END

    if (1)
     {my $n = 0;
      for my $i(map {scalar reverse} 1..$N)
       {my $ii = $t->find($i);
         ++$n if $t->find($i) eq 2 * $i;
       }
      ok $n == $N;
     }

iterator($tree)

Make an iterator for a tree

     Parameter  Description
  1  $tree      Tree

Example:

    local $keysPerNode = 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 $keysPerNode = 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;

printKeys($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 $keysPerNode = 15;

    my $t = new; my $N = 256;

    $t = insert($t, $_, 2 * $_) for 1..$N;


    is_deeply $t->printKeys, <<END;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

   72 144
     9 18 27 36 45 54 63
       1 2 3 4 5 6 7 8
       10 11 12 13 14 15 16 17
       19 20 21 22 23 24 25 26
       28 29 30 31 32 33 34 35
       37 38 39 40 41 42 43 44
       46 47 48 49 50 51 52 53
       55 56 57 58 59 60 61 62
       64 65 66 67 68 69 70 71
     81 90 99 108 117 126 135
       73 74 75 76 77 78 79 80
       82 83 84 85 86 87 88 89
       91 92 93 94 95 96 97 98
       100 101 102 103 104 105 106 107
       109 110 111 112 113 114 115 116
       118 119 120 121 122 123 124 125
       127 128 129 130 131 132 133 134
       136 137 138 139 140 141 142 143
     153 162 171 180 189 198 207 216 225 234 243
       145 146 147 148 149 150 151 152
       154 155 156 157 158 159 160 161
       163 164 165 166 167 168 169 170
       172 173 174 175 176 177 178 179
       181 182 183 184 185 186 187 188
       190 191 192 193 194 195 196 197
       199 200 201 202 203 204 205 206
       208 209 210 211 212 213 214 215
       217 218 219 220 221 222 223 224
       226 227 228 229 230 231 232 233
       235 236 237 238 239 240 241 242
       244 245 246 247 248 249 250 251 252 253 254 255 256
  END

    if (1)
     {my $n = 0;
      for my $i(1..$N)
       {my $ii = $t->find($i);
         ++$n if $t->find($i) eq 2 * $i;
       }
      ok $n == $N;
     }

    local $keysPerNode = 15;

    my $t = new; my $N = 256;

    $t = insert($t, $_, 2 * $_) for reverse map{scalar reverse} 1..$N;


    is_deeply $t->printKeys, <<END;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

   371
     09 18 032 48 061 75 86 99 132 202 252 322
       001 002 03 04 05 06 07 08
       011 012 13 14 15 16 17
       19 021 022 23 24 25 26 27 28 29 031
       33 34 35 36 37 38 39 041 042 43 44 45 46 47
       49 051 052 53 54 55 56 57 58 59
       62 63 64 65 66 67 68 69 071 72 73 74
       76 77 78 79 081 82 83 84 85
       87 88 89 091 92 93 94 95 96 97 98
       101 102 111 112 121 122 131
       141 142 151 152 161 171 181 191 201
       211 212 221 222 231 232 241 242 251
       261 271 281 291 301 302 311 312 321
       331 332 341 342 351 352 361
     452 542 622 681 732 822 891
       381 391 401 402 411 412 421 422 431 432 441 442 451
       461 471 481 491 501 502 511 512 521 522 531 532 541
       551 552 561 571 581 591 601 602 611 612 621
       631 632 641 642 651 652 661 671
       691 701 702 711 712 721 722 731
       741 742 751 761 771 781 791 801 802 811 812 821
       831 832 841 842 851 861 871 881
       901 902 911 912 921 922 931 932 941 942 951 961 971 981 991
  END

    if (1)
     {my $n = 0;
      for my $i(map {scalar reverse} 1..$N)
       {my $ii = $t->find($i);
         ++$n if $t->find($i) eq 2 * $i;
       }
      ok $n == $N;
     }

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

Attributes

The following is a list of all the attributes in this package. A method coded with the same name in your package will over ride the method of the same name in this package and thus provide your value for the attribute in place of the default value supplied for this attribute by this package.

Replaceable Attribute List

maximumNumberOfKeys maximumNumberOfNodes minimumNumberOfKeys

maximumNumberOfKeys

Maximum number of keys per node.

maximumNumberOfNodes

Maximum number of children per parent.

minimumNumberOfKeys

Minimum number of keys per node.

Private Methods

new()

Create a new multi-way tree node.

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

splitFullLeafNode($node)

Split a full leaf 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

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

Index

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

2 deleteElement - Delete an element in a node

3 fillFromLeftOrRight - Fill a node from the specified sibling

4 find - Find a key in a tree returning its associated data or undef if the key does not exist

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

6 full - Confirm that a node is full.

7 halfFull - Confirm that a node is half full.

8 height - Return the height of the tree

9 indexInParent - Get the index of a node in its parent

10 insert - Insert a key and data into a tree

11 iterator - Make an iterator for a tree

12 leaf - Confirm that the tree is a leaf.

13 leftMost - Return the left most node below the specified one

14 mergeOrFill - make a node larger than a half node

15 mergeRoot - Merge the root node

16 mergeWithLeftOrRight - Merge two adjacent nodes

17 new - Create a new multi-way tree node.

18 printKeys - Print the keys in a tree optionally marking the active key

19 reUp - Reconnect the children to their new parent

20 rightMost - Return the right most node below the specified one

21 root - Return the root node of a tree.

22 separateData - Return ([lower], center, [upper]) data

23 separateKeys - Return ([lower], center, [upper]) keys.

24 separateNode - Return ([lower], [upper]) children

25 splitFullLeafNode - Split a full leaf and return the new parent or return the existing node if it does not need to be split.

26 splitFullNode - Split a full node and return the new parent or return the existing node if it does not need to be split

27 splitLeafNode - Split a full leaf node in assuming it has a non full parent

28 splitNode - Split a full node in half assuming it has a non full parent

29 splitRootLeafNode - Split a full root that is also a leaf

30 splitRootNode - Split a full root

31 T - Write a result to the log file

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