问题标签 [tree-balancing]

我有一棵大树，随着算法的进展而增长。每个节点都包含集合，我想它是作为平衡二叉搜索树实现的。每个节点的集合在该节点创建之后，在用于创建该节点的子节点之前应保持固定。

然而，我担心复制每套产品的成本过高。相反，我希望每个新创建的节点集都利用父节点集的所有适当部分。简而言之，我很高兴复制集合的 O(log n) 而不是 O(n)。

是否有任何 STL 关联数据结构的变体提供这种部分复制优化？也许在 Boost 中？当然，这样的数据结构在 Haskell 或 OCaML 中实现起来很简单，但在 C++ 中需要更多的努力。

我正在构建一个递归 Java 方法来平衡使用每个节点中的权重的二叉搜索树（使用整数，但设计为通用）。出于我的目的，节点的权重定义为子节点数 + 1。

在平衡结束时，任何节点的值都应该是以该节点为根的子树中所有节点的值的中值。

这是我的代码：

我正在尝试修改树而不返回任何内容，但代码不会更改树。我知道我在某处通过引用传递和按值传递搞砸了，但我不知道在哪里 - 任何人都可以帮忙吗？我花了几个小时调试，但在调试递归时我真的很困惑。

我不太明白为什么 splay 树数据结构中的旋转不仅考虑了评级节点的父节点，还考虑了祖父节点（之字形和之字形操作）。为什么以下不起作用：

例如，当我们向树中插入一个新节点时，我们检查是插入左子树还是右子树。如果我们插入到左边，我们将结果向右旋转，右子树反之亦然。递归它会是这样的

那应该避免整个“张开”过程，你不觉得吗？

我的树的平衡部分遇到了问题。我在递归插入后调用了 checkBal。如果我尝试添加 5、2 和 4，它会检查 2 的平衡并继续回到 5，然后进入右旋转的 rotateLeft 部分，这是正确的。但是第二行的 rotateLeft 函数出错。

这个实现有什么问题？我到处搜索并将我所做的与人们谈论它是如何完成的方式进行比较。我终于让一切正常了。最后我忘记将 N 设置为 K 了。

如果树是 AVL 树或不使用 prolog，我正在尝试实现测试。

我做了一个高度测试，适用于我迄今为止所做的测试，但我的平衡测试仍然不强。

这是我到目前为止的工作：

我基于旧的 stackoverflow 代码中的代码。但它并不适用于所有情况。将包括我的身高代码。在某个地方我犯了一个错误，我确定在哪里可以找到它。

为什么我的代码不评估某些树？

Prolog - 平衡树与否

这是我基于平衡树测试的线程，我确实尝试过他在评论中发布的树，但我失败了，有什么想法吗？

我在 C++ 中实现了一个红黑树，但是我的旋转方法有问题。插入方法工作得很好，没有任何平衡，但是一旦我尝试旋转，我的树就会丢失信息。我的猜测是我没有以正确的方式设置指向节点的指针，但我不太明白这里到底出了什么问题。

这是我的向右旋转方法：

正在发生的事情的一个例子是我插入 c、b 和 a。树最初看起来像这样：

旋转后，树只会打印出根节点，c。

关于可能发生的事情的任何想法？谢谢！

因此，在平衡 KD 树时，您应该找到中位数，然后将所有较小的元素放在左子树上，将较大的元素放在右边。但是，如果您有多个元素的值与中位数相同，会发生什么？它们进入左子树，右子树还是丢弃它们？

我问是因为我尝试过做多件事，它会影响我最近邻搜索算法的结果，并且在某些情况下，树的给定部分的所有元素都将具有完全相同的值，所以我不知道在这种情况下如何将它们分开。

假设我有一个带有 N 个节点的常量（一旦构建就不会改变）平衡树，每个内部节点都有 p 个子节点。显然，访问节点的最坏情况是 logp(N)。但是访问 r 个节点的摊销成本呢？如果我们按升序访问它们（有一个搜索树）怎么办？它只是（logp（N））/ r吗？

我正在为 AVL 树做演示，不明白什么是平衡因子。请给我链接或任何我能以图形方式理解的 AVL 树的高度效应的高度

我在项目（Java's）上使用带有链接叶子的红黑二叉树TreeMap，以快速查找和迭代项目。问题是我可以轻松地在树上获得 35000 个左右的项目，并且有几次我必须删除“X 以上的所有项目”，这几乎可以是整个树（就像一次 30000 个项目，因为它们都更大比 X），并且每次都需要花费太多时间来删除它们并重新平衡树。

有什么算法可以帮助我（所以我可以自己实现树）？