Basic Solution
Fibonacci trees have several properties that can be used to form a compact Fibonacci tree:
- Every node in a Fibonacci tree is itself a Fibonacci tree.
- The number of nodes in a Fibonacci tree of height n is equal to Fn+2 - 1.
- The number of nodes in between a node and its left child is equal to the number of nodes in the node's left child's right child.
- The number of nodes in between a node and its right child is equal to the number of nodes in the node's right child's left child.
Without loss of generality, we will assume our Fibonacci tree has the following additional property:
- If a node has height n, then the left child has height n-2, and the right child has height n-1.
Combining these properties, we find that the number of nodes in between a node of height n and its left and right children is equal to Fn-1 - 1, and we can use this fact to generate a compact Fibonacci tree:
static int fibs[] = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170};
void fibonacci_subtree(int root, int height, int *fib)
{
if (height == 1) {
insert_into_tree(root);
} else if (height == 2) {
insert_into_tree(root + *fib);
} else if (height >= 3) {
fibonacci_subtree(root - *fib, height - 2, fib - 2);
fibonacci_subtree(root + *fib, height - 1, fib - 1);
}
}
...
for (height = 1; height <= max_height; height++) {
fibonacci_subtree(0, height, fibs + max_height - 1);
}
This algorithm generates the minimum number of nodes possible for a given height, and it also produces the minimum possible range. You can shift the range around by making the root node something other than zero.
Compact Fill Algorithm
The basic solution only produces Fibonacci trees, which always have Fn+2 - 1 nodes. What if you want to generate an unbalanced tree with a different number of nodes while still minimizing the range?
In that case, you need to generate the next larger Fibonacci tree with a few modifications:
- Some number of elements at the end of the sequence will not be inserted.
- Those elements will create gaps, and the location of those gaps need to be tracked.
- The difference between nodes needs to be reduced appropriately.
Here's one approach that still takes advantage of the recursive nature of the solution:
void fibonacci_subtree(int root, int height, int *fib, int num_gaps, bool prune_gaps)
{
if(height < 1)
return;
if(prune_gaps && height <= 2) {
if(!num_gaps) {
if(height == 1) {
insert_into_tree(root);
} else if(height == 2) {
insert_into_tree(root + *fib);
}
}
return;
}
if(height == 1) {
insert_into_tree(root);
} else {
int max_rr_gaps = *(fib - 1);
int rr_gaps = num_gaps > max_rr_gaps ? max_rr_gaps : num_gaps;
num_gaps -= rr_gaps;
int max_rl_gaps = *(fib - 2);
int rl_gaps = num_gaps > max_rl_gaps ? max_rl_gaps : num_gaps;
num_gaps -= rl_gaps;
int lr_gaps = num_gaps > max_rl_gaps ? max_rl_gaps : num_gaps;
num_gaps -= lr_gaps;
int ll_gaps = num_gaps;
fibonacci_subtree(root - *fib + lr_gaps, height - 2, fib - 2, lr_gaps + ll_gaps, prune_gaps);
fibonacci_subtree(root + *fib - rl_gaps, height - 1, fib - 1, rr_gaps + rl_gaps, prune_gaps);
}
}
The main loop is slightly more complicated to accommodate an arbitrary range of keys:
void compact_fill(int min_key, int max_key)
{
int num_nodes = max_key - min_key + 1;
int *fib = fibs;
int max_height = 0;
while(num_nodes > *(fib + 2) - 1) {
max_height++;
fib++;
}
int num_gaps = *(fib + 2) - 1 - num_nodes;
int natural_max = *(fib + 1) - 1;
int max_r_gaps = *(fib - 1);
int r_gaps = num_gaps > max_r_gaps ? max_r_gaps : num_gaps;
natural_max -= r_gaps;
int root_offset = max_key - natural_max;
for (int height = 1; height <= max_height; height++) {
fibonacci_subtree(root_offset, height, fibs + max_height - 1, num_gaps, height == max_height);
}
}
Closed Form Solution
If you look at the differences between every pair of words generated by the basic solution, you find that they alternate between two sequential elements of the Fibonacci sequence. This alternating pattern is defined by the Fibonacci word:
A Fibonacci word is a specific sequence of binary digits (or symbols from any two-letter alphabet). The Fibonacci word is formed by repeated concatenation in the same way that the Fibonacci numbers are formed by repeated addition.
It turns out there's a closed-form solution for the Fibonacci word:
static double phi = (1.0 + sqrt(5.0)) / 2.0;
bool fibWord(int n)
{
return 2 + floor(n * phi) - floor((n + 1) * phi);
}
You can use this closed-form solution to solve the problem using two nested loops:
// Used by the outer loop to calculate the first key of the inner loop
int outerNodeKey = 0;
int *outerFib = fibs + max_height - 1;
for(int height = 1; height <= max_height; height++) {
int innerNodeKey = outerNodeKey;
int *smallFib = fibs + max_height - height + 3; // Hat tip: @WalterTross
for(int n = fibs[height] - 1; n >= 0; n--) {
insert_into_tree(innerNodeKey);
// Use closed-form expression to pick between two elements of the Fibonacci sequence
bool smallSkip = 2 + floor(n * phi) - floor((n + 1) * phi);
innerNodeKey += smallSkip ? *smallFib : *(smallFib + 1);
}
if(height & 0x1) {
// When height is odd, add *outerFib.
outerNodeKey += *outerFib;
} else {
// Otherwise, backtrack and reduce the gap for next time.
outerNodeKey -= (*outerFib) << 1;
outerFib -= 2;
}
}