algorithm - 二叉搜索树可能会因旋转而损坏吗？

Question

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

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

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

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

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

---

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

Answer 1

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