Build a tree for $(-\infty,+\infty)$ similar to dyadic interval trees for $\left[0,+\infty\right)$

Question

Using dyadic intervals, I can build a binary tree for $\left[0,+\infty\right)$ by having a node the $i$-th at level $l$ representing the range $\left[i\cdot2^l,(i+1)\cdot2^l\right)$ and has the $(i)$- and $(i+1)$ at level $l-1$ as children.

I would like to build a similar tree for $(-\infty,+\infty)$, but it is not clear to me how this can be done using a single tree. One solution would be to use two binary trees as described above, one for positive and one for negative numbers. Is there a solution that uses a single tree? The tree does not have to be binary, but it would be good if there is a bound on the branching factor.

The intended use of this is to maintain information about floating point values. That is, $l$ can also be negative. It can be used, for example, to do approximate percentile queries. See for example: https://github.com/twitter/algebird/blob/develop/docs/src/main/tut/datatypes/approx/q_tree.md and https://github.com/twitter/algebird/blob/develop/algebird-core/src/main/scala/com/twitter/algebird/QTree.scala.

Answer 1

Maybe the surreal numbers will work as dyadic intervals.

Surreal numbers have a reduced form containing a left and right surreal which is like a range. I think these ranges match the description of "dyadic intervals" in the link you provided.

Nan (the empty set) is considered to be positive or negative infinity depending on whether it is on the left or right side of the reduce surreal form.

The bit form of these dyadic intervals will be the right/left path down the surreal tree diagram (https://en.wikipedia.org/wiki/Surreal_number)

They start like this:

Surreal No.  Tree path  Binary Form   Reduced Form    Interval
   0            nan
   1            ""            1           {0|0}      {-inf,+inf}
   2           "L"           10           {0|1}      {-inf,0}
   3           "R"           11           {1|0}      {0,+inf}
   4           "LL"         100           {0|2}      {-inf,-1}
   5           "LR"         101           {2|1}      {-1,0}
   6           "RL"         110           {1|3}      {0,1}
   7           "RR"         111           {3|0}      {1,+inf}

You would also have to imagine that half way between + and - infinity is zero. Then half way between zero and +inf is 1. Then half way between 1 and +inf is 2. etc for all integers. Maybe that makes it unsuitable.

I am unsure whether surreal numbers are related to your question. I had already noticed that the surreal numbers have a quality of half ranges when I read your post.

Edit:

• a "1" bit is prefixed to the L/R path of the given surreal. Where L=0 and R=1. Ex:-1/2 is LR on the surreal tree diagram. LR converts to 01 and then we prefix a "1" to get "101". 101 is the binary form of the LR path.
• Surreal numbers are listed as their birth number. Not their value number. Their values of their left/right reduced sides are used to determine the ranges they represent.
• I can provide python code which produces these list if you want to see how these numbers and ranges are created.
• the example provided above was made by hand and certainly contains mistakes.