旋转操作是否会破坏二叉搜索树（BST）的结构？

哈哈，这个问题我当初写红黑树插入逻辑的时候也卡了好久！等值节点的处理确实是红黑树实现里容易踩的隐形坑，尤其是旋转操作和BST基础性质的冲突，我来给你捋捋根源和解决办法～

问题到底出在哪？ #

你描述的场景里，核心矛盾是等值节点的放置规则和左旋转操作的适配性冲突：

• 你设定的初始BST规则是「左子节点 < 父节点，右子节点 ≥ 父节点」
• 当对某个带等值右子节点的节点执行左旋转后，原来的右子节点（等值节点）会变成新的父节点，而原来的父节点会沦为它的左子节点——这时候就直接违反了「左子节点必须小于父节点」的BST规则。

两种可行的解决思路 #

根据我自己的实现经验，有两种靠谱的修正方向，你可以根据需求选：

1. 调整等值节点的放置逻辑（推荐） #

最省心的办法是要么用计数字段代替新增节点，要么统一等值节点的存放位置：

• 「计数字段方案」：遇到等值节点时，不需要新增树节点，直接给目标节点加一个count属性（初始为1，插入等值就+1）。这种方式完全避免了等值节点带来的旋转冲突，还能减少树的高度，效率更高。
• 「统一存放位置方案」：把原来的规则改成「左子节点 ≤ 父节点，右子节点 > 父节点」，也就是所有等值节点都放左子树。这样左旋转后，原父节点作为新父节点的左子节点，依然满足≤的条件，不会触发BST性质违规。

2. 旋转前后针对性修正 #

如果必须保留「右子节点 ≥ 父节点」的规则，那就要在旋转操作前后加判断逻辑：

• 旋转前先检查目标节点的右子节点是否是等值节点：如果是，先对这个右子节点执行一次右旋转（把它的右子树提上来，让非等值的节点成为右子节点），再执行原左旋转。
• 或者在旋转完成后，立即检查新父节点和左子节点的关系：如果是等值情况，直接交换两个节点的位置，或者调整它们的子树结构，确保左子节点严格小于父节点。

举个直观的小例子 #

假设初始树结构是这样的：

5
     \
      5  # 等值右子节点

直接左旋转后会变成：

5
   /
  5

这就违反了你的BST规则。但如果用计数字段的话，直接把根节点的count改成2，根本不需要旋转；如果把等值节点放左子树，初始结构就是：

5
   /
  5

后续任何旋转操作都不会触发性质冲突。

内容的提问来源于stack exchange，提问作者Denis Seletkov