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

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (3)
  • 关注 (0)
  • 查看 (89)

我写了一个作为通用排序容器的AVL树的C语言库为了测试,我想要有一种方法来填充一棵树,使它最大程度地不平衡,也就是说,它包含的节点数有最大的高度。

AVL树具有这样的优点:如果从空树开始,按升序(或降序)插入节点,则树总是完全平衡的(也就是说,对于给定的节点数,树有其最小高度)。从空树T0开始,为每个节点n生成精确平衡的AVL树TN的整数键序列是简单的。

  • K1=0
  • Kn+1=kn+1,即kn=n-1

我正在寻找一个(希望是简单的)整数键序列,当插入到最初的空树T0中时,生成的AVL树T0,...,TN都是最大的联合国平衡。

我也会对一个解感兴趣,其中只有最后一棵树TN是最大不平衡的(节点数n将是算法的一个参数)。

满足约束条件的解

  • 最大(K1,...,kn)-min(K1,...,kn)+1≤2n
提问于
用户回答回答于

基本解

Fibonacci树有几个属性,可以用来形成紧凑的Fibonacci树:

  1. Fibonacci树中的每个节点本身就是Fibonacci树。
  2. 高度为n的Fibonacci树的节点数等于fn+2-1.
  3. 节点与其左子节点之间的节点数等于节点的左子节点的右子节点数。
  4. 节点与其右子节点之间的节点数等于该节点的右子节点的左子节点数。

在不失去通用性的情况下,我们将假设Fibonacci树具有以下附加属性:

  1. 如果节点的高度为n,则左子具有n-2,右子具有高度n-1。结合这些性质,我们发现在n高的节点与其左、右子节点之间的节点数等于FN-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树,它总是有fn+2-1节点.。如果想要生成一个具有不同节点数的不平衡树,同时仍然最小化范围,那该怎么办?在这种情况下,需要生成下一个更大的Fibonacci树,只需做一些修改:
  2. 序列末尾的一些元素将不会被插入。
  3. 这些因素将造成差距,需要跟踪这些差距的位置。
  4. 节点之间的差异需要适当地缩小。

这里有一种方法仍然利用了解决方案的递归特性:

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

热门问答

腾讯云 COS 怎么才能外链调用 m3u8 到别的网站播放?

滑稽园扛把子

Swoole · PHP开发工程师 (已认证)

As a PHP Developer
推荐
设置公有读私有写:当访问对象时,COS 读取到对象的权限为公有读,此时无论存储桶为何种权限,对象都可以被直接下载 设置步骤 登录 对象存储控制台,选择左侧菜单栏【存储桶列表】,进入存储桶列表页面。单击需要修改对象权限的对应存储桶,进入存储桶。 📷 找到需要设置权限的对象(如 e...... 展开详请

Ubuntu搭建的WordPress如何修改php.ini?

滑稽园扛把子

Swoole · PHP开发工程师 (已认证)

As a PHP Developer
推荐
php新手很多不知道怎么查配置文件在哪,这里提供一个很简单的方法 使用 php -i 命令可以打印php的详细信息,可以把这堆东西输出一下 php -i > outputphp.txt,结合 grep 查找命令 php -i| grep php.ini 打印结果如下 Config...... 展开详请

归档存储采用的存储介质是什么, 安全可靠吗?

滑稽园扛把子

Swoole · PHP开发工程师 (已认证)

As a PHP Developer
推荐
归档存储主要是针对海量、重要且访问频率极低的非结构化数据进行长期的归档保存和备份管理。 在数据安全层面,归档存储提供数据锁定机制,防止数据被修改和删除,保障数据安全。 技术架构: image.png 与对象存储的差异 归档存储 CAS 是一项离线存储服务,不同于在线的对象存储 ...... 展开详请

在按官网手册排错后依然提示1004错误?

看你的代码好像是短信相关的代码,1004错误代表请求包解析失败,通常情况下是由于没有遵守 API 接口说明规范导致的。 建议您通过以下方式定位解决: 首先,要确认发送的请求是否是标准的 json 格式; 第二,检查是否有将单引号当做双引号使用(json 标准应该是双引号); 第...... 展开详请

redis数据库应该怎样连接???

滑稽园扛把子

Swoole · PHP开发工程师 (已认证)

As a PHP Developer
推荐
实例初始化完成后,连接腾讯云Redis时,需要输入设置的密码。主从版和集群版的连接示例如下 主从版连接示例 主从版支持2种格式 • 格式1,“实例id:密码”的格式类型,例如您的实例id是crs-bkuza6i3,设置的密码是abcd1234,则连接命令如下 redis-cli ...... 展开详请

如何使用holer实现从外网访问本地WEB应用?

Dingda

Dingda · 站长 (已认证)

多一些不为什么的坚持
推荐
解压holer软件 获取holer access key信息: 在holer官网上申请专属的holer access key或者使用开源社区上公开的access key信息。 启动holer服务: Windows系统平台: 打开CMD窗口进入可执行程序所在的目录下,执行命令:...... 展开详请

所属标签

扫码关注云+社区