Sum of a binary tree

Question

I have a binary tree which leafs have a size of 1, and the parent double in size at each level.

I project those nodes on a linear axe (memory space).

I need to get the equation that gives the adress of the node with the id of the node.

Here is the tree :

 7 <- size=8
 3 11 <- size=4
 1 5 9 13 <- size=2
 0 2 4 6 8 10 12 14 <- size=1

The address space with the sizes of the nodes :

1 2 1 4 1 2 1 8 1 2 1 4 1 2 1

So the first results are :

f(0) = 0
f(1) = 1
f(2) = 3
f(3) = 4
f(4) = 8
f(5) = 9
f(6) = 11
f(7) = 12
f(8) = 20

What is the formula of this layout ?

Answer 1

I don't understand where the function f at the end comes from? How does it relate to the tree and node indices and weights?

Answer 2

Usually, when you want to lay out a binary tree on an array, you use 2 * i + 1 to get to the left child of a node, 2 * i + 2 to get to the right, which gives:

0 -> 1, 2
1 -> 3, 4
2 -> 5, 6
3 -> 7, 8
and so on.

I realize that this is not how you have it arranged in the question.

Answer 3

it takes the id of the node (cf schema) and gives the position in memory.

For instance the node 3 is after 0, 1 and 2 so f(3) = 1 + 2 + 1 = 4

Answer 4

The sequence 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 is almost the same as this sequence: https://oeis.org/A007814 (if A(i) is the ith term of the oeis sequence, then 2**A(i) is the ith term of your sequence, where ** is exponent).

Answer 5

@stef it is different, there is plenty of variations possible for this, depending of the size(s) of the nodes. There will always a power of 2, but with other elements.

Answer 6

Node n is preceded by n nodes of size at least 1. Half of those nodes, rounded down, have a size that is at least 1 greater (2 instead of 1). Half of those further nodes, rounded down, have a size that is at least 2 greater (4 instead of 2). Half of those have a size that is at least 4 greater.

We can denote rounding down using the floor operator, ⌊x⌋.

Therefore, the offset of node n from the beginning is n + ∑_0<i<∞ ⌊n/2ⁱ⌋(2ⁱ−2ⁱ⁻¹) = n + ∑_0<i<∞ ⌊n/2ⁱ⌋2ⁱ⁻¹.

This is integer sequence A006520 except it includes an initial 0.

The following C code demonstrates a calculation of it.

#include <stdio.h>
static unsigned int f(unsigned int n)
{
 unsigned int t = n;
 for (unsigned int p = 1; n /= 2; p *= 2)
 t += p*n;
 return t;
}
int main(void)
{
 for (unsigned int n = 0; n < 20; ++n)
 printf("%u -> %u.\n", n, f(n));
}

Equivalently, the bits for the binary of n may be reinterpreted as bit i having position value 2ⁱ⁻¹•(i+2), instead of the normal 2ⁱ. Thus, bit 0 has value 1, bit 1 has value 3, bit 2 has value 6, bit 3 has value 20, and so on. This code demonstrates that:

static unsigned int f(unsigned int n)
{
 unsigned int t = 0;
 /* i is the bit index.
 d tracks the power, 2^(i-1). However, it would need to be 1/2 for the
 first iteration, so instead we make it double the power and divide by 2
 when using it.
 */
 for (unsigned int i = 0, d = 1; n; i += 1, d *= 2, n /= 2)
 t += (n&1) * (i+2)*d/2;
 return t;
}

OP writes in a comment:

it is different, there is plenty of variations possible for this, depending of the size(s) of the nodes.

If the size of a node at level i is s(i), where i is 0 for a leaf and 1 more for each successive parent level, then a general formula is n•s(0) + ∑_0<i<∞ ⌊n/2ⁱ⌋(s(i)−s(i−1)).

Answer 7

@Eric I was expecting a nice formula with some 2^ shannanigans and no recursion ...

But I was a bit naïve. Thank you for your analysis & result, I totally take it !

Very interesting last remark, but I am not sure to understand sum_0<i<∞ is it an infinite sum ? Or something else ? I am in basic C I don't have access to advanced mathematics operation.

Answer 8

It is nominally an infinite sum, but the terms are zero once 2ⁱ exceeds n. So it could also be written as ∑_{0 < i ≤ log 2n}.

Answer 9

@Eric oh ok so with __builtin_clz perfect.