问题标签 [tree-balancing]

这是我认为应该如何完成的（在阅读了 DS Malik 的“使用 C++ 的数据结构”第 652 页后）。我们从其父节点开始遍历通往已删除叶子的路径。P对于这条路径上的每个节点，我们执行下面介绍的操作。假设删除缩短了 的较短子树，P并且Q是 的较高子树的根P。让bf()表示 balance_factor。

1. 如果|bf(P)|>1和bf(Q) = 0，则旋转P

2. 如果|bf(P)|>1和 与bf(Q)具有相同的符号bf(P)，则旋转P

3. 如果|bf(P)|>1和 与bf(Q)有相反的符号bf(P)，则先旋转Q，然后旋转P（即使在Q旋转之后bf(P) = 0）

4. 如果|bf(P)|<2, 则什么都不做P并继续P' 的父级

这个对吗？

所以我很难理解如何平衡 AVL 树。我了解旋转的东西，但我不知道如何找到节点高度的平衡因子，例如：

http://i.imgur.com/yh5zNIl.png

谁能向我解释一下我们实际上是如何找到每个节点的平衡因子的？

我知道 [(left subtree) - (right subtree)] 的高度是否不在 (-1<= x <= 1) 范围内，那么它不平衡......但我不知道如何找到“x”。

（编辑：我不需要代码，我只想了解如何找到BF）。

我有一个 BST 和 2 个队列。为了在尽可能短的时间内插入和删除，我需要经常平衡我的树。为此，我使用 DSW 算法。

我已经实现了这一切，一切都很好。我的问题是我不知道平衡树的最佳时间是什么时候。

我已经尝试寻找关于此的论文和任何类型的信息，但我找不到任何信息。

我基本上需要知道什么时候平衡树是最佳的，这样它不会经常花费太多时间，但它通常足以让我的插入和删除时间不会花费很长时间。所以最终总运行时间尽可能短。

有任何想法吗？

段树中的操作复杂度等于O(logn)，在此基础上我们可以说任何段树都是平衡的吗？

假设我有一个 AVL 树，它的节点将自己的平衡因子存储为单个整数。

如果我知道它的左右子节点的平衡因子，我如何计算节点 N 的平衡因子。

请注意，我没有rHeight 和 lHeight，所以bal(N) = lHeight - rHeight不是一个选项。

是否可以强制Boost.Spirit Qi以这种方式运行，生成的语法可以根据一些运行时可计算的条件/规则/速率进行调整？例如，输入由语言结构组成，这些结构在解析过程中会导致不同的选择，一些更频繁，另一些 - 更少。但是替代的顺序会影响效率，即语法的运行时最优性。在某些情况下，在任意输入（可能是强聚类的）的情况下，不可能提前确定更频繁地选择哪个替代方案。

我知道可以qi::symbols在运行时附加符号，但是对于其他一些解析器来说类似的行为是可取的。

我一直在使用代码来实现插入到 AVL 平衡二叉树中，该二叉树将用于大型项目。我选择了 AVL 而不是红黑和其他平衡方法，因为它简单，因为我需要确信它是正确的。我的测试代码工作正常 - 但是我被引导相信可以使用可变余额限制/容差。我还没有看到这是作为 AVL 的一部分实现的，是的，我真的不需要它，但作为调试的一部分，我测试过它失败了。看起来更高的平衡限制可能需要在经过一些旋转后向上传播树以降低树的高度。

有没有其他人成功尝试过可变余额限制？注意：如果可以的话，我不想走树来重新计算平衡因子。在这个阶段，除非有人有一些有用的想法，否则我可能只会坚持 1 的余额限制。

在下面的测试代码中，如果 BALANCELIMIT 为 1，则所有似乎都有效 - 但如果更高则无效

我有以下理论问题：
我在 3 维空间中有 n 个长方体。它们与坐标系对齐，因此可以通过点 (x,y,z) 和尺寸 (dimX,dimY,dimZ) 来描述一个长方体。我想以一种能够检查新插入的长方体是否与现有长方体（碰撞检测）相交的方式组织这些长方体。为此，我决定使用分层边界框。所以总而言之，我有一个边界体积的二叉树结构。然后通过递归确定到两个孩子的距离（=两个长方体的两个中心之间的距离）并插入距离最小的路径来完成插入。碰撞检测的工作原理类似，但我们采用与给定长方体相交的子路径中的所有边界体积。
棘手的部分是，如果一些长方体彼此非常接近而其他长方体相距很远，如何平衡这棵树以获得更好的性能。到目前为止，我还没有找到使用例如 AVL-tree 的方法，因为这样我就必须能够以某种方式比较两个长方体，而不会破坏碰撞检测所依赖的条件。
PS：我知道有库可以做到这一点，但我想详细了解碰撞检测的原理，例如在游戏中，因此想自己实现。

假设我有一个不平衡的 BST。BST 存储在数组中，其中索引 0 处，索引kroot上节点的左右子节点分别位于索引2k和2k + 1上。例如一棵树：

将存储在数组中[5, 3, nil, 2, 4, nil, nil, 1, nil, ...]，我想对其进行平衡，以使结果搜索树的最大高度最小（=没有超过存储数据所需的级别）。
例如，它可能是一棵树，其中数组中的值之间没有间隙，并且所有 nil 值都被“推”到后面（注意：这个树定义实际上比我在上一段中的目标更具限制性）。例如上面[4, 2, 5, 1, 3, nil, ...]。
有没有这样的算法？如果没有，是否有类似的算法平衡树至少“好”。

附加信息：
- 算法需要就地，只允许 O(1) 额外内存-这个
问题 中提到了一个算法，但是它依赖于交换指针（数组需要 2^n 大）
- 有一个非常相似的问题，遗憾的是，接受的答案只是关于树木的一般性讨论。（我没有 AVL 平衡树的元数据，是吗？如果我错了，请证明我错了）
- 可接受的答案也可以是没有这样的算法，如果是这种情况，请提供一些参考资料/证明或逻辑假设

我正在尝试编写代码来创建 AVL 平衡二叉树。目的是每次插入新节点时都要旋转子树以保持（AVL）平衡。

（一个节点的左子树的所有值都必须小于这个节点的值；一个节点的右子树的所有值都必须高于这个节点的值）

我刚刚编写的代码适用于以特定顺序插入的数字，但不适用于其他顺序。例如，以下输入工作正常：

这个不会：

为什么？