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.
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?