/ 
Math-PlanePath-Toothpick-18
River stage zero No dependents
/ Math::PlanePath::HTree

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 row 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 goes 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. The N=1 start is not like this, it begins at a corner and grows across.

A central growth can be had here by beginning at a suitable sized "up" direction block. For example N=33 in the sample above. "H" shaped parts grow symmetrically around such a start.

Nmid = 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 rows                     4 rows
beginning X=4^k/2                    X=8

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

The tree is also often conceived as branch lengths decreasing by factor sqrt(2) each time. That could be had here using 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.

Level Methods

($n_lo, $n_hi) = $path->level_to_n_range($level)

Return (1, 2*4**$level - 1). This is a square block of points X,Y <= 2*(2^level-1).

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(), a spine point N=2^k has two children, begin 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

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, 2015 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/>.