# 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

I am asking myself if I'm reinventing the wheel here. I would like to verify and optimize my implementation but could not find any more information about this tree or storage method.

Does anybody know how to call this thing?

• At first glance this looks like the arry implementation of complete binary trees like usually done in case of the heap priority queue. But I might be overlooking some of your specific requirements. – Hendrik Jan Dec 21 '18 at 14:01
• Thanks for the hint. Yes, it is an implicit data structure, but it is not breadth-frist. The method of index-calculation is different (more like a horizontal traversal from left to right) – mby0 Dec 21 '18 at 14:36
• Sorry, you are right. Please have a look at Binary Indexed Trees, which are also known as Fenwick trees. I am not really familiar with those, but the pictures in this answer look similar to yours. (Fenwick trees have a specific use in mind though). – Hendrik Jan Dec 21 '18 at 14:44