Kevin Ryde > Math-PlanePath-Toothpick-14 > Math::PlanePath::HTree

Download:
Math-PlanePath-Toothpick-14.tar.gz

Dependencies

Annotate this POD

Website

View/Report Bugs
Module Version: 14   Source  

NAME ^

Math::PlanePath::HTree -- H-tree

SYNOPSIS ^

 use Math::PlanePath::HTree;
 my $path = Math::PlanePath::HTree->new;
 my ($x, $y) = $path->n_to_xy (123);

DESCRIPTION ^

This path is a version of the H-tree starting from an extremity and going breadth-first into successive sub-blocks of the tree.

                                    ...
                                     |
     14 58      57      54      53   | 122     121     118     117
      |  |       |       |       |   |   |       |       |       |
     13 45--38--44      43--37--42   |  93--78--92      91--77--90
      |  |   |   |       |   |   |   |   |   |   |       |   |   |
     12 59   |  56      55   |  52   | 123   | 120     119   | 116
      |      |               |       |       |               |
     11     35------33------34       |      71------67------70
      |      |       |       |       |       |       |       |
     10 60   |  63   |  48   |  51   | 124   | 127   | 112   | 115
      |  |   |   |   |   |   |   |   |   |   |   |   |   |   |   |
     9| 46--39--47   |  40--36--41   |  94--79--95   |  88--76--89
      |  |       |   |   |       |   |   |       |   |   |       |
     8| 61      62   |  49      50   | 125     126   | 113     114
      |              |               |               |
     7|             32--------------64--------------65
      |              |                               |
     6| 14      13   |  30      29      98      97   | 110     109
      |  |       |   |   |       |       |       |   |   |       |
     5| 11---9--10   |  23--19--22      81--72--80   |  87--75--86
      |  |   |   |   |   |   |   |       |   |   |   |   |   |   |
     4| 15   |  12   |  31   |  28      99   |  96   | 111   | 108
      |      |       |       |               |       |       |
     3|      8------16------17              68------66------69
      |      |               |               |               |
     2|  3   |   7      24   |  27     100   | 103     104   | 107
      |  |   |   |       |   |   |       |   |   |       |   |   |
     1|  2---4---5      20--18--21      82--73--83      84--74--85
      |  |       |       |       |       |       |       |       |
     0|  1       6      25      26     101     102     105     106
      |
       -------------------------------------------------------------
       X=0   1   2   3   4   5   6   7   8   9  10  11  12  13  14

Each tree block starts at N=2^k and goes up or right. For example N=8 descends into block N=9 to N=15 above, and N=16 into block N=17 to N=31 to the right. The "spine" points N=2^k continue infinitely but the blocks above or right terminate at sub-depth k.

    Spine         Sub-Tree

     N=1
      |
     N=2 --------- N=3
      |
     N=4 --------- N=5
      |            /  \
      |          N=6  N=7
      |
     N=8 ----------- N=9
      |            /     \
      |        N=10      N=11
      |        /  \      /  \
      |     N=12 N=13  N=14 N=15
      |
     N=16 ---
      |

Within a sub-block the points are a binary tree traversed breadth first and anti-clockwise. So for example N=20,21,22,23 go anti-clockwise, then the next level N=24 to N=31 similarly anti-clockwise.

Notice the pattern made by the blocks is symmetric around the N=2^k spine, so for example at N=64 the preceding parts on the left are the same pattern as the block on the right. The way the numbering runs is different, but the shape is the same.

Infinitely Smaller

The H-tree is usually conceived as an initial H shape growing four smaller H's at each endpoint. That could be had here using a suitable size "up" block such as N=33.

    N = 2*4^k+1 to 4*4^k-1        eg. k=2  N=33 to N=63
    being 2*4^k-1 many points         31 points
    and 2k tree levels                4 levels
    beginning X=4^k/2                 X=8

A "right" sub-part such as N=65 could be used in a similar way if a 2-high 1-wide portion was wanted.

The tree is also often conceived as the branch lengths decreasing by factor sqrt(2) each time. That could be had by X*sqrt(2) to widen all the horizontals.

FUNCTIONS ^

See "FUNCTIONS" in Math::PlanePath for behaviour common to all path classes.

$path = Math::PlanePath::HTree->new ()

Create and return a new path object.

Tree Methods

@n_children = $path->tree_n_children($n)

Return the children of $n, or an empty list if $n has no children (including when $n < 1, ie. before the start of the path).

Within a sub-tree block the children are consecutive N values, but that's not so for the spine points N=2^k. For example N=16 has children N=17 and N=32 which are not consecutive.

$n_parent = $path->tree_n_parent($n)

