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

Question

我写了一个C language library of AVL trees as general purpose sorted containers .出于测试目的，我希望有一种方法来填充一棵树，使其最大程度地不平衡，即，使其具有与其包含的节点数对应的最大高度。

AVL 树有一个很好的特性，如果从空树开始，按升序(或降序)顺序插入节点，树总是完全平衡的(即，对于给定数量的节点，它具有最小高度) .从空树 T₀ 开始，为每个节点数 n 生成完全平衡的 AVL 树 T_n 的一个整数键序列是

• k₁ = 0
• k_n+1 = k_n+1 ，即 k_n = n-1

我正在寻找一个(希望是简单的)整数键序列，当将其插入最初为空的树 T₀ 时，会生成 AVL 树 T₀, 。 .., T_n 都是最大不平衡的。

我也对只有最后一棵树 T_n 最大程度不平衡的解决方案感兴趣(节点数 n 将是算法的参数)。

满足约束的解

• max(k₁, ..., k_n) - min(k₁, ..., k _n) + 1 ≤ 2 n

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

我无法在 Internet 上找到任何关于通过插入生成最大高度的 AVL 树的信息。当然，我正在寻找的生成树序列将包括所有所谓的 Fibonacci 树，它们是给定深度且节点数最少的 AVL 树。有趣的是，英文维基百科在关于 AVL 树的文章中甚至没有提到斐波那契树(也没有斐波那契数列!)，而德文维基百科有一个很好的article。完全献给他们。但我对我的问题仍然一无所知。

欢迎使用 C 语言的小技巧。

Answer 1

基本解决方案

斐波那契树有几个属性可以用来形成紧凑的斐波那契树:

1. 斐波那契树中的每个节点本身就是一棵斐波那契树。
2. 高度为 n 的斐波那契树中的节点数等于 F_n+2 - 1。
3. 一个节点与其左子节点之间的节点数等于该节点的左子节点的右子节点中的节点数。
4. 一个节点与其右子节点之间的节点数等于该节点右子节点的左子节点中的节点数。

不失一般性，我们假设我们的斐波那契树具有以下附加属性:

1. 如果一个节点的高度为n，那么左 child 的高度为n-2，右 child 的高度为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);
    }
}

封闭式解决方案

如果您查看基本解决方案生成的每对单词之间的差异，您会发现它们在斐波那契数列的两个连续元素之间交替出现。此交替模式由 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.

原来有一个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);
}

您可以使用这个封闭形式的解决方案来解决使用两个嵌套循环的问题:

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