Path-Indexed Prefix Tree
Classifying numbers with respect to their path
Last updated
Classifying numbers with respect to their path
Last updated
We will now consider yet another binary tree, called Path-Indexed Prefix Tree (PIPTree).
A PIPTree for a natural number is defined as follows:
Nodes are indexed, with the root index as 1.
For a node with index , the left child has index and right child has index .
Each node represents the following:
A path that is the binary representation of node index . The length of path is .
A number at path , that is .
A prefix defined by the ECFs of sequences of and the next number at that path, calculated as .
Notice that path with all zeros is not considered here, which would be a problem as we have previously mentioned powers of two have path of all zeros. Instead, we append 1 to their path, assigning them to the root.
🟢 The good case:
🔴 The bad case:
We will refer to this property as the nature of a node, i.e. a node can have good nature or bad nature. The good case is named so because the bijective map of prefix behaves exactly the same as the number does. It is the opposite for the bad case.
As you might guess, this is the source of colors we can see in our tree example. It is really hard to come up with any pattern regarding the nature of a node; nothing seemed evident to the author nevertheless.
Computationally, one can calculate the children and check the prefix to find the nature, but that is not satisfactory. We would like to find the nature of any node, just by looking at that node! There is a way to do so. 🎉
In a PIPTree for paths of length , there will be nodes.
Due to path indexing and the nature of , we get the following property: for a node with number :
the left child has number where the root number is
right child has number
It is quite a neat property that this way, you will obtain all numbers from to . Furthermore, the leaf nodes will all be odd numbers, and the rightmost branch of the tree will all be powers of two.
When we examine the prefix of each node, we notice a pattern. Consider a node with prefix , and root prefix . There are two observed cases:
Left child has prefix
Right child has prefix
Left child has prefix
Right child has prefix