浅谈 Splay(一)

浅谈 Splay(一)

1. 右旋(Right Rotation)

观察每个节点的变化,其中每个节点都有指向其父节点的指针没有画出。

1.png

①②③处节点连接有变化。

(1)$Q$ 的左子树修改为 $P$ 的右子树的内容

即 $B$ 成为 $Q$ 的左子树, $B$ 的父节点是 $Q$ 。

1
2
q->left = p->right; 
p->right->father = q;

注意 P​ 可能没有右子树(即不存在 P->right 节点)。

修改如下:

1
2
q->left = p->right; 
if(p->right != NULL) p->right->father = q;

(2)$P$ 的右子树修改为 $Q$ ,且同时 $Q$ 的父节点修改为 $P$ 。

1
2
p->right = q; 
q->father = p;

注意 Q 和 P 的左右子树有变化,所以 Q,P 的信息需要重新维护。

1
update(q); update(p); //先Q后P

(3)$R$ 的子树应该修改为 $P$

需要判断 $Q$ 是 $R$ 的哪种子树,左子树则 $P$ 给 $R$ 的左子树,否则给右子树。

全局变量 $root$ 记录树根。

特判 $Q$ 有可能就是树根(即 $R$ 不存在);

1
2
3
4
5
6
7
8
if(r == NULL) {
p->father = NULL; root = p; return;
}
if(q == r->left) {
r->left = p; p->father = r;
} else {
r->right = p; p->father = r;
}

整理一下,不管 Q​ 有无父节点,P 的父节点均修改为 Q 的父节点

1
2
3
4
5
6
p->father = r;
//记录树根
if(r == NULL) { root = p; return; }
//判断P连到R的那颗子树
if(q == r->left) r->left = p;
else r->right = p;

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void right_rotate(node *p) {

node *q = p->father; //记录p的父节点
node *r = q->father; //记录p的父节点的父节点

//操作1
q->left = p->right;
if(p->right != NULL) p->right->father = q;

//操作2
p->right = q; q->father = p;

//维护节点信息(注意此处可暂不维护P)
update(q); //update(p);

//操作3
p->father = r;
if(r == NULL) { root = p; return; }

if(q == r->left) r->left = p;
else r->right = p;
}

2、左旋(Left Rotation)

同理右旋,只是①②不同。

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void left_rotate(node *p) {

node *q = p->father; //记录p的父节点
node *r = q->father; //记录p的父节点的父节点

//操作1
q->right = p->left;
if(p->left != NULL) p->left->father = q;

//操作2
p->left = q; q->father = p;

//维护节点信息
update(q); //update(p);

//操作3
p->father = r;
if(r == NULL){ root = p; return; }

if(q == r->left) r->left = p;
else r->right = p;
}

3、双旋

不断旋转 $X$ 节点,为了保证复杂度,需要连续旋转两次且旋转的次序不同。

定义 $X$ 的父节点为 $Y$,$Y$ 的父节点为 $Z$。

(1)$X$ 和 $Y$ 同时是其父节点的左子树或者同时是各自父节点的右子树(即同侧)。

这时我们要进行两次旋转,先旋转 $Y$,再旋转 $X$

2.png

同左旋转演示图如下:

3.png

同右旋转演示图如下:

4.png

(2)$X$ 和 $Y$ 是其父节点的左、右子树,不同侧(即一左一右或一右一左)。

这时我们只要 旋转两次 X​ 即可。

5.png

(3)判断 $X$ 节点如何旋转。

$X$ 是其父节点的左子树则右旋,否则左旋。

$X$ 若是它父节点左子树返回 true,否则返回 false

1
2
3
4
5
6
7
8
9
bool getlr(node *p) {
return (p->father->left == p);
}

//选择合适的旋转方式
void rotate(node *p) {
if(getlr(p)) right_rotate(p);
else left_rotate(p);
}

4、旋转到根

将 $X$ 旋转到根是 splay 的关键,为了保证复杂度,只要对 $X$ 节点操作,操作后就要将其旋转到根。

如何旋转到根:

  • 一步旋转就可以到根,进行单旋;

  • 两步或两步以上,可以不断使用双旋。

设计函数 splay(p,q) 将 $P$ 旋转到 $Q$ 下方

  • q == NULL 表示 $P$ 旋转到了根;
  • while $P$ 至少两次旋转才能到达:双旋;
  • if $P$ 还差一步满足条件:单旋。

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void splay(node *p, node *tar) {

while(p->father != tar and p->father->father != tar) {
if(getlr(p) == getlr(p->father)) {
rotate(p->father); rotate(p);
} else {
rotate(p); rotate(p);
}
}

if(p->father != tar) rotate(p);

update(p); //优化(避免重复维护)
}
发布于

2019-07-27

更新于

2023-01-11

许可协议

评论