旋转操作直接影响父指针、左右子指针、高度和平衡因子;其中高度必须更新以确保后续平衡判断准确,平衡因子随之重算;中序序列、键值、节点身份等保持不变。
路径压缩技术通常用于并查集(union-find)中,与二叉搜索树(bst)的旋转操作没有直接关系。你提到的“二叉搜索树旋转操作对变量的影响”,实际关注的是旋转过程中节点指针、高度值、平衡因子等内部状态的变化,而非路径压缩。
旋转操作改变哪些变量
在AVL树等自平衡BST中,一次旋转(如左旋或右旋)会直接影响以下变量:
- 父指针(parent):新根节点的父指针被更新;原根及其子节点的父指针也需重连
- 左右子指针(left/right):例如右旋时,原根节点的left指向其左孩子的右子树,而左孩子节点的right指向原根
- 高度(height):旋转后子树结构变化,必须重新计算涉及节点的高度,否则后续平衡判断失效
-
平衡因子(balance factor):高度变更后,相关节点的平衡因子自动改变,通常需显式更新(如
node.bf = height(left) - height(right))
为什么高度和平衡因子必须更新
不更新高度会导致后续插入/删除时误判是否失衡。例如:某节点右旋后,若未更新其新父节点的高度,下次检查该节点平衡因子时仍用旧高度计算,可能漏掉本应触发的双旋场景。
平衡因子本身不存储在所有BST实现中,但在AVL树中是核心判断依据。它不是独立维护的,而是由左右子树高度差实时推导——所以真正需要主动更新的是高度,平衡因子可按需重算或随高度同步修正。
旋转不影响的变量
以下内容在旋转中保持不变:
- 中序遍历序列:旋转不改变BST的有序性,所有节点的键值相对顺序完全保留
- 节点存储的数据(key/value):旋转只调整结构连接,不读写业务数据
- 内存地址或节点身份:节点对象本身不被复制或销毁,只是指针关系重排
典型代码中的变量修改示意
以右旋为例(y为原根,x为y.left):
执行x.right = y和y.left = T2后,必须紧接着调用updateHeight(y)和updateHeight(x);若使用平衡因子优化,还需设置x.bf = 0、y.bf = 0(LL型单旋后的情形),但该赋值依赖于旋转前T2的高度情况,并非无条件成立。











