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

Question

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

Wal*_*oss 21 c algorithm tree avl-tree data-structures

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

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

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

我在寻找整数密钥的(希望简单)序列,在初始为空树T插入时₀,生成AVL树牛逼₀,...,T _ñ这都是最大的未平衡.

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

满足约束的解决方案

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

是优选的,但不是严格要求的.4 n而不是2 n的关键范围可能是合理的目标.

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

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

Answer 1

god*_*el9 8

基本解决方案

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

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

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

如果节点的高度为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);
}

Run Code Online (Sandbox Code Playgroud)

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

紧凑填充算法

基本解决方案只生成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);
    }
}

Run Code Online (Sandbox Code Playgroud)

主循环稍微复杂一些,以适应任意范围的键:

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

Run Code Online (Sandbox Code Playgroud)

封闭式解决方案

如果查看基本解决方案生成的每对单词之间的差异,您会发现它们在Fibonacci序列的两个连续元素之间交替.这种交替模式由Fibonacci字定义:

Fibonacci字是二进制数字的特定序列(或来自任何双字母字母的符号).Fibonacci字是通过重复连接形成的,其方式与通过重复加法形成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);
}

Run Code Online (Sandbox Code Playgroud)

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

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

Run Code Online (Sandbox Code Playgroud)

Answer 2

Wal*_*oss 6

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

我们的想法是生成斐波那契树,直到给定的高度(必须事先知道),完全避免所有的树木旋转.通过选择插入顺序使中间树保持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

Run Code Online (Sandbox Code Playgroud)

这是代码(简化):

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

Run Code Online (Sandbox Code Playgroud)

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

Run Code Online (Sandbox Code Playgroud)

这里是最接近我的版本中的代码(这里有一个静态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);
   }

Run Code Online (Sandbox Code Playgroud)

高度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 ₁} = T ₁到T _{F _H} = T _n,即N =Σh _{= 1 ... H}(F _{h + 2} - 1)= F _{H + 4} - H - 1.但是两个连续的斐波纳契数具有渐近比φ≅1.618,在黄金比例,以使得N/N≅φ ²≅2.618.您可以将其与完全平衡的二叉树进行比较,其中非常类似的公式适用,只有"对数"为2而不是φ.

虽然我怀疑,这将是欢颜摆脱φ的²因素,考虑到当前代码的简单性,它仍然是有趣的要注意以下几点:当你添加高度h的任何中间斐波那契树的"增量"的节点,这个"斐波那契边界"(我的术语)的两个连续键之间的差异是F _{H-h + 3}或F _{H-h + 4},以一种特殊的交替模式.如果我们知道这些差异的生成规则,我们可以简单地用两个嵌套循环填充树.

归档时间：	12 年，1 月前
查看次数：	1910 次
最近记录：	12 年，1 月前