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

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

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

我写了一个作为通用排序容器的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树,直到给定的高度(必须事先知道),完全避免所有树的旋转。中间树通过选择插入顺序保持AVL平衡。因为它们有两个Fibonacci树的下部的高度,所以它们都是最大不平衡的。

插入是通过在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));
   }

更新

由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的斐波那契树有FH+2-1节点,键值之间没有“洞”,并且具有kmax-kroot=fh+1-1。如果有必要,可以通过偏移根的键值,并在算法中可选择地交换左右键,方便地定位密钥范围。

热门问答

腾讯云广州一区DNS变更,需要怎么操作?

思潮澎湃轻描淡写的生活,但思潮澎湃
推荐
我也收到相关的通知了,这里分享下~ 2019年1月31日,腾讯云将对广州地区旧的基础网络DNS服务器(10.225.30.181、10.225.30.223)进行下线。在此期间,腾讯云提供最新的DNS服务器供您更新使用。 我们建议您尽快将DNS服务器配置进行更新,并且我们为您提供...... 展开详请

快照容量与费用的比例?如何关闭停用?

帅的惊动我国计算机大神
推荐已采纳
快照已于2019年1月22日0时启动正式商业化进程,商业化后所有存量快照和新产生的快照将根据快照使用的存储容量进行收费。 在快照商业化后,腾讯云仍旧会在国内主要地域为用户提供一定量的免费额度。免费额度策略如下: 免费额度覆盖范围为中国大陆地域,中国香港及海外地域暂无免费快照额...... 展开详请

无服务器云函数的cron表达式问题?

腾讯云serverless团队

腾讯云 · 产品团队 (已认证)

腾讯云无服务器云函数SCF产品
推荐
https://cloud.tencent.com/document/product/583/9708#cron-.E8.A1.A8.E8.BE.BE.E5.BC.8F.E8.AF.AD.E6.B3.95.E4.B8.80.EF.BC.88.E6.8E.A8.E8.8D.90.E...... 展开详请

云服务器-intelS2 标准入门型 带独立ip么?

Eli Qiao

腾讯 · 高级工程师 (已认证)

腾讯云CVM后台高级研发工程师
推荐

购买时,可以配置wan网ip,也可以之后添加eip

购买云服务器后上面的是否配套有数据库(mysql, sql server)和Web服务器等?

西风

renzha.net · 站长 (已认证)

www.renzha.net
推荐已采纳

买了服务器自己安装配置数据库即可,也可以另外选购性能更高,更安全可靠的云数据库。

无服务器云函数添加触发方式以错误码9000失败?

腾讯云serverless团队

腾讯云 · 产品团队 (已认证)

腾讯云无服务器云函数SCF产品
推荐

实在抱歉,最近这两天由于广州区 api 网关集群的配置量已超上限,导致 api 网关无法新增服务。目前 api 网关的研发同学已经在紧急扩容广州区集群了。

所属标签

扫码关注云+社区