Math::PlanePath::HTree -- H-tree
use Math::PlanePath::HTree; my $path = Math::PlanePath::HTree->new; my ($x, $y) = $path->n_to_xy (123);
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.
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.
See "FUNCTIONS" in Math::PlanePath for behaviour common to all path classes.
$path = Math::PlanePath::HTree->new ()
Create and return a new path object.
@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).
$n
$n < 1
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).
undef
$n <= 1
@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.
For tree_depth_to_n() it can be noted the sub-trees overlap in the following style,
tree_depth_to_n()
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.
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.
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.
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),
tree_n_children()
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
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
tree_n_parent()
N = 1000xxxx Nparent = 10000xxx right shift except for high 1-bit
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.
tree_n_to_subheight()
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
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
Math::PlanePath, Math::PlanePath::UlamWarburton
http://user42.tuxfamily.org/math-planepath/index.html
Copyright 2013 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/>.
To install Math::PlanePath::HTree, copy and paste the appropriate command in to your terminal.
cpanm
cpanm Math::PlanePath::HTree
CPAN shell
perl -MCPAN -e shell install Math::PlanePath::HTree
For more information on module installation, please visit the detailed CPAN module installation guide.