2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Hendrik Jan Dec 21 '18 at 14:01
  • $\begingroup$ 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) $\endgroup$ – mby0 Dec 21 '18 at 14:36
  • 2
    $\begingroup$ 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). $\endgroup$ – Hendrik Jan Dec 21 '18 at 14:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.