如何生成最大不平衡的AVL树

我编写了一个AVL树的C语言库作为通用分类容器 。 出于测试目的，我希望有一种方法来填充树，使其最大程度地不平衡，即，使其具有包含的节点数的最大高度。

AVL树具有很好的属性，如果从空树开始，按升序（或降序）顺序插入节点，则树始终是完全平衡的（即，对于给定数量的节点，它具有其最小高度）。 从空树T ₀开始，为每个节点数n生成精确平衡的AVL树T _n的一个整数键序列就是简单的

• k ₁ = 0
• k _{n + 1} = k _n +1，即k _n = n-1

我正在寻找一个（希望很简单的）整数键序列，当插入最初空的树T _0时 ，生成最大不平衡的AVL树T ₀ ，…，T _n 。

我也感兴趣的是一种解决方案，其中只有最后一棵树T _n最大程度地不平衡（节点数n将是算法的参数）。

满足约束的解决方案

• max（k ₁ ，…，k _n ） – min（k ₁ ，…，k _n ）+1≤2n

是可取的，但不是严格要求的。 4 n而不是2 n的关键范围可能是合理的目标。

我无法在互联网上找到关于通过插入生成最大高度的AVL树的任何内容。 当然，我正在寻找的生成树的序列将包括所有所谓的Fibonacci树，它们是具有最小节点数的给定深度的AVL树。 有趣的是，英语维基百科甚至没有在AVL树的文章中提到斐波那契树（也不是斐波那契数字！），而德语维基百科有一篇非常好的文章完全致力于它们。 但对于我的问题，我仍然处于黑暗中。

C语言有点刺耳的黑客是受欢迎的。

Answer 1

基本解决方案

Fibonacci树有几个属性可用于形成一个紧凑的Fibonacci树：

1. Fibonacci树中的每个节点本身都是斐波纳契树。
2. 高度为n的Fibonacci树中的节点数等于F _{n + 2} – 1。
3. 节点与其左子节点之间的节点数等于节点左子节点右子节点中的节点数。
4. 节点与其右子节点之间的节点数等于节点右子节点左子节点中的节点数。

在不失一般性的情况下，我们假设我们的Fibonacci树具有以下附加属性：

1. 如果节点的高度为n，则左子节点的高度为n-2，右子节点的高度为n-1。

结合这些属性，我们发现高度为n的节点与其左右子节点之间的节点数等于F _n-1 – 1，我们可以使用这个事实生成一个紧凑的Fibonacci树：

 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); } 

该算法为给定高度生成可能的最小节点数，并且还生成最小可能范围。 您可以通过使根节点不为零来改变范围。

紧凑填充算法

基本解决方案只生成Fibonacci树，它总是有F _{n +} 2-1节点。 如果要生成具有不同节点数的不平衡树，同时仍然最小化范围，该怎么办？

在这种情况下，您需要生成下一个更大的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字定义：

Fibonacci字是二进制数字的特定序列（或来自任何双字母字母的符号）。 Fibonacci字是通过重复连接形成的，其方式与通过重复加法形成Fibonacci数相同。

事实certificate，Fibonacci这个词有一个封闭forms的解决方案 ：

 static double phi = (1.0 + sqrt(5.0)) / 2.0; bool fibWord(int n) { return 2 + floor(n * phi) - floor((n + 1) * phi); } 

您可以使用此封闭forms的解决方案来使用两个嵌套循环来解决问题：

 // 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; } } 

Answer 2

我已经找到了我的问题的答案，但我仍然希望能找到一个更简单，特别是更节省时间且不太节省空间的算法，希望它具有更好的键范围属性。

我们的想法是生成斐波纳契树，直到给定的高度（必须事先知道），完全避免所有的树木旋转。 通过选择插入顺序使中间树保持AVL平衡。 由于它们具有它们连接的两个斐波那契树中较低的高度，因此它们都是最大不平衡的。

通过虚拟插入Fibonacci树序列中的所有节点来完成插入，但是，对于每个虚拟树，仅有效地插入高度为1的子树的节点。这些是两个连续斐波纳契树之间的“增量”节点。

以下是max_height = 5的情况：

 insert 0 => Fibonacci tree of height 1 (1 node): 0 insert 8 => Fibonacci tree of height 2 (2 nodes): 0 8 insert -8 insert 12 => Fibonacci tree of height 3 (4 nodes): 0 -8 8 12 insert -4 insert 4 insert 14 => Fibonacci tree of height 4 (7 nodes): 0 -8 8 -4 4 12 14 insert -12 insert -2 insert 6 insert 10 insert 15 => Fibonacci tree of height 5 (12 nodes): 0 -8 8 -12 -4 4 12 -2 6 10 14 15 

这是代码（简化）：

 void fibonacci_subtree(int root, int height, int child_delta) { if (height == 1) { insert_into_tree(root); } else if (height == 2) { insert_into_tree(root + child_delta); } else if (height >= 3) { fibonacci_subtree(root - child_delta, height - 2, child_delta >> 1); fibonacci_subtree(root + child_delta, height - 1, child_delta >> 1); } } ... for (height = 1; height <= max_height; height++) { fibonacci_subtree(0, height, 1 << (max_height - 2)); } 

