我现在正在学习算法，在实现红黑树插入时，我想到了问题标题中描述的想法。当涉及到等值节点时，就会发生这种情况。
让我们从一个简单的示例树开始，其中左子节点小于父节点，右子节点大于或等于父节点。
这种树的初始状态可能如下:
然后，如果我向左旋转这棵树，我会得到:
违反所有左子节点都小于父节点的 BST 条件的节点以红色显示。
所以问题是:为什么许多在二叉搜索树上实现插入、删除或其他算法的算法在旋转破坏 BST 时使用旋转(或者我只是做错了旋转)？
最佳答案
问题是为什么要在满足所有条件时轮换 BST。您示例中的轮换不会以任何方式实现。在“许多算法”中，仅当“插入”或“删除”或“其他”生成违反 BST 属性的新树时才需要旋转。比方说，如果您将 6 替换为 8 作为 BST 的根，那么您的旋转现在就有意义了。
关于algorithm - 二叉搜索树可能会因旋转而损坏吗？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/49601436/