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

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

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

我写了一个作为通用排序容器的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
提问于
用户回答回答于

假设:

  • 设U(N)表示高度为n的最大不平衡AVL树中的节点数。
  • U(0)=0
  • U(1)=1
  • U(N)=U(n-1)+U(n-2)+1(n>=2)(即一个根节点加两个最大不平衡子树)
  • 为了方便起见,让我们假设U(n-1)总是左子树,U(n-2)总是右边的。
  • 让每个节点由一个唯一的字符串表示,该字符串表示从根到节点的路径。根节点是空字符串,级别1节点是“L”和“R”,级别2节点是“LL”、“LR”、“RL”和“RR”等等。

结论:

  • U(N)中A级节点的有效字符串是A字符,且满足不等式:n-count(“L”)-2*计数(“R”)>=1
  • 计数(“L”)+计数(“R”)=A或计数(“L”)=A-计数(“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)树,就会得到这个结果。(注意,树左侧的键遵循Fibonacci序列,从1到5,)

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

热门问答

腾讯云 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窗口进入可执行程序所在的目录下,执行命令:...... 展开详请

所属标签

扫码关注云+社区