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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.