基本解决方案
斐波那契树有几个属性可以用来形成一个紧凑的斐波那契树：
- 斐波那契树中的每个节点本身就是一棵斐波那契树。
- 高度为 n 的斐波那契树中的节点数等于 F n+2 - 1。
- 节点与其左孩子之间的节点数等于该节点左孩子的右孩子中的节点数。
- 节点与其右孩子之间的节点数等于该节点右孩子的左孩子中的节点数。
不失一般性，我们将假设我们的斐波那契树具有以下附加属性：
- 如果一个节点的高度为 n，则左孩子的高度为 n-2，右孩子的高度为 n-1。
结合这些性质，我们发现高度为 n 的节点与其左右子节点之间的节点数等于 F n-1 - 1，我们可以利用这一事实生成紧凑的斐波那契树：
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);
}
该算法为给定高度生成可能的最小节点数，并且它还生成最小可能范围。您可以通过使根节点不为零来移动范围。
紧凑填充算法
基本解决方案只生成斐波那契树，它总是有 F n+2 - 1 个节点。如果您想生成具有不同数量节点的不平衡树，同时仍然最小化范围怎么办？
在这种情况下，您需要通过一些修改生成下一个更大的斐波那契树：
- 序列末尾的一些元素将不会被插入。
- 这些元素将产生差距，并且需要跟踪这些差距的位置。
- 节点之间的差异需要适当减小。
这是一种仍然利用解决方案的递归性质的方法：
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);
}
}
主循环稍微复杂一些，以适应任意范围的键：
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);
}
}
封闭式解决方案
如果您查看由基本解决方案生成的每对单词之间的差异，您会发现它们在斐波那契数列的两个连续元素之间交替出现。这种交替模式由斐波那契字定义：
斐波那契字是二进制数字（或任何两个字母字母表中的符号）的特定序列。斐波那契字是通过重复连接形成的，就像斐波那契数是通过重复加法形成的一样。
事实证明，斐波那契词有一个封闭形式的解决方案：
static double phi = (1.0 + sqrt(5.0)) / 2.0;
bool fibWord(int n)
{
return 2 + floor(n * phi) - floor((n + 1) * phi);
}
您可以使用这个封闭形式的解决方案来解决使用两个嵌套循环的问题：
// 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;
}
}