UPDATE

godel9的解决方案解决了该解决方案的密钥传播问题。 这是godel9代码的输出：

 insert 0 => Fibonacci tree of height 1 (1 node): 0 insert 3 => Fibonacci tree of height 2 (2 nodes): 0 3 insert -3 insert 5 => Fibonacci tree of height 3 (4 nodes): 0 -3 3 5 insert -2 insert 1 insert 6 => Fibonacci tree of height 4 (7 nodes): 0 -3 3 -2 1 5 6 insert -4 insert -1 insert 2 insert 4 insert 7 => Fibonacci tree of height 5 (12 nodes): 0 -3 3 -4 -2 1 5 -1 2 4 6 7 

这里是最接近我的版本中的代码（这里有一个静态的fibs数组）：

 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); } 

高度H的最终Fibonacci树具有F _{H + 2} - 1个节点，在键值之间没有“孔”，并且具有k _max - k _root = F _{H + 1} - 1.如果需要，可以方便地定位键范围，通过偏移根的键值，并可选地在算法中左右交换。

仍然未解决的是使用整数键紧凑填充任何给定的键范围（虽然对于完全平衡的树来说它是微不足道的）。 使用这种算法，如果你想用n个节点（带整数键）制作一个最大不平衡树，其中n不是斐波纳契数 - 1，你想要更小的键范围，你可以找到第一个高度可以容纳n个节点，然后运行该高度的算法，但是在插入n个节点时停止。 将保留许多“孔”（在最坏的情况下，大约为n /φ≅n/ 1.618）。

与我在撰写此解决方案的介绍时的直观理解相反，此算法的时间效率（无论是否有godel9的重要改进）已经是最优的，因为它是O（n）（因此当包含插入时，它变成O（n log n））。 这是因为操作次数与所有Fibonacci树的节点之和成比例，从T _{F 1} = T ₁到T _{F H} = T _n ，即N =Σh _{= 1 ... H} （F _{h + 2} - 1）= F _{H + 4} - H - 1.但是两个连续的Fibonacci数具有渐近比φ≅1.618， 黄金比率 ，因此N /n≅φ2≅2.618。 您可以将此与完全平衡的二叉树进行比较，其中非常类似的公式适用，只有“对数”为2而不是φ。

虽然我怀疑摆脱φ2因素是值得的，考虑到当前代码的简单性，但仍然有趣的是注意以下内容：当你添加高度为h的任何中间Fibonacci树的“增量”节点时，这个“斐波那契边界”（我的术语）的两个连续键之间的差异是F _{H-h + 3}或F _{H-h + 4} ，以一种特殊的交替模式。 如果我们知道这些差异的生成规则，我们可以简单地用两个嵌套循环填充树。

Answer 3

有趣的问题。 看起来你已经有了一个很好的解决方案，但我会发现更容易组合的方法。

假设：

• 设U（n）表示高度为n的最大不平衡AVL树中的节点数。

• U（0）= 0

• U（1）= 1

• 对于n> = 2，U（n）= U（n-1）+ U（n-2）+ 1（即，根节点加上两个最大不平衡子树）

• 为方便起见，我们假设U（n-1）始终是左子树，U（n-2）总是正确的。

• 让每个节点由表示从根到节点的路径的唯一字符串表示。 根节点是emptry字符串，1级节点是“L”和“R”，2级节点是“LL”，“LR”，“RL”和“RR”等。

结论：

• U（n）中A级节点的有效字符串是A个字符长且满足不等式：n – count（“L”） – 2 * count（“R”）> = 1

• count（“L”）+ count（“R”）= A或count（“L”）= A – count（“R”）

• 因此计数（“R”）<= n - A - 1

• 我们可以使用以下函数生成给定级别的所有有效路径，并确定每个节点的键值。

   void GeneratePaths(int height, int level) { int rLimit = height - level - 1; GeneratePaths(height, rLimit, level, string.Empty, 0); } void GeneratePaths(int height, int rLimit, int level, string prefix, int prefixlen) { if (prefixlen + 1 < level) { GeneratePaths(height, rLimit, level, prefix + "L", prefixlen + 1); if (rLimit > 0) GeneratePaths(height, rLimit - 1, level, prefix + "R", prefixlen + 1); } else if (prefixlen + 1 == level) { InsertNode(prefix + "L", height) if (rLimit > 0) InsertNode(prefix + "R", height); } } void InsertNode(string path, int height) { int key = fibonacci(height); int index = height - 2; for (int i=0; i < path.length(), i++) { int difference = fibonacci(index); char c = path.charAt(i); if (c == 'L') { key -= difference; index -= 1; } else if (c == 'R') { key += difference; index -= 2; } } InsertKey(key); } 

如果使用这些函数生成U（5）树，则会得到此结果。 （请注意，树左边的键遵循从1到5的斐波纳契数列，）

  5 3 7 2 4 6 8 1 3 4 6 1