如何通过旋转或交换操作更新Binary Search Tree且不破坏其性质？

当需要修改BST节点值且不能用删除再插入的方式时，可通过交换节点值配合递归调整或旋转调整节点位置来实现，核心是始终维持BST的左小右大性质。

方法一：交换节点值（最直观） #

根据新值与原节点值的大小关系，分两种情况处理：

情况1：新值小于原节点值 #

1. 找到当前节点左子树的最大值节点（即左子树最右侧的节点，该节点无右子树）
2. 交换当前节点与该最大值节点的值——此时当前节点的值变为左子树最大值，符合BST性质（左子树所有节点≤该值，右子树所有节点>原节点值>该值）
3. 把问题转化为：在最大值节点的原位置，将其值从原节点的旧值改为新值。重复上述步骤，直到该节点无左子树，直接修改其值为新值即可（此时该节点是当前子树的最小值候选，修改后不会破坏父节点的大小关系）

情况2：新值大于原节点值 #

1. 找到当前节点右子树的最小值节点（即右子树最左侧的节点，该节点无左子树）
2. 交换当前节点与该最小值节点的值——此时当前节点的值变为右子树最小值，符合BST性质（左子树所有节点<原节点值<该值，右子树所有节点≥该值）
3. 把问题转化为：在最小值节点的原位置，将其值从原节点的旧值改为新值。重复上述步骤，直到该节点无右子树，直接修改其值为新值即可

示例

原BST结构：

5
   / \
  3   7
 / \ / \
2  4 6  8

• 把节点5的值改为4：

  1. 找到左子树最大值节点4，交换5和4的值，树变为：

     4
       / \
      3   7
     / \ / \
     

  2 5 6 8

  2. 原4节点（现在值为5）无右子树，直接改为4，最终树：
  

  4
   / \
  3   7
  

  / \ /
  2 4 6 8

• 把节点5的值改为6：

  1. 找到右子树最小值节点6，交换5和6的值，树变为：

     6
       / \
      3   7
     / \ / \
     

  2 4 5 8

  2. 原6节点（现在值为5）无左子树，直接改为6，最终树：
  

  6
   / \
  3   7
  

  / \ /
  2 4 6 8

方法二：旋转调整节点位置 #

如果必须使用旋转操作，核心是将目标值对应的节点逐步提升到当前节点的子节点位置，再交换值：

情况1：新值小于原节点值 #

1. 定位左子树的最大值节点M
2. 若M是其父节点P的右孩子，对P执行左旋，将M提升为P的父节点；重复此操作，直到M成为当前节点的左孩子
3. 交换当前节点与M的值
4. 在M的原位置（此时该节点无右子树）修改值为新值

情况2：新值大于原节点值 #

1. 定位右子树的最小值节点M
2. 若M是其父节点P的左孩子，对P执行右旋，将M提升为P的父节点；重复此操作，直到M成为当前节点的右孩子
3. 交换当前节点与M的值
4. 在M的原位置（此时该节点无左子树）修改值为新值

旋转操作的本质是调整节点层级，让目标节点更接近当前节点，避免直接删除插入带来的结构变动。

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