一、旋转(Zig - Zag)

1. 右旋(Right Rotation)

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

1.png

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

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

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

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

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

修改如下:

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

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

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

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

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

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

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

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

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

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 的父节点

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

Code :

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 :

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

bool getlr(node *p) {
    return (p->father->left == p);
}
  
//选择合适的旋转方式
void rotate(node *p) {
    if(getlr(p)) right_rotate(p); 
    else left_rotate(p);
}

二、旋转到根

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

如何旋转到根:

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

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

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

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

Code :

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);  //优化(避免重复维护)
}