AVL树执行旋转操作后有多少个节点的深度会发生变化

首先我们可以直接给出明确结论：单次AVL旋转操作只会修改常数个节点的层级，和树的总规模无关，整体重平衡过程的层级修改节点量级要分插入、删除两种场景判断：

不管是LL/RR型单旋，还是LR/RL型双旋，单次旋转涉及的节点都是固定数量的：

• 单旋仅需调整3个节点的父子关系，对应修改这3个节点的层级
• 双旋本质是两次连续的单旋，最多调整4个节点的层级
  两种情况都属于O(1)量级，不会随树的高度变化。

举个LL型单旋的例子：

假设失衡节点为A，其左孩子为B，B的右子树根节点为C。旋转后B成为该子树的新根，A降级为B的右孩子，C调整为A的左孩子。整个过程只有A、B、C三个节点的父节点发生变化，其余节点的父节点、层级完全不受影响。

插入节点后，我们从插入位置向上回溯，找到第一个失衡节点执行旋转后，该子树的高度会直接恢复到插入前的高度，失衡状态不会向上传播，因此插入操作最多只会触发1次旋转。
整个插入重平衡过程中，修改层级的节点总数是O(1)，和树的高度log(n)无关。

删除节点会导致所在子树的高度减1，完成一次旋转调整后，当前子树的高度可能仍然比删除前低1，失衡状态会向上层父节点传播，因此最多需要回溯O(log n)层，触发O(log n)次旋转。
每次旋转修改O(1)个节点的层级，因此整个删除重平衡过程中，修改层级的节点总数是O(log n)，和你猜测的量级一致。

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