# Documentation of “bin number” trees

TL;DR: I implemented a special (?) binary tree and can't find any further details on the method I used on the internet. I would like to know if there are any scientific papers discussing my implementation.

Long version:

I saw this very interesting binary tree using "bin numbers" in RFC 7574. The leaf nodes contain data and consist of even numbers, and a single integer can be used to address ranges of leaves.

                               7
/ \
/     \
/         \
/             \
3                11
/ \              / \
/   \            /   \
/     \          /     \
1       5        9       13
/ \     / \      / \      / \
0   2   4   6    8   10  12   14

C0  C1  C2  C3   C4  C5  C6   C7


Implementation details are not part of this RFC, so I did the implementation myself. I use a flat array so that every node is positioned at the index of their "bin number" for fast O(1) access:

Tree = [ Node0, Node1, Node2, ... ]


I created some methods to inspect a single node:

depth(index) = log2( ~index & (index + 1))        // depth from bottom
pos(index)   = (index >> (depth(index) + 1)) & 1  // left or right


And some helper methods to navigate the tree/array:

lChild(index) = (index & 1) ? index - 2 ** (depth(index) - 1) : -1
rChild(index) = (index & 1) ? index + 2 ** (depth(index) - 1) : -1
parent(index) = pos(index) ? index - 2 ** depth(index) : index + 2 ** depth(index)


** = exp operator