问题标签 [tree-rotation]

给定一组值，可以从这些值形成许多不同的可能的二叉搜索树。例如，对于值 1、2 和 3，我们可以根据这些值生成五个 BST：

许多基于平衡二叉搜索树的数据结构使用树旋转作为重塑 BST 的原语，而不会破坏所需的二叉搜索树不变量。树旋转可用于将节点拉到其父节点上方，如下所示：

给定一个包含一组值的 BST，是否总是可以将该 BST 转换为同一组值的任意其他 BST？例如，我们是否可以仅通过使用树旋转将上述五个 BST 中的任何一个转换为任何其他 BST？

我试图在完成重新平衡时找出红黑树中的旋转。我理解为什么会发生轮换，但我不明白它是如何完成的。此外，像 LL、RR、LR 和 RL 这样的中间旋转是为了达到结果而完成的，如果有人告诉我关于何时进行这些旋转中的任何一个的任何经验法则，我也将不胜感激。这是旋转：

当我在学习二叉树的中期时，我发现了一个声明，即任何任意 n 节点二叉树都可以转换为任何其他 n 节点二叉树，最多 2*n-2 次旋转。有什么证据吗？我找到了某种渐近符号的证明，但不是那么清楚。我的意思是有人可以解释/说明为什么这是真的吗？如果它说 n 节点二叉树，它是否包括根？

在《Introduction To Algorithms - A Creative Approach 》一书中，问题 4.24：

令 T1 和 T2 是两棵任意树，每棵树都有 n 个节点。证明对 T1 最多应用 2n 次旋转就足够了，因此它等于 T2。

对于二叉搜索树，我想出了一个算法：

1. 找到等于 T2 的根的元素，我们称之为目标根。

2. 使用 AVL 旋转策略，旋转 target-root 使其成为 T1 的新根。
   在此过程中，可能会执行多次旋转。

3. 对于 T1 和 T2 的左子树，递归处理如上。
   对于 T1 和 T2 的右子树，递归处理如上。

该算法在最坏的情况下运行在 O(N^2) 中。

我不太明白“任意树”这个短语，我不知道如何使 T1 等于 T2。

有人可以帮助解决这个问题吗？

将新元素插入n-element Red Black Tree 时的最大旋转次数是多少？

如果我是正确的，不违反 RBT 规则的插入需要最大2轮换（2 例）。假设是这样，O(1)也是正确答案吗？

如果是这样，请确认并告诉我，什么需要最多 3 次旋转？

AVL 树似乎有四种变换：Left-Left、Left-Right、Right-Left 和 Right-Right。但是，似乎也可能存在其他情况。我将此提交为左平衡：

左旋和右旋都不能平衡这棵树。使用什么算法来平衡它？

这是序列 20,10,5,30,40,57,3,2,4,35,25,18,22,27 我已经尝试过将每个新插入的节点都设为根，但它不起作用。谁能给我一步一步的解释？

这个较早的问题询问是否总是可以将一组值的一个 BST 转换为仅使用树旋转的同一组值的另一个 BST（答案是肯定的）。但是，是否总是可以使用最多 O(n) 总树旋转来做到这一点？

我一直面临着 AVL 树实现的一个非常奇怪的问题。鉴于下面的代码，我只能在没有正确旋转的情况下运行它，因为如果这样做，我就会崩溃。我已经尝试过调试、删除文件和重新制作项目，然后重新构建，这些都没有奏效。

预先，如果代码有点难以理解，我深表歉意，我是巴西人，变量名大多是葡萄牙语，如果这被证明是帮助解决问题的问题，我会将变量名更改为英文。

avl.h文件：

avl.c文件：

main.c文件：

正如你所看到的，我的左右旋转功能（rotaciona_dir和rotaciona_esq分别）基本上是镜子，所以我觉得右边的那个不起作用。我尝试了不同的调用，现在我只是使用for循环进行测试。如果我让输入减少，一切正常，但只要我需要调用该rotaciona_dir函数，程序就会崩溃。

关于 IDE/编译器，我在 Ubuntu 16.04 LTS 系统中使用 Code-Blocks IDE 13.12。

此外，欢迎任何代码改进或一般编程技巧。我自己不是一个 C 程序员（Python 是我的主要语言），所以这个问题的答案可能很简单，我就是不明白。

我有以下二叉树，我正在尝试使用最少的树旋转次数将其转换为目标二叉树（帖子中的第二棵树）。这棵树的理论最小旋转数是 5，但是，我能算出的最小值是 6 旋转，我也复制了旋转，我错过了什么？

树： 1 \ \ 3 / \ / \ 2 5 / \ / \ 4 7 / \ / \ 6 11 / \ / \ 9 12 / \ 8 10

目标树： 1 \ \ 11 / \ / \ 9 12 / \ / \ 3 10 / \ / \ 2 5 / \ / \ 4 7 / \ 6 8

到目前为止我尝试过的旋转（所有这些都需要 6 次旋转）：

订单 1： Rotate left with root 7 and pivot 11 Rotate left with root 5 and pivot 11 Rotate left with root 3 and pivot 11 Rotate left with root 7 and pivot 9 Rotate left with root 5 and pivot 9 Rotate left with root 3 and pivot 9 订单 2： Rotate left with root 7 and pivot 11 Rotate left with root 5 and pivot 11 Rotate left with root 7 and pivot 9 Rotate left with root 3 and pivot 11 Rotate left with root 5 and pivot 9 Rotate left with root 3 and pivot 9

订单3： Rotate left with root 7 and pivot 11 Rotate left with root 5 and pivot 11 Rotate left with root 7 and pivot 9 Rotate left with root 5 and pivot 9 Rotate left with root 3 and pivot 11 Rotate left with root 3 and pivot 9

订单4： Rotate left with root 7 and pivot 11 Rotate left with root 7 and pivot 9 Rotate left with root 5 and pivot 11 Rotate left with root 3 and pivot 11 Rotate left with root 5 and pivot 9 Rotate left with root 3 and pivot 9

订单5： Rotate left with root 7 and pivot 11 Rotate left with root 7 and pivot 9 Rotate left with root 5 and pivot 11 Rotate left with root 5 and pivot 9 Rotate left with root 3 and pivot 11 Rotate left with root 3 and pivot 9