问题标签 [tree-balancing]

我已经用 C++ 中的旧二叉树构建了一个 AVL 树以供练习，但它无法正常工作。我认为它可能没有正确更新节点的高度，但我无法找出问题的根源（我 90% 确定它与辅助函数 getHeight、setHeight、getBalance 有关）。

一些示例测试运行..：

添加 6,3,4 会导致右旋转，它应该会导致 RL 旋转

类似地添加 20,30,25 会导致 LL 旋转，而它应该会导致 LR 旋转

添加 20,30,10,5,6 在应该导致 RL 旋转时会导致两个单独的右旋转

我将不胜感激任何提示/帮助进一步解决这个问题。让我知道我是否可以提供更多信息来提供帮助。

谢谢你。

我在检查给定树是否平衡的天气时感到困惑。为了检查树是否平衡，我们计算 mod（左子树的高度差 - 每个节点的右子树的高度）。
让我们以图中的树为例。youtube讲座中红色节点的差异计算为2。他们说左子树的高度为1，右子树的高度为-1。但到目前为止我所了解的高度是左子树为2，右子树为0

任何人都请帮助我消除这种混乱。

我正在尝试编写这个函数，该函数接受一个 doubleLinkedList 并在适当的位置构造一个平衡的二叉搜索树。TreeNode.left 相当于前一个指针，TreeNode.right 相当于下一个指针。我从这里的程序中获得灵感，但这不起作用：

http://www.geeksforgeeks.org/in-place-conversion-of-sorted-dll-to-balanced-bst/

我周二有期中考试，无法理解红黑树。我怎么知道树是平衡的？我知道这与正确数量的黑色节点和黑色深度有关。但我不太明白。我需要知道这一点，因为您将树旋转基于此。如果有人可以提供一步一步的解释，那就太好了。谢谢！

本练习要求学生从 AVL 树中删除一个节点。在这种情况下，这需要一些平衡，因为最深和最浅深度之间的差异> 1。但是平衡应该发生在删除之前还是之后？还是没关系？

有问题的 AVL 树的图像

我正在研究一个 BST，它将根据节点的命中及其元素平衡节点，其中命中是一个属性，当使用 find()、contains() 等找到节点时该属性会增加。树的根是节点具有最高的点击次数。我所有的代码都很好，除了在我增加命中后平衡树的平衡方法。我正在使用修改后的 AVL 树旋转方法（https://users.cs.fiu.edu/~weiss/dsj2/code/weiss/nonstandard/Rotations.java），我不比较元素，而是比较一个节点。无论我尝试什么，我都无法让它工作，我无法让树正确平衡这是我到目前为止的代码：

现在 balance 方法只是删除了它应该旋转的节点，我尝试调试它但看不出有什么问题。

我不知道我在哪里遇到问题，但我在 AVL 实现中遇到了一个奇怪的错误，翻译成MQL4/MQL5语言。

在失败的情况下，我正在进入

• 递归指向同一个节点问题

或者

• 没有任何父节点的分离节点，

因此在平衡时，我遇到了空指针问题。

测试用例：

下面附上MetaTrader4/5 终端 [日志]的副本/粘贴

通过案例：

失败案例：

这是MQL4/MQL5代码，但语言或多或少反映了 CPP。

Cpp 和头文件的来源：

根据要求提供更多详细信息： 测试 MQL 脚本：

终端输出：

我在处理平衡 AVL 树问题时遇到了麻烦，因为我的解决方案似乎与教科书后面的解决方案相冲突。我查看了 AVL 树的在线可视化，他们认为我的是正确的。我的课本错了吗？

这是树：

然后我必须将 65 插入到这个 AVL 树中。这会导致不平衡，据我了解，需要左右旋转。

这是我想出的，并已通过http://robinsswei.github.io/VisGraphs/avltree.html确认：

这是我的教科书所说的正确答案：

哪一个是正确答案？

例如，如果我们在一个左分支上按降序排列的值为 10、9 ... 1 的节点，我们如何在树上执行旋转以使其成为平衡的 AVL 树？我正在考虑重复单次右转，但有人可以在这里显示步骤顺序吗？

我想知道AVL 树或红黑树平衡方法（通过简单旋转在每个节点插入时发生）是否可以在二叉树构造的任何阶段扩展到任何给定的二叉树。

我发现，对于任何给定的不平衡二叉树，遵循 AVL 或红黑旋转规则会导致出现平局，在这种情况下，您可以选择至少两种方式来平衡树。如果您遵循 AVL 规则，您将获得相同的级别差异，这意味着您可以选择至少两个节点来平衡树。

显然，您为平衡所做的任何决定都会导致不同的平衡树（也许其中一个在级别差异方面的情况更好）。我在一个简单的例子上测试了这个过程，我不确定它是否适用于所有情况，所以我想知道：

1. 如果可以概括
2. 如果有一个例子证明它不能被推广？

为什么还要考虑这种情况？

1. 知道很有趣！
2. 假设一个二叉树数据结构（并且您不想使用 AVL 或红黑）。所以你不想一直保持平衡，但有时你可能想在树的构建过程中保持平衡。

一个简单的例子：

• 假设我们的元素由 {1, 3, 5, 7}
• RR：向右旋转
• RL：向左旋转

给定的二叉树如下所示：

如果你将它与 RR (pivot 5) 然后 RL (pivot 3) 平衡，它将如下所示（如果从一开始就使用 AVL 方法，则使用相同的树）：

如果您将其与 LL（枢轴点 5）平衡：