Kepler Tree¶

The default and only tree currently is by Kepler.

In principle similar bit reversal etc variations as in "RationalsTree" would be possible.

    N=1                             1/2
                              ------   ------
    N=2 to N=3             1/3               2/3
                          /    \            /   \
    N=4 to N=7         1/4      3/4      2/5      3/5
                       | |      | |      | |      | |
    N=8 to N=15     1/5  4/5  3/7 4/7  2/7 5/7  3/8 5/8

A node descends as

          X/Y
        /     \
    X/(X+Y)  Y/(X+Y)

Kepler described the tree as starting at 1, ie. 1/1, which descends to two identical 1/2 and 1/2. For the code here a single copy starting from 1/2 is used.

Plotting the N values by X,Y is as follows. Since it's only fractions X/Y<1, ie. X<Y, all points are above the X=Y diagonal. The unused X,Y positions are where X and Y have a common factor. For example X=2,Y=6 have common factor 2 so is never reached.

    12  |    1024                  26        27                1025
    11  |     512   48   28   22   34   35   23   29   49  513     
    10  |     256        20                  21       257          
     9  |     128   24        18   19        25  129               
     8  |      64        14        15        65                    
     7  |      32   12   10   11   13   33                         
     6  |      16                  17                              
     5  |       8    6    7    9                                   
     4  |       4         5                                        
     3  |       2    3                                             
     2  |       1                                                  
     1  |
    Y=0 |   
         ----------------------------------------------------------
          X=0   1    2    3    4    5    6    7    8    9   10   11

The X=1 vertical is the fractions 1/Y at the left end of each tree row, which is

    Nstart=2^level

The diagonal X=Y-1, fraction K/(K+1), is the second in each row, at N=Nstart+1. That's the maximum X/Y in each level.

The N values in the upper octant, ie. above the line Y=2*X, are even and those below that line are odd. This arises since X<Y so the left leg X/(X+Y) < 1/2 and the right leg Y/(X+Y) > 1/2. The left is an even N and the right an odd N.

Tree Methods¶

Each point has 2 children, so the path is a complete binary tree.

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

Return the two children of $n, or an empty list if "$n < 1" (before the start of the path).

This is simply "2*$n, 2*$n+1". The children are $n with an extra bit appended, either a 0-bit or a 1-bit.

"$num = $path->tree_n_num_children($n)"

Return 2, since every node has two children, or return "undef" if "$n<1" (before the start of the path).

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

Return the parent node of $n, or "undef" if "$n <= 1" (the top of the tree).

This is simply "floor($n/2)", stripping the least significant bit from $n (undoing what "tree_n_children()" appends).

"$depth = $path->tree_n_to_depth($n)"

Return the depth of node $n, or "undef" if there's no point $n. The top of the tree at N=1 is depth=0, then its children depth=1, etc.

The structure of the tree with 2 nodes per point means the depth is simply floor(log2(N)), so for example N=4 through N=7 are all depth=2.

Tree Descriptive Methods¶

"$num = $path->tree_num_children_minimum()"

"$num = $path->tree_num_children_maximum()"

Return 2 since every node has 2 children, making that both the minimum and maximum.

"$bool = $path->tree_any_leaf()"

Return false, since there are no leaf nodes in the tree.