首页 算法

# 一、旋转（Zig - Zag）

# 1. 右旋（Right Rotation）

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

1.png

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

# （1）QQ 的左子树修改为 PP 的右子树的内容

即 BB 成为 QQ 的左子树， BB 的父节点是 QQ 。

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

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

修改如下：

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

# （2）PP 的右子树修改为 QQ ，且同时 QQ 的父节点修改为 PP 。

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

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

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

# （3）RR 的子树应该修改为 PP

需要判断 QQ 是 RR 的哪种子树，左子树则 PP 给 RR 的左子树，否则给右子树。

全局变量 rootroot 记录树根。

特判 QQ 有可能就是树根（即 RR 不存在）；

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、双旋
不断旋转 XX 节点，为了保证复杂度，需要连续旋转两次且旋转的次序不同。
定义 XX 的父节点为 YY，YY 的父节点为 ZZ。
# （1）XX 和 YY 同时是其父节点的左子树或者同时是各自父节点的右子树（即同侧）。
这时我们要进行两次旋转，先旋转 YY，再旋转 XX。
2.png
同左旋转演示图如下：
3.png
同右旋转演示图如下：
4.png
# （2）XX 和 YY 是其父节点的左、右子树，不同侧（即一左一右或一右一左）。
这时我们只要 旋转两次 X​ 即可。
5.png
# （3）判断 XX 节点如何旋转。
XX 是其父节点的左子树则右旋，否则左旋。
XX 若是它父节点左子树返回 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);
}
# 二、旋转到根
将 XX 旋转到根是 splay 的关键，为了保证复杂度，只要对 XX 节点操作，操作后就要将其旋转到根。
如何旋转到根：
  • 一步旋转就可以到根，进行单旋；
  • 两步或两步以上，可以不断使用双旋。
设计函数 splay(p,q) 将 PP 旋转到 QQ 下方。
  • q == NULL 表示 PP 旋转到了根；
  • while PP 至少两次旋转才能到达：双旋；
  • if PP 还差一步满足条件：单旋。
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);  // 优化（避免重复维护）
}
  
 更新于