平衡树树旋转

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
inline void left_rotate(int &node)
{
    int r=tree[node].r;
    tree[node].r=tree[r].l;
    tree[r].l=node;
    node=r;
}
inline void right_rotate(int &node)
{
    int l=tree[node].l;
    tree[node].l=tree[l].r;
    tree[l].r=node;
    node=l;
}

分析

先上一张树旋转的示意图

树旋转

图片来自《算法导论》 $\text{P176 13.2}$ 旋转

树旋转的作用

树旋转是平衡树上用于维护平衡树平衡的基本操作，有左旋和右旋两种操作

旋转过程分析

在进行树旋转时需要维护好二叉搜索树的性质，即

对于每棵子树，都有：

左 < 根 < 右

再看《算法导论》中描述旋转的图片。

以右旋为例，旋转后$\text{x}$代替$\text{y}$作为子树的根节点，由于原来$\text{x}$在$\text{y}$的左子树上，所以旋转最后$\text{y}$在$\text{x}$的右子树上；

而旋转前$\text{x}$的左子树$\alpha$的根节点则一定小于$\text{x}$和$\text{y}$,所以旋转后$\alpha$仍在$\text{x}$的左子树上；

而$\text{x}$的右子树$\beta$的根节点则可以看出来是$\text{x} < \beta < \text{y}$的一种关系，所以旋转后在$\text{y}$的左子树上；

至于$\text{y}$的右子树$\gamma$则与$\text{x}$的左子树$\alpha$类似，这里不再阐述。

代码分析

以左旋为例：

1
int r=tree[node].r;

先将node节点的右子树另外保存，同swap函数的t变量类似。

1
tree[node].r=tree[r].l;

将图中$\text{x}$节点的右子树$\text{y}$节点改为$\text{y}$节点的左子树$\beta$

1
tree[r].l=node;

将图中$\text{y}$节点的左子树改为$\text{x}$节点

1
node=r;

最后把正在旋转的子树的根节点改为$\text{y}$

参考文献

  1. 【AgOHの数据结构】平衡树专题之叁 树旋转与AVL树

  2. 《算法导论》 $\text{P176 13.2}$ 旋转

  3. Github/StableAgOH/Codebase-for-AgOH