2

我在自己的代码上用 C++ 实现 AVL 树，但这个问题更多的是关于理解AVL 树而不是代码本身。如果它不适合这里，我很抱歉，但我已经通过互联网爬行，但我仍然没有找到解决我的问题的方法。

我的代码在相对较小的输入（~25-30 位）下按预期工作，所以我想它应该可以工作更多。我正在使用一个数组，在其中保存我在插入期间访问过的节点，然后使用 while 循环我在需要时提高每个节点的高度，我知道当我找到一个高度相等的节点时，这个过程必须结束（他们的减法结果是0就是）。

问题是在平衡方面。虽然我可以找到每个节点的平衡因子并正确平衡树，但我不确定是否应该在平衡后停止调整高度并结束插入循环或继续执行直到条件成立，我只是想不通现在出来了。我知道在删除节点和重新平衡树期间，我应该继续检查，但我不确定插入和平衡。

任何人都可以对此提供任何见解，也许还有一些文档？

4

2 回答 2

0

如果一次只插入一个项目：在插入使其失去平衡后，只需要一次（单次或双次）旋转来重新调整 AVL 树。http://cis.stvincent.edu/html/tutorials/swd/avltrees/avltrees.html知道结论后大概可以自己证明。

于 2012-11-30T09:07:48.213 回答
0

仅供未来读者参考，如果您像我的示例一样实现了二叉树，则无需编辑平衡节点上方的节点高度：

           10
        (1)/ \(2)
         8   16
          (1)/ \(0)
            11 

(Numbers in parenthesis are the height of each sub tree)

假设在上面的树上我们插入一个节点，data=15然后生成的子树如下：

           10
        (1)/ \(2)
         8   16
          (1)/ \(0)
            11
        (0)/  \(1)
              15

请注意尚未编辑子树的先前高度。成功插入后，我们通过插入路径返回，在本例中为(11, 16, 10). 通过这条路径返回后，我们在需要时编辑高度。这意味着16 的子树的左侧高度将为 2，而子树的右侧高度为 0，导致 AVL 树不平衡。用双旋转平衡树后，子树为：

             15
         (1)/  \(1)
           11  16

因此子树的高度最大为 1，就像以前一样，因此该子树根上方的高度没有改变，return现在必须改变高度的函数。

于 2013-01-11T16:07:55.043 回答