问题标签 [tree-balancing]

我使用自平衡二叉搜索树（目前它是一棵 AVL 树，但可以用另一棵树代替）。我注意到有一些不同的时期只执行某些操作：很少执行大量删除或插入批处理，而大部分时间它是不可变的搜索树。如果我将重新平衡推迟到批次结束，会有任何性能提升吗？

对于类分配，我需要向提供的 BinarySearchTree 类添加一个方法，该方法将通过将值按顺序存储在数组中来平衡二叉搜索树，并使用这些值构造一棵新树。但是，当我尝试运行该方法时，我得到一个 nullPointerException。如何更改方法以正确平衡二叉搜索树？

我在下面包含了我的代码（试图将其缩减为仅解决问题所需的代码）；底部的两种方法是我试图用于平衡的方法。

我正在阅读有关 AVL 树的信息，并在那里重定向到自平衡树，我读到了

在计算机科学中，自平衡（或高度平衡）二叉搜索树是任何基于节点的二叉搜索树，它在面对任意项目插入和删除时自动保持其高度（根以下的最大层数）较小。1

这些结构为可变有序列表提供了有效的实现，并可用于其他抽象数据结构，例如关联数组、优先级队列和集合。

我很困惑

1. 高度与列表有什么关系？大批？
2. 小高度树如何为可变有序列表提供有效的实现？大批？排队？
3. 假设列表的节点或数组的索引是列表或数组的高度，它怎么会小？

我正在尝试从元素向量创建一个 AVL 完美平衡的树。我已经开始使用少量元素（8），以便我可以检查算法的正确性。打印树中的值时出现我的问题，我不断收到下一个异常

当我到达 (root)->(right)->left-:value 时，即使我在打印任何内容之前检查指针是否为空。结构是：

数组：int vector[8] = { 1, 2, 3, 4, 5, 6, 7, 8 }; 打印功能：

调用：

构建树是我的构建功能：

我对使用指针和平衡树有点生疏。有人可以帮助我提供线索吗？

在树上：

使节点 C 不平衡的两个子树是什么？

我目前正在使用 C++ 学习数据结构。我了解在插入新节点时如何平衡二叉搜索树。

但是，如果您已经有一个退化的树（单个链接列表），并且想要在不创建新树的情况下平衡它怎么办？总之，我将如何使用现有节点将退化树重新组装成完整的树？（使用旋转方法）

例如，我的节点保存（9 个节点）的数据：1、3、6、9、12、15、18、21、24

我需要一个推动开始。我不知道从哪里开始。感谢您的帮助。

我能找到的所有类型的二叉搜索树都是自平衡的。有没有什么不是，实际上是有用的？

我在红黑树上输入了几个数字。(41; 38; 31; 12; 19; 8) 删除 8 和 12 (第一个截图) 后进入第二个截图的类型。我不明白为什么 31 变成红色。请帮帮我？如果您可以请提及与此相关的案例。谢谢 ！

给定一个仅由加减法运算符和数字组成的二元算术表达式树，如何尽可能平衡树？任务是在不评估表达式的情况下平衡树，即节点的数量应该保持不变。

例子：

加法是可交换的和关联的，并且允许平衡。交换性允许交换连续“+”节点的子节点。关联性允许旋转。在上面的例子中，执行的转换可以被视为

1. 在根部的“+”上向右旋转。
2. 交换“5”和“-”节点。

我正在考虑按顺序遍历并首先平衡任何子树。我会尝试通过尝试所有可能的节点排列（其中只有 12 个）来平衡具有两个连续“+”节点的任何子树，以希望降低树的总高度。此方法应在任何步骤将树的高度最多减少 1。但是，我无法确定它是否总是会给出最小高度的树，尤其是当有超过 2 个连续的“+”节点时。

另一种方法可能是将表达式树读入数组并用变量替换任何“-”子树。然后我们 DP 确定括号的最佳位置。这必须自下而上进行，以便任何“-”子树在 DP 算法考虑时已经平衡。但是，我很担心，因为可能有 (n+1)！排列节点和括号的方法。虽然我正在寻找 O(n) 算法。

这是一个已知问题吗？是否有具体的解决方法？

我有一个BinarySearchTreeInstance bankaccount 的对象，这是我创建的一个类，所以基本上它只是一个二元搜索树，我编写了一个方法来获取树并平衡它，由于某种原因，它在平衡之前准确地打印出树：

现在，首先我有一个createList方法，它接受一个列表和一个并通过按顺序遍历它来tree(one node)创建一个树数据，因此它是一个排序数组。arrayList(DynamicArray)然后使用另一种方法以平衡的方式创建树，方法是使数组的中间元素成为根，然后将左中间元素作为左子树的根，将右中间元素作为右子树的根

出于某种原因，如果我这样做：

好吧，它将首先使用比较器按数字对数组进行排序，因此数组应该是 {1,2,3,4,5,6,7,8} （这就是比较器的工作方式）然后我期望树要平衡，但它保持不变。知道代码有什么问题吗？

编辑：这是我到目前为止所做的更改，buildBalancedTree 给了我一个 NullpointerException