Return the parent node of $n, or undef if $n <= 1 (the start of the path).

Tree Descriptive Methods

@nums = $path->tree_num_children_list()

Return list 0,1,2 since there are nodes with 0, 1 and 2 children in the tree. N=1 has 1 child and thereafter each point has 0 or 2.

FORMULAS ^

Depth to N

For tree_depth_to_n() it can be noted the sub-trees overlap in the following style,

    Depth

     0  N=1
         |
     1  N=2--
         |   \
     2  N=3   N=4------
               |       \
     3        N=5       N=8 -------------
             /  \        |               \
     4     N=6  N=7     N=9               N=16--------
                       /    \              |          \
     5              N=10      N=11        N=17        N=32-----
                    /  \      /  \        /   \        |       \
     6           N=12 N=13  N=14 N=15   N=18 N=19     N=33      N=64--
                                        /  \ / \      /   \      |

A sub-tree begins at depth k and ends at depth 2k. So tree k-1 has ended at depth 2k-2 leaving tree k as the smallest N for depths 2k-1 and 2k, those being its last two rows. For example depth=3,4 is sub-tree k=2, and depth=5,6 is sub-tree k=3.

The last two rows of sub-tree k have N in binary

    1000000     N=2^k start
     ...
    101xxxx     second last row
    11xxxxx     last row

So third and second highest 1-bit formed by 5=[101]*2^d and 6=[110]*2^d give

    d = floor((depth-3)/2)
    Nrow = / 5*2^d   if depth odd
           \ 6*2^d   if depth even

Eg. depth=5, d=1, Nrow=5*2^1=10, or depth=6, d=1, Nrow=12.

Depth to N End

As can be seen in the "Depth to N" diagram above, the last N in a tree row is always the "spine" point N=2^depth. All sub-trees are run to completion before the next spine point is taken, and those sub-trees have power-of-2 many points.

Depth to Width

The total number of points in a given row is a sum across those sub-trees which are running at that depth. Sub-trees k=floor(depth/2) to k=depth are running and their rows have

    e = floor(depth/2)
    2^(e-1) + 2^(e-2) + ... + 4 + 2 + 1

plus the spine point N=2^depth gives

    width = 2^floor(depth/2)

Notice this is not the same as Nend-Nrow, since the point numbering is not breadth-wise across all sub-trees, only within each sub-tree. This means N descends into sub-trees and then jumps back up again to do the next so rows are not contiguous runs of N.

N Children

For tree_n_children(), on a spine point N=2^k the children are N+1 for the first of the sub-tree and 2N for the next spine point N=2^(k+1),

    spine point N=2^k   children N+1
                                 2N

Otherwise in a sub-tree the children are a bit-shift left

    N          = 10000xxx
    N children / 1000xxx0    left shift except for high 1-bit
               \ 1000xxx1

If the second highest bit of N is a 1-bit then that's the last row of the sub-tree and there's no children

    N = 11xxxxxx    last row, no children

N Parent

For tree_n_parent(), a spine point N=2^k the parent it the preceding spine N=2^(k-1). Otherwise going up a level in a sub-tree is a bit shift

    N       = 1000xxxx
    Nparent = 10000xxx    right shift except for high 1-bit

N to Sub-Tree Height

For tree_n_to_subheight(), the height of the sub-tree at N is the number of 0-bits between the two highest 1-bits of N.

    100010101
     ^^^--------- 3 zeros between highest 1-bits

If there's only a single 1-bit in N then it's an N=2^k "spine" point and the sub-height is infinite since the spine continues infinitely.

This zeros rule works because the sub-trees at each N=2^k are numbered breadth first with 2^m points in each row. For example at N=17 the sub-tree to the right goes

    N binary  N decimal    Sub-Height
    --------  ----------   ----------
    10000     spine N=16    infinite
    10001     N=17             3
    1001x     N=18 to 19       2
    101xx     N=20 to 23       1
    11xxx     N=24 to 31       0     leaf nodes

OEIS ^

Entries in Sloane's Online Encyclopedia of Integer Sequences related to this path include

http://oeis.org/A117625 (etc)

    A164095     N start of each row, tree_depth_to_n()
                  being 5*2^k and 6*2^k alternately

SEE ALSO ^

Math::PlanePath, Math::PlanePath::UlamWarburton

HOME PAGE ^

http://user42.tuxfamily.org/math-planepath/index.html

LICENSE ^

Copyright 2013, 2014 Kevin Ryde

This file is part of Math-PlanePath-Toothpick.

Math-PlanePath-Toothpick is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version.

Math-PlanePath-Toothpick is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with Math-PlanePath-Toothpick. If not, see <http://www.gnu.org/licenses/>.

syntax highlighting: