问题标签 [tree-rotation]

我正在尝试实现一个自平衡二叉搜索树并编写了一个函数来用它的左旋转替换一棵树：

尝试使用rustc bst.rs导致以下错误编译此示例：

我知道，由于函数返回时原始树被破坏，由于生命周期参数逆变，它的左旋转不能超过它。我的意图是让函数消耗原始树并返回左旋转，这样左旋转将继承原始树在未调用函数时的生命周期。这在 Rust 中可能吗？如果不是，实现我支持树替换的目标的最简单设计是什么？我的偏好是避免依赖 Rust 标准库并学会自己管理生命周期。

请原谅我缺乏 Rust 生命周期的经验。我的背景知识主要是 C++ 和 ML 风格的语言。

我很难理解为什么下面的树旋转代码有效。如果T2指向y.left和y.left指向x，这不是使最后一个赋值x.right = T2等于x.right = x吗？指针不应该指向初始T2吗？

我现在正在学习算法，在实现红黑树插入时，我想到了问题标题中描述的想法。这发生在涉及等值节点时。

让我们从一个简单的示例树开始，其中左子节点小于父节点，右子节点大于或等于父节点。

这种树的初始状态可能如下：

然后，如果我向左旋转这棵树，我得到：

违反 BST 条件的节点，即所有左子节点都小于父节点，以红色显示。

所以问题是：为什么许多在二叉搜索树上实现插入、删除或其他操作的算法在旋转破坏 BST 时使用旋转（或者我只是做错了旋转）？

这个问题类似于完成 BST 数组表示的排序列表，但可能更具体。这个问题可以用来解决在 Complete Binary Search Tree 中动态插入节点。

考虑在内存中表示为连续数组的完整二叉树a[0..n)，其中元素a[0]是树的根，对于任何节点a[i]，它都有左孩子a[2*i+1]和右孩子a[2*i+2]（如果这些索引小于n）。

C++ 程序员会熟悉这种表示形式，因为std::make_heap. std::make_heap(a, a+n)接受一个未排序的数组（可以看作是一个未排序的完整二叉树）并排列它的元素（可以看作是树的旋转）以将树变成一个完整的二叉堆，其中每个节点的值都大于它的任何一个子节点。我们说结果数组是“最大堆顺序”。

另一方面，如果每个节点的值都大于其左孩子但小于其右孩子，那么我们说完全二叉树是完全二叉搜索树。在这种情况下，假设结果数组处于“级别顺序”。^[1]

尽管对于给定的一组元素有许多允许的“最大堆顺序”，但每组元素只有一个唯一的“级别顺序”。

以下向量按水平顺序排列：

我正在寻找的是一系列有效的算法：

1. 将未排序的序列排列成水平顺序
2. 将已排序的序列排列为级别顺序
3. 将级别顺序序列排列为排序顺序

当我说高效时，我的意思是无需深度递归、无需动态内存分配且无需临时数组即可工作的算法。我已经知道置换不能特别快地完成；我希望 O(n lg n)。

请注意，第 2 部分和第 3 部分基本上要求提供映射OldIndex -> NewIndex；一旦有了这样的功能，您就可以使用其中一种算法就地进行排列。

第 1 部分要求nonstd::make_searchtree通过类比来实现std::make_heap. 第 3 部分要求nonstd::sort_searchtree通过类比来实现std::sort_heap.

[1]——我基本上是编造了“水平顺序”这个词。如果您知道此排序的更广泛认可的学术术语，请发表评论！

所以我有一个看起来像这样的二叉树实现

（实际的实现稍微复杂一些，因为存储了额外的数据，因为这是用于布尔代数简化器，但为了让我的观点更简单，我会保持简单）

基本上我收到一棵树，我需要对其进行改造，使其完全左倾

例如

需要成为

我了解树旋转的概念，但我真的不知道如何使用它们（或任何其他算法）使树完全倾斜，如上图所示

如果有人能指出我的算法或其他资源的方向来做到这一点，我将非常感激

我已经实现了几个函数来旋转展开树中的节点，但它通过将相同的节点发送到不同的地方以某种方式破坏了我的树。他们将儿子旋转到父亲节点。爸爸的指针可能是过度的，但我想尝试这种方式。我在函数中使用那些将节点调整为根。

我想知道我是否在 AVL 树上正确应用了以下插入和删除操作：

• 插入物(42)
• 插入(90)
• 删除(62)
• 插入(92)
• 删除(50)

对于这个问题，删除会将已删除的项目替换为其后继项目。

这就是我认为应该通过这些操作修改树的方式：

插入（42）和插入（90）

删除(62)

插入(92)

删除(50)

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

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

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

我在尝试旋转 AVL 树时遇到了一些麻烦。我整天都在网上挖掘，我认为我的代码应该可以工作。我不知道为什么，但是当我测试我的函数时，我丢失了应该旋转的子树。

我能得到任何帮助吗？

这是代码：

这是平衡树的函数：

注意：cbst__balance是一个函数，它返回作为输入给出的树的权重。