algorithm - 二叉搜索树会被旋转破坏吗？

Question

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

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

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

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

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

---

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

Answer 1

问题是为什么要在满足所有条件时轮换 BST。您的示例中的旋转将不会在任何意义上实现。在“许多算法”中，仅当“插入”或“删除”或“其他”生成违反 BST 属性的新树时才需要旋转。假设您将 6 替换为 8 作为 BST 的根，现在您的轮换将有意义。

Answer 2

据我所知，大多数教科书通过考虑唯一键来介绍 BST，即：left < root < right. 一切都基于此，包括轮换。如何处理重复项通常留作练习，没有人说它必须像将不变量更改为left <= root < right.

这完全是因为您描述的问题：在某些情况下，旋转可能无法“开箱即用”重复。即使您添加重复节点（并且不要在每个节点中存储计数），也可能总有一种方法可以使它们工作，但是不得不提及边缘情况及其解决方案只会分散总体思路涉及旋转的各种树。

所以基本上：

• 根据您的树，如果您更改教科书的先决条件，旋转可能并不总是以教科书中描述的“标准”方式工作：如果教科书说left < root < right，您不应该假设它的算法也可以按照给定的 forleft <= root < right或任何其他先决条件工作。你可能需要改变一些东西。例如，在 RB 树中，您可能需要在较低级别进行旋转。
• 如果您不想更改任何内容，只需在节点中添加另一个字段，该字段计算该节点的键出现的次数。