标签: avl-tree

作为程序员,我应该何时考虑使用RB树,B树或AVL树？在决定选择之前需要考虑哪些关键点？

有人可以解释一下每个树形结构的场景,为什么选择其他树木结构参考关键点？

有人可以解释一下这两种数据结构之间的主要区别是什么吗？我一直试图在网上找到一个突出差异/相似之处的来源,但我没有找到任何太丰富的信息.在哪种情况下,一个人比另一个人更受欢迎？什么实际情况使一个"更好"使用比另一个？

给定数据结构规范,例如具有已知复杂性边界的纯函数映射,必须在若干实现之间进行选择.有一些关于如何选择正确的民间传说,例如红黑树被认为通常更快,但AVL树在工作负载上具有更好的性能和许多查找.

1. 是否有关于这种知识的系统性介绍(发表的论文)(与集合/地图相关)？理想情况下,我希望看到对实际软件进行统计分析.例如,它可能得出结论,有N种典型的地图用法,并列出每种地图的输入概率分布.

2. 是否有系统基准测试地图并设置不同输入分布的性能？

3. 是否存在使用自适应算法根据实际使用情况更改表示的实现？

我正在寻找计算AVL树中节点平衡的最佳方法.我以为我有它工作,但经过一些繁重的插入/更新,我可以看到它的工作正常(根本没有).

这是一个由两部分组成的问题,第一部分是如何计算子树的高度,我知道定义"节点的高度是从该节点到叶子的最长向下路径的长度".而我理解它,但我没有实现它.并且为了进一步混淆我这个引用可以在维基百科的树高上找到"传统上,值-1对应于没有节点的子树,而零对应于具有一个节点的子树."

而第二部分是得到一个子树的平衡因素,AVL树,我没有问题理解概念,"让你的高度L和R子树和减去R从L".这被定义为这样的事情:BALANCE = NODE[L][HEIGHT] - NODE[R][HEIGT]

在维基百科上阅读在描述插入到AVL树中的前几行中说:"如果平衡因子变为-1,0或1,那么树仍然是AVL形式,并且不需要旋转."

然后继续说,"如果平衡因子变为2或-2,那么植根于此节点的树是不平衡的,并且需要树旋转.最多需要单次或双次旋转来平衡树." - 我没有抓麻烦.

但是(是的,总有一个但是).

这是令人困惑的地方,文本说明"如果R的平衡因子为1,则意味着插入发生在该节点的(外部)右侧,需要左旋转".但是从理解的角度来看,正如我所引用的那样,如果平衡因素在[-1, 1]那之内,那么就没有必要进行平衡了吗？

我觉得我是如此接近抓概念,我已经得到了树旋转下来,实现正常的二叉搜索树,抓AVL树的边缘,但只是似乎缺少必要的顿悟.

编辑:代码示例比学术公式更受欢迎,因为我总是更容易在代码中掌握一些东西,但是非常感谢任何帮助.

编辑:我希望我能将所有答案都标记为"已接受",但对我而言,NIck的答案是第一个让我走"aha"的答案.

AVL树与B树有何不同？

我正在研究各种树木,并遇到了AVL树木和树木.我想知道

1. AVL树和splay树有什么区别？
2. 我们在什么基础上选择这些发辫？
3. 这些树的积极和消极是什么？
4. 这些树的大O符号表现如何？

所以我自学了AVL树,我理解它背后的基本思想,但我只是想确保我实际实现它的直觉是有效的:

我会用左旋转检查它 -

所以,以下情况很简单:

      8
     / \
    7   10
   /
  6
 /
3

当我们添加3时,树重新平衡为:

    8
   / \
  6   10
 / \
3   7

但轮换是基于3的增加还是根据7的子树的不平衡？它甚至是基于植根于8的树的不平衡吗？

在我看来,以下示例是事情变得有点毛茸茸的地方:

      9
     / \
    7   10
   / \
  6   8
 /
3

因此,在这种情况下,当添加3时,7处的子树很好,因此子树不需要旋转.然而,9处的树是不平衡的,加上3,所以我们将旋转基于9.我们得到:

      7
     / \
    6   9
   /   / \
  3   8   10

因此,在编写我的代码时,我很快就会编写以下代码,从小子树开始,使用更大的子树来完成这个工作？

伪代码:

function balanceTree(Node n){

  if (n is not null){

    balanceTree(n.rightchild);
    balanceTree(n.leftchild);
  }

  if (abs(balanceFactor(n))>1){

    rotateAsNeeded(n);// rotate based on balance factor

  }

}

提前致谢!

假设我有两个AVL树,并且第一个树中的每个元素都小于第二个树中的任何元素.将它们连接成一个单独的AVL树的最有效方法是什么？我到处搜索但没找到任何有用的东西.

我正在阅读Steve Yegge关于单身人士的文章.在其中他提到他的老师告诉他AVL树是邪恶的.只是红色和黑色的树木是更好的解决方案吗？

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