我写了一个作为通用排序容器的AVL树的C语言库为了测试,我想要有一种方法来填充一棵树,使它最大程度地不平衡,也就是说,它包含的节点数有最大的高度。
AVL树具有这样的优点:如果从空树开始,按升序(或降序)插入节点,则树总是完全平衡的(也就是说,对于给定的节点数,树有其最小高度)。从空树T0开始,为每个节点n生成精确平衡的AVL树TN的整数键序列是简单的。
我正在寻找一个(希望是简单的)整数键序列,当插入到最初的空树T0中时,生成的AVL树T0,...,TN都是最大的联合国平衡。
我也会对一个解感兴趣,其中只有最后一棵树TN是最大不平衡的(节点数n将是算法的一个参数)。
满足约束条件的解
发布于 2018-02-06 17:15:39
基本解
Fibonacci树有几个属性,可以用来形成紧凑的Fibonacci树:
在不失去通用性的情况下,我们将假设Fibonacci树具有以下附加属性:
这里有一种方法仍然利用了解决方案的递归特性:
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);
}
}
闭形解
如果查看基本解决方案生成的每一对单词之间的差异,会发现它们在Fibonacci序列的两个顺序元素之间交替。此交替模式Fibonacci word:
Fibonacci字是二进制数字(或来自任何两个字母的字母的符号)的特定序列.。斐波那契词是由重复级联形成的,就像斐波那契数是由重复加法形成的一样。
结果发现Fibonacci字的闭形解:
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;
}
}
https://stackoverflow.com/questions/-100007353
复制相似问题