问题标签 [tree-balancing]

我正在实现 AVL 树，并且我的搜索和插入功能正常工作，但是我的删除功能出现分段错误。我之前已经正确实现了 BST 树，所以我知道问题在于树的重新平衡，而不是节点的初始删除。

由于我的插入操作适用于重新平衡，我也知道问题不在于旋转功能本身。

我尝试了不同的策略，例如在每个节点上保持平衡因子，并尝试实现我在网上找到的其他源代码，但我总是以分段错误而告终，并且真的找不到在哪里。我会很感激任何帮助。

所以我需要删除函数来删除指定的节点，并在必要时使用适当的旋转重新平衡树。但是，每当我尝试在我的 main.js 中调用该函数时，我都会遇到分段错误。谢谢。

对于硬件任务，我的任务是向 BinarySearchTree 类添加一堆方法。我有两种方法是 balance 和 InsertTree（我认为它应该被命名为 InsertNode）。教科书的作者提供了这些方法应该是什么样子的伪代码。两种方法相互配合；balance 应该采用不平衡的树并将每个元素插入到数组中。我相信 InsertTree 应该从数组中获取元素并将它们放回新形成的树中。

BST 类本身非常大，所以我认为发布它不是一个好主意。但是您可以在示例材料下找到源代码。参考代码位于 ch07.trees 包中。

到目前为止，这是我对作者伪代码的解释：

我必须使用 ArrayList，因为所有方法都是 T 类型的泛型。在我的驱动程序类中，我只是添加了一组不平衡的元素 [A、B、C、D、E、F]，并且索引将正确显示我已经增加index 为 6。但是，当新树调用 InsertTree(0, index - 1) 时，我得到了这个：

163 号线tree.InsertTree(0, index -1);和 180 号线是tree.add(array.get(mid));

似乎问题与中点有关，但我不确定问题可能是什么。我不是使用 ArrayLists 的专家，因此对于解决此问题的任何帮助将不胜感激。

编辑：

我相信问题已经解决了。我将创建的数组放回 balance 方法而不是方法之外，并将数组添加到 InsertTree 方法参数中。然后，我必须将 this.tree.add 中的每个条件输出更改为 this.add。我还将 BinarySearchTree 树移回了平衡方法，因为在我收到 NullPointerException 之前。

我的方法是否按预期工作仍有待确定。

我有一个 BST 的插入函数，它还调用并检查节点是否平衡。如果不是，我在节点上调用旋转函数。这就是问题所在 -> 直到那时我的程序运行良好，但是，在添加该函数后，我的程序抛出了错误。我现在只写了 leftrotate 函数，因为我正在测试一个只需要左旋转的案例，因此现在的 rightrotate 现在没有问题。这是我的插入功能

平衡的标准是这样的：一个节点的左子树和右子树的绝对差不能大于1。这是我的左旋转函数：

这是释放树的函数：

但是，所有块都没有被释放，并且树似乎没有正确地平衡自己。这是 valgrind 报告：

我究竟做错了什么 ？有小费吗？编辑：最小的主要，我打开的文件是一个二进制文件。'i' 是指插入指令。

当我试图从我的自平衡树中删除一个节点（如只有插入操作时，没有泄漏）时，我特别遇到了内存泄漏。在我的删除和插入操作完成后，我调用了一个函数来销毁树，但仍然存在内存泄漏。该函数本身似乎工作正常（我打印了一个树的前序遍历，它是正确的）。这是我的删除功能的样子：

还有我的销毁/免费功能：

我不知道如何释放要删除的节点的内存。这就是内存泄漏的原因——当我打印正在释放的根（在destroytree中）时，总是丢失已删除的节点，因此我认为这就是内存泄漏的地方。我唯一的问题是，使用我编写的 deletenode 函数，我不知道在哪里释放这些内存。我将不胜感激任何帮助。另外，当我插入节点时，我当然会在我的插入节点中进行 malloc。

我正在 Idris 中实现红黑树。在这个实现中，节点除了携带有关其值和颜色的信息外，还携带有关其黑色高度的信息（即从该节点到任何叶子的黑色节点的数量，不包括自身）。

为了实现插入功能，我必须实现一个平衡功能，它修复了红色节点有一个红色子节点的任何情况（这违反了红黑规则）。这是它修复的一种情况。

Bx 表示节点 x 为黑色，Rx 表示节点 x 为红色。括号中的 n 是该节点的黑色高度。

这是平衡的代码。

第一行（不是类型定义）是图中的内容。

当我运行它时，我得到了这个：

我不确定错误是什么。它可能与类型定义中的 p 和 q 有关吗？

我正在探索 AVL 树并找到了这个答案，其中有人说 AVL 中的查找比插入或删除更快。

尽管对于所有这 3 个过程，最差的时间复杂度仍然是对数。

是因为插入过程中涉及的旋转或平衡吗？

根据自平衡 BST 的定义，孩子的身高应该 = Big-Theta(logn)。

在以下情况下，如何检查 BST 是否是自平衡的？其左子树和右子树中的节点数不超过其子树（包括节点本身）中节点总数的90%。