如何最大限度地产生不平衡的AVL树 [英] How to generate maximally unbalanced AVL trees
问题描述
我已经写了AVL树 C语言库为通用有序容器的。为测试目的，我想有一种方法来填充树，以便它最大是不平衡的，即，使之具有最大高度为它包含的节点的数目。
I have written a C language library of AVL trees as general purpose sorted containers. For testing purposes, I would like to have a way to fill a tree so that it is maximally unbalanced, i.e., so that it has the maximum height for the number of nodes it contains.
AVL树有很好的特性，如果从空树开始，您在上升（或下降）的顺序插入节点，树总是完全平衡（也就是说，它有它的最小高度为节点给定数量） 。整数键的一个序列产生一个完全平衡的AVL树T <子> N 为节点的每个数n，从空树T <子> 0 开始，简直就是
AVL trees have the nice property that if, starting from the empty tree, you insert nodes in ascending (or descending) order, the tree is always exactly balanced (i.e., it has its minimum height for a given number of nodes). One sequence of integer keys that generates an exactly balanced AVL tree Tn for every number of nodes n, starting from the empty tree T0, is simply
- K <子> 1 = 0
- K <子> N + 1 = K <子> N +1，也就是说，K <子> N = N-1
- k1 = 0
- kn+1 = kn+1 , i.e., kn = n-1
我在找整数键的（希望简单）序列，当在初始为空树T <子> 0 插入，生成AVL树牛逼<子> 0 。 ..，T <子> N 的都是最大的取消的平衡。
I'm looking for a (hopefully simple) sequence of integer keys that, when inserted in the initially empty tree T0, generates AVL trees T0, ..., Tn that are all maximally unbalanced.
我也将有兴趣的溶液，其中只有最后树，T <子> N ，最大是不平衡（节点的数量n将是该算法的参数）。
I would also be interested in a solution where only the last tree, Tn, is maximally unbalanced (the number of nodes n would be a parameter of the algorithm).
有一个解决方案，满足约束
A solution satisfying the constraint
- 最大值（K <子> 1 ，...，K <子> N ） - 分（K <子> 1 ，...，K <子> ñ）+ 1≤2 N
- max(k1, ..., kn) - min(k1, ..., kn) + 1 ≤ 2 n
为preferrable，但没有严格要求。正的4而不是2 N的一个关键的范围可能是一个合理的目标。
is preferrable, but not strictly required. A key range of 4 n instead of 2 n may be a reasonable target.
我没能在互联网上找到关于任何事情的产生，通过插入，在最大高度的AVL树。当然，产生的树木我正在寻找的顺序将包括所有所谓的斐波那契树，这是一个给定的深度与节点的最小数量的AVL树。有趣地，在英文维基百科甚至没有提到斐波那契树（也斐波那契数字！）在AVL树的文章，而德国维基百科有一个很好的文章完全奉献给他们。但我还是在黑暗中关于我的问题。
I've not been able to find anything on the Internet regarding the generation, by insertion, of AVL trees of maximal height. Of course, the sequence of generated trees I'm looking for will include all so-called Fibonacci-trees, which are the AVL trees of a given depth with the minimal number of nodes. Funnily, the English Wikipedia does not even mention Fibonacci trees (nor Fibonacci numbers!) in the article on AVL trees, while the German Wikipedia has a very good article completely dedicated to them. But I'm still in the dark regarding my question.
C语言位摆弄黑客们的欢迎。
C language bit twiddling hacks are welcome.
推荐答案
基本解决方案
斐波树木具有可以被用于形成一个紧凑斐波树几个属性：
Fibonacci trees have several properties that can be used to form a compact Fibonacci tree:
- 在一个斐波那契树中的每个节点本身就是一个斐波那契树。
- 在高度为n的斐波树节点的数量等于至F <子> n + 2中 - 1
- 在一个节点和它的左子之间的节点的数量等于在节点的左子的右子节点的数量。
- 在一个节点和它的右子之间的节点的数量等于在节点的右子的左子节点的数目。
- 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:
- 如果一个节点有高度n，则左子具有高度正2，右侧孩子有高度的N-1。
结合这些特性，我们发现，节点的高度的节点n和它的左和右孩子之间的数量等于至F <子> n-1个 - 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.
紧凑型填充算法
基本的解决方案只生产斐波那契树，总是有˚F<子> N + 2 - 1个节点。如果你想生成具有不同数量的节点不平衡的树，同时还最大限度地减少了范围？
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:
- 在序列的端部元件的某些数字将无法插入。
- 在这些元素将创建空白，这些空白的位置，需要跟踪。
- 需要适当减少节点之间的差异。
这里有一个方法，仍然需要的解决方案的递归性优势：
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);
}
}
解析解
如果你看一下每对由碱性溶液中产生的单词之间的差异，你会发现，他们轮流斐波纳契数列的两个连续元素之间。这种交替图案由斐波字的定义：
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;
}
}
这篇关于如何最大限度地产生不平衡的AVL树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
