问题标签 [avl-tree]

我想在不使用任何递归过程的情况下计算 avl 树中节点的平衡因子。我怎样才能做到这一点？请告诉我方法或提供 C++ 代码片段。

我正在向您发布使用我开发的AVL 树的代码。插入的方法，avlinsert方法如下。我在纸上开发了这段代码，它没有经过测试，但我希望这能奏效。我要讨论的主要问题是节点的平衡因子首先看代码。通过这种方式，这个想法将变得清晰，我想问什么。所以这里是代码：

这不是全部代码，但足以向您展示我正在尝试做的事情。您已经在这段代码中看到我在插入期间设置节点的平衡因子（第二个 while 循环块）。好的，这很好。但是在插入之后，我需要执行旋转。我也有旋转代码，但主要问题是当节点旋转时，我需要重置旋转代码中节点的平衡因子。这就是我的问题。我该怎么做？代码片段是什么？

要计算 AVL 树中节点的平衡因子，我们需要找到其左子树的高度和其右子树的高度。然后我们用左子树的高度减去右子树的高度：

balancefactor = leftsubtreeheigh - rightsubtreeheight

我的问题是：如何计算左子树或右子树的高度？

例如，在给定的图^₁中，根节点 40 的左子树的高度为 4，而 40 的右子树的高度为 2，因此高度差为 2。

我如何在 C++ 中做到这一点？我不想使用递归，因为它非常令人困惑。使用显式堆栈而不是递归更容易理解。

^₁ 该图已从 imgur 服务器中删除。

我正在处理一项要求我实现 AVL 树的任务。我很确定我的轮换方法是正确的，但我无法确定何时使用它们。

例如，书中的解释说我应该爬上与插入节点/元素相同的路径。但是，我不能有任何父指针。

最新代码：

我在这里要做的是爬回树上，但它只能在插入节点后检查平衡。因此，这在 else 子句中。

我还尝试将余额代码放在 R Samuel Klatchko 建议的位置，但检查了每个插件的余额。例如：如果连续插入 7、9、5、3 和 1，尝试插入 1 时会出现空指针异常。

编辑：上述的一个原因可能与我做高度的方式有关。如果我每次都用 height() 计算高度，但它会破坏 AVL 树的 O(log(n)) 时间，那么它在一次右旋转时效果很好。

关于如何做到这一点的任何想法？

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

我对这个非常简单的代码块有疑问。请给我你的建议。 （我的这个问题解决了，在解决这个问题时，id stakx 的人真的帮了我，唯一的问题是我在使用堆栈<treeNode>，当我仔细看到堆栈的推送方法时，有一个复制过程当我写 head->object=number 时，所以最后我做了一个指针堆栈，就像这个堆栈<treeNode*>，它确实解决了问题，我现在没有问题，我非常非常感谢 stakx 人。）

在代码之前，您需要提供以下树

替代文本 http://img44.imageshack.us/img44/7016/avlimage06.jpg
，如图所示，根为 8，堆栈有两个节点，即 6 和 4。我将此堆栈和根节点传递给以下代码

该函数的输出由下式给出

这是我正在使用的堆栈的 pop 方法的代码

这是堆栈的push方法的代码

BBTHMNN(h) = 平衡二叉树的节点数最少

BBTHMNN(h) = BBTHMNN(h-1) + BBTHMNN(h-2) + 1

满足上式的平衡二叉树的名称。我在互联网上搜索过，但我找不到树的名字

下面的代码几乎可以完美运行，但是 9 和 7 的孩子直接垂下而不是作为左孩子。我该如何纠正？

谢谢，CB

我想让我的avl-tree支持重复键，但是具有重复项的默认行为存在问题，binary search tree即旋转可以使具有相同键的节点位于父级的左侧和右侧。

例如，当添加三个节点都带有键 A 时，会导致树进行旋转，如下所示：

因此，使用该键获取所有条目将是一个问题……并且双向搜索并不好。

我想到的解决方案是让每个节点存储一个重复的数组，所以当添加一个已经存在的新项目时，只需向数组中添加一个新项目，使用键删除项目将删除整个节点，同时查找所有项目with key 将返回该数组。

是否有任何其他方法来处理重复？

插入项需要一个键和一个值..所以我需要存储值以便通过 findAll 使用某些键方法返回它们。

我目前正在做一个需要使用 AVL 树的项目，我为 avl 编写的插入函数似乎不起作用，它最多适用于 3 或 4 个节点；

我非常感谢您的帮助尝试如下