§ Numbering nodes in a tree

If we consider a tree such as:
b         c
        d   e
The "standard way" of numbering, by starting with a 0 and then appending a 0 on going to the left, appending a 1 on going to the right doesn't make a great deal of sense. On the other hand, we can choose to number them as follows:
  • Consider the root to have value 1
  • Every time we go right, we add 1/2^{height}. When we go left, we subtract 1/2^{height}.
  • This gives us the numbers:
0.5       1.5
       1.25     1.75
  • This also makes intuitive why to find the node to replace 1.5 when we deleteit is to go to the left child 1.25 and then travel as much to the right as possible. That path corresponds to:
1+1/21/4+1/8+1/16+=1+1/21/4+1/4=1.5 \begin{aligned} &1 + 1/2 - 1/4 + 1/8 + 1/16 + \dots \\ &= 1 + 1/2 - 1/4 + 1/4 \\ &= 1.5 \end{aligned}
  • So in the limit, the rightmost leaf of the left child of the parent has the same value as the parent itself. In the non-limit, we get as close aspossible.
  • This also may help intuit hyperbolic space? Distances as we go down in thethree shrink. Thus, it's easier to "escape" away to the fringes of the space,rather than retrace your step. Recall that random walks in hyperbolic spacealmost surely move away from the point of origin. It feels to me like thisexplains why. If going towards the root / decreasing heighttakes distance dd, going deeper into the tree / increasing the heightneeds distance d/2d/2. So a particle would "tend to" travel the shorter distance.