相关疑难解决方法(0)

我编写了一个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语言有点刺耳的黑客是受欢迎的.