红黑树旋转操作是否同时保留所有节点黑高与中序遍历顺序求证

考题核心题干 #

围绕红黑树的旋转操作，设置两个待判断的性质论断，要求选出正确的论断组合：

• 论断1：旋转可保留所有节点的黑高
• 论断2：旋转可保留中序遍历顺序
  对应待选选项：
• A. 仅论断1正确
• B. 仅论断2正确
• C. 论断1、2均正确
• D. 论断1、2均不正确

争议双方观点 #

• 授课教师官方判定：旋转操作不保留节点黑高，正确答案为B，即旋转仅能保留中序遍历顺序
• 参考考生（提问者）存疑立场：认为旋转操作可同时保留所有节点的黑高，正确答案应为C而非B，特发起技术求证，明确两方观点的实际正确性

核心技术判定 #

纯旋转操作的设计目标，就是在不改动节点颜色、不破坏已有二叉搜索树计数属性的前提下，调整树的结构平衡：

• 中序遍历顺序的保留是旋转的固有特性：旋转只会调整子树的指针指向，完全不改动节点的键值相对位置，旋转前后遍历整棵树得到的中序序列完全一致，这一点不存在任何争议。
• 节点黑高的保留同样是纯旋转的固有特性：旋转全程不会修改任何节点的颜色值，子树内部的节点连接关系也不会被调整，每个节点到其下方NIL叶子节点路径上的黑色节点计数（即黑高），不会因为纯旋转发生任何变化。

造成本次判卷偏差的常见认知误区：很多人会把红黑树插入/删除节点后，旋转配套的变色修复步骤对黑高的影响，错算成旋转本身的效果。实际上如果没有后续的性质修复流程，单独执行纯旋转操作完全不会改动黑高。
综上，提问者对题目的技术理解是准确的，该考题的正确答案应为C，授课教师的判定存在概念混淆，把后续的修复变色操作和纯旋转操作的技术边界搞混了。

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