3
$\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?

Improve this question
$\endgroup$
3
  • $\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
    Commented Dec 21, 2018 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
    Commented Dec 21, 2018 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
    Commented Dec 21, 2018 at 14:44

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.