问题标签 [tree-balancing]

好吧，这里有很多代码，但我认为最好以防万一某些东西在我的逻辑中没有立即显现出来。

我的问题从高度和我计算的平衡因子开始。我查阅了无数的 AVL-tree 算法，并在纸上做了很多粗略的工作，试图找出解决这棵树的野兽平衡方面的最佳方法。这是我必须要做的：

i̶d̶o̶e̶n̶o̶t̶ . 我的树唯一不正确的是任何给定节点的频率偏离了 1-3 个元素，并且高度不是所有元素的应有高度。

我很确定在调试时它与我的平衡算法有关，因为一方面我的高度完全偏离（我相信高达 7）并且我大约 70% 的节点具有正确的计数（频率） .

我的大问题：我的平衡逻辑和/或旋转逻辑有什么问题？我的整个代码是错误的，还是我至少在正确的轨道上？

**当我取出我段错误所在的节点时，由于某些上帝遗弃的原因更新了代码后，整个程序都可以工作，但仍然给我错误的频率：/

所以从字面上看，1个元素/节点会造成这个段错误，但它仍然是错误的......

示例输入->

是O(1)还是O(logN)但系数较小？

如果未指定，我至少想知道答案是基于一个合理的假设，即地图/集合是使用红黑或 AVL 树实现的。我认为插入元素的一般算法类似于：

• 找到正确的地方 - O(logN)
• 做实际插入 - ？
• 如有必要，重新平衡树 - ？

现在，如果我们提供正确的迭代器提示，那么第一步就变成了O(1)。其他步骤也是O(1)还是O(logN)？

B 树是类似于 AVL 树的自平衡树。在这里，我们可以看到如何使用左右旋转来保持 AVL 树的平衡。

这里是一个解释插入 B 树的链接。如果我没记错的话，这种插入技术不涉及任何旋转，以保持树平衡。因此它看起来更简单。

问题：是否有任何类似的（或任何其他不使用旋转的技术）来保持 avl 树的平衡？

我目前有一个排序的链表，并且使用void返回方法，我需要从列表中递归构造一个平衡的二叉搜索树（称为第二个参数）。作为参数，我只能有 LL Head、正在创建的根和列表的长度。

该方法不会对 LL 造成破坏，然后为了测试树，我有一个 printTree 和一个 treeDepth：

我想知道 AVL 树重新平衡是否存在根本问题。根据几个教程，对于 AVL 插入，最多 2 次旋转它可以平衡。但是，这可能取决于所谓的平衡。按照链接查看树。

最初它有6个元素。假设我们将最后一个值插入为 3 或 4.5 或 5.5 或 6.5。无论如何，它将被插入底部的左侧。总共有 7 个元素树，为了完美平衡，我认为它只有 3 行。

这将强制新根为 6 或 6.5（如果我们插入 6.5）。我真的想不出一种在 2 次旋转内重新平衡它的方法。如果我们只依赖“平衡”的定义，4-rows 仍然被称为平衡，但它会导致更多的搜索时间。

我错过了什么吗？

如果图片被删除，下面是文字版本：

换句话说，如果您要在插入后立即从左到右读取红黑树中叶子的值，那么在对树执行平衡操作后，该顺序是否保持不变？

有没有办法转换它，以便它根据高度检查平衡？（假设这就是问题所在。）

例如：

我正在尝试解决以下问题：“给定一个具有唯一整数元素的排序（递增顺序）数组，编写一个算法来创建一个高度最小的 BST。”

给定的答案将根节点作为数组的中间。虽然这样做对我来说很直观，但我试图严格地证明，让根节点位于数组的中间总是最好的。

书中给出的理由是：“要创建最小高度的树，我们需要将左子树中的节点数与右子树中的节点数尽可能匹配。这意味着我们想要根节点成为数组的中间，因为这意味着一半的元素会小于根，而一半的元素会更大。”

我想问：

1. 为什么任何最小高度的树都是左子树中的节点数与右子树中的节点数尽可能相等的树？（或者，你有没有其他方法可以证明最好让根节点位于数组的中间？）

2. 最小高度的树是否与平衡的树相同？从上一个关于 SO 的问题中，这就是我得到的印象，（可视化平衡树）但我很困惑，因为这本书特别指出“具有最小高度的 BST”，而从未“平衡 BST”。

谢谢。

资料来源：破解编码采访

LeetCode有问题。我使用一个简单的递归解决方案来解决它，但是运行时间很长，为 170 毫秒。然后我找到了一个类似的解决方案，它也是递归的，它的运行时间只有大约 10 毫秒。为什么？

我的解决方案：

我找到的快速解决方案：

谢谢！

我正在解决“Cracking the Coding Interview”中的以下问题：实现一个函数来检查二叉树是否平衡。平衡树是这样一棵树，使得任何节点的两个子树的高度都不会相差超过 1。

本书的示例解决方案（复制如下）假设从节点发出的树是平衡的，如果（a）节点的左子树和右子树是平衡的；(b) 节点本身是平衡的。我试图理解为什么会这样？上述两个条件的满足如何证明从节点发出的整棵树是平衡的？

谢谢