抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

Hello World

人よ、幸福に生きろ！

博客

归档

分类

标签

源码

生活在树上

字数：3.5k 字

时长：15 分钟
cpp

发布于：2024年5月19日

次浏览

二叉搜索树

Treap树

  • 每个结点有2个值
    1. 键值：value
    2. 优先级：priority

value要满足BST的基本性质，priority用于满足堆的性质，用来实现二叉树的平衡

  • Treap通过随机化的priority属性,以及维护堆性质的过程，[打乱]了结点的插入顺序。从而让二叉搜索树达到了理想的复杂度，避免了退化成链的问题
  • 利用Treap可以实现一个名次树而且比红黑树好写很多，在算法竞赛中很常用

结点结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
struct Node {
  Node *ch[2];// ch[0]左树的指针，ch[1]右树的指针
  int val, rank;
  int rep_cnt;// val出现的次数
  int siz;// 结点树的大小

  Node(int val) : val(val), rep_cnt(1), siz(1) {
    ch[0] = ch[1] = nullptr;
    rank = rand();
  }

  void upd_siz() {
    siz = rep_cnt;
    if (ch[0] != nullptr) siz += ch[0]->siz;
    if (ch[1] != nullptr) siz += ch[1]->siz;
  }
};

旋转

旋转操作的含义：

  • 在不影响搜索树的性质的前提下，把和旋转方向相反的子树变成根结点。
  • 将新的根结点的子树变为旧根结点的子树
  • 这里使用一个temp存新的根结点，并且最后要更改引用
1
2
3
4
5
6
7
8
9
enum rot_type { LF = 1, RT = 0 };

void _rotate(Node *&cur, rot_type dir) {
  Node *tmp = cur->ch[dir];// 把和旋转方向相反的子结点变成根结点
  cur->ch[dir] = tmp->ch[!dir];// 将新的根结点的子树变为旧根结点的子树
  tmp->ch[!dir] = cur;// 新子树放到与旋转相同方向的根结点，从而完成旋转操作
  cur->upd_siz(), tmp->upd_siz();
  cur = tmp;
}

插入

插的过程中通过旋转来维护树堆中堆的性质,旋转完成后要更新结点大小

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void _insert(Node *&cur, int val) {
  if (cur == nullptr) {
    cur = new Node(val);
    return;
  } else if (val == cur->val) {
    cur->rep_cnt++;
    cur->siz++;
  } else if (val < cur->val) {
 
    _insert(cur->ch[0], val);
    if (cur->ch[0]->rank < cur->rank) {
    	 	      // 利用rank维护小根堆性质
      _rotate(cur, RT);// 要把左结点转上来，需要右旋
    }
    cur->upd_siz();
  } else {
    _insert(cur->ch[1], val);
    if (cur->ch[1]->rank < cur->rank) {
      _rotate(cur, LF);
    }
    cur->upd_siz();
  }
}

删除

注意更新结点大小，思路和插入差不多

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
void _del(Node *&cur, int val) {
	// 每次递归都要重新更新size
  if (val > cur->val) {
    _del(cur->ch[1], val);
    cur->upd_siz();
  } else if (val < cur->val) {
    _del(cur->ch[0], val);
    cur->upd_siz();
  } else {
    if (cur->rep_cnt > 1) {
      cur->rep_cnt--, cur->siz--;
      return;
    }
    uint8_t state = 0;
    state |= (cur->ch[0] != nullptr);
    state |= ((cur->ch[1] != nullptr) << 1);
    Node *tmp = cur;
    switch (state) {
      case 0:
        delete cur;
        cur = nullptr;
        break;
      case 1:
        cur = tmp->ch[0];
        delete tmp;
        break;
      case 2:
        cur = tmp->ch[1];
        delete tmp;
        break;
      case 3:
        rot_type dir = cur->ch[0]->rank < cur->ch[1]->rank ? RT : LF;// 把优先级更小的儿子转上去
        _rotate(cur, dir);
        _del(cur->ch[!dir], val);// 旋转完成后删除旧节点(位于根节点的旋转方向的子节点)
        cur->upd_siz();
        break;
    }
  }
}

根据值查询排名

查询以 cur 为根节点的子树中，val 这个值的大小的排名（该子树中小于 val 的节点的个数 + 1）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int _query_rank(Node* cur, int val) {
  int less_siz =
      cur->ch[0] == nullptr ? 0 : cur->ch[0]->siz;  // 在BST中，左儿子比父节点小
  if (cur->val == val)
    return less_siz + 1;
  else if (cur->val > val) {
    if (cur->ch[0] != nullptr)
      return _query_rank(cur->ch[0], val);
    else
      return 1;  // 没有比它小的了
  } else {
    if (cur->ch[1] != nullptr)
      // 如果要查的值比这个节点大，那这个节点的左子树以及这个节点自身肯定都比要查的值小
      // 所以要加上这两个值，再加上往右边找的结果
      // （以右子树为根的子树中，val 这个值的大小的排名）
      return less_siz + cur->cnt + _query_rank(cur->ch[1], val);
    else
      return cur->siz + 1;  // 没有右子树
  }
}

根据排名查询值

直接递归，和BST搜索的写法差不多

  • 排名<=左子树的大小，则搜索左子树
  • 排名>=左子树的大小 + 根结点的重复次数，则搜索右子树
1
2
3
4
5
6
7
8
9
int _query_val(Node *cur, int rank) {
  int less_siz = cur->ch[0] == nullptr ? 0 : cur->ch[0]->siz;
  if (rank <= less_siz)
    return _query_val(cur->ch[0], rank);
  else if (rank <= less_siz + cur->rep_cnt)
    return cur->val;
  else
    return _query_val(cur->ch[1], rank - less_siz - cur->rep_cnt);
}

查询第一个比 val 小的节点

全局变量，q_prev_tmp
是只有在 val 比当前节点值大的时候才会被更改的，所以返回这个变量就是返回 val 最后一次比当前节点的值大，之后就是更小了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int _query_prev(Node *cur, int val) {
  if (val <= cur->val) {
  	// 往左子树找
    if (cur->ch[0] != nullptr) return _query_prev(cur->ch[0], val);
  } else {
  	// 只有能进到这个 else 里，才会更新 q_prev_tmp 的值
    q_prev_tmp = cur->val;
    // 因为要确定最大的，所以要到右子树继续找
    if (cur->ch[1] != nullptr) _query_prev(cur->ch[1], val);
	// 接下来的递归可能不会更改 q_prev_tmp
    // 了，那就直接返回最后一次进到 这个 else 中的
    // cur->val
    return q_prev_tmp;
  }
  return -1;
}

查询第一个比 val 大的节点

1
2
3
4
5
6
7
8
9
10
int _query_nex(Node *cur, int val) {
  if (val >= cur->val) {
    if (cur->ch[1] != nullptr) return _query_nex(cur->ch[1], val);
  } else {
    q_nex_tmp = cur->val;
    if (cur->ch[0] != nullptr) _query_nex(cur->ch[0], val);
    return q_nex_tmp;
  }
  return -1;
}

Splay树

理论

通常在任意数据结构的生命期内，不仅执行不同操作的概率往往极不均衡，而且各操作之间具有极强的关联性，并在整体上多呈现出极强的规律性。其中最为典型的，就是所谓的“数据局部性”，即：

(1) 刚刚被访问过的元素，极有可能在不久之后再次被访问到
(2) 将被访问的下一元素，极有可能就处于不久之前被访问过的某个元素附近

就BST而言，数据局部性具体表现为：

(1) 刚刚被访问过的节点，极有可能在不久的之后访问到
(2) 将被访问的下一节点，极有可能就处于不久之前被访问过的节点的附近

因此，只需将刚被访问过的节点，及时地”转移“至树根（附近），即可加速后续的操作。Splay树应运而生

对比Splay和Treap:

(1) Splay树允许把任意节点旋转到根
(2) 需要分裂和合并时，Splay树的操作非常简便

结构与操作

每一次查询后都要splay

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
int root;             // 根节点
int ch[N][2], fa[N];  // 子节点/父节点
int val[N];           // 权值
int size[N];          // 子树大小
int cnt[N];           // 重复次数
int tot;              // 节点个数

struct Splay {
  // 维护子树大小
  void maintain(int x);

  // 查找这个节点是父亲的左子树还是右子树
  bool get(int x);

  // 销毁这个节点
  void clear(int x);

  // 旋转
  void rotate(int x);

  // 伸展操作
  void splay(int x);

  // 插入v
  void insert(int v);

  // 查询值为v的数排名
  int find_rank(int v);

  // 查询排名为r的数
  int find_val(int r);

  // 查询根节点的前驱
  int pre();

  // 查询根节点的后继
  int next();

  // 删除一个值为val的数
  void del(int v);

} tree;

基本操作

1
2
3
4
5
6
7
8
9
10
11
12
void Splay::maintain(int x) {
  size[x] = size[ch[x][0]] + size[ch[x][1]] + cnt[x];
}

bool Splay::get(int x) {
  // 左儿子返回0.右儿子返回1
  return x == ch[fa[x]][1];
}

void Splay::clear(int x) {
  ch[x][0]=ch[x][1]=fa[x]=val[x]=size[x]=cnt[x]=0;
}

旋转

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 节点x上升一位
void Splay::rotate(int x) {
  // 右儿子的父亲左移，左儿子的父亲右移
  // 设父亲为y，祖父为z
  int dir = get(x);
  int y = fa[x], z = fa[y];
 
  // 先杀皇帝再让太子继位，然后再供奉祖宗牌匾
  ch[y][dir] = ch[x][!dir];
  if (ch[y][!dir]) fa[ch[x][!dir]] = y;
  ch[x][!dir] = y;
  fa[y] = x;
  fa[x] = z;
  if (z) ch[z][y == ch[z][1]] = x;
  
  // 先维护儿子，再维护父亲
  maintain(y);
  maintain(x);
  
}

伸展

1
2
3
4
5
6
7
8
void Splay::splay(int x) {
  // 设父亲为y,祖父为z
  // 若儿子种类相同，则先转祖父，再转父亲
  // 若儿子种类不同，则先转父亲，再转祖父
  for (int i = fa[x]; i = fa[x], i; rotate(x))
    if (fa[f]) get(x) == get(i) ? rotate(i) : rotate(x);
  root = x;
}

插入

依然是三种情况：

  • 空树nullptr
  • 重复的值，直接cnt++然后伸展
  • 没有，则按照BST插入后伸展

这里数组的下标用tot标记，即元素的插入顺序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
void Splay::insert(int v) {
  if (!root) {
    val[++tot] = val;
    cnt[tot] = size[tot] = 1;
    root = tot;
    return;
  } 
  else {
    int cur = root, i = 0;
    while (1) {
      if (val[cur] == v) {
        cnt[cur]++;
        maintain(cur);
        maintain(i);
        splay(cur);
        return;
      }
      i = cur;
      cur = ch[cur][val[cur] < v];
      if (cur == 0) {
        tot++;
        val[tot] = v;
        cnt[tot]++;
        fa[tot] = i;
        ch[x][val[x] < v] = tot;
        maintain(tot);
        maintain(x);
        splay(tot);
        return;
      }
    }
  }
}

查询值为v的数的排名

经典回顾：

  • 如果 x 比当前节点的权值小，向其左子树查找。
  • 如果 x 比当前节点的权值大，将答案加上左子树（size）和当前节点（cnt）的大小，向其右子树查找。
  • 如果 x 与当前节点的权值相同，将答案加 1 并返回。

最后要进行splay

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int Splay::find_rank(int v) {
  int ans = 0, cur = root;
  while (1) {
    if (v < val[cur])
      cur = ch[cur][0];
    else {
      ans += size[ch[cur][0]];
      if(!cur)return ans+1;
      if (v == val[cur]) {
        splay(cur);
        return ans + 1;
      }
      ans += cnt[cur];
      cur = ch[cur][1];
    }
  }
}

查询排名为r的数

经典回顾：

  • 如果左子树非空且剩余排名 r 不大于左子树的大小 size，那么向左子树查找。
  • 否则将 r 减去左子树的和根的大小。如果此时 r 的值小于等于 0，则返回根节点的权值，否则继续向右子树查找。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int Splay::find_val(int r) {
  int cur = root;
  while (1) {
    if (ch[cur][0] != 0 && r <= size[ch[cur][0]])
      cur = ch[cur][0];
    else {
      r -= cnt[cur] + size[ch[cur][0]];
      if (r <= 0) {
        splay(cur);
        return val[cur];
      }
      cur = ch[cur][1];
    }
  }
}

查询前驱

前驱定义为小于 x 的最大的数，那么查询前驱可以转化为：将 x 插入（此时 x 已经在根的位置了），前驱即为 x 的左子树中最右边的节点，最后将 x 删除即可。

这里插入和删除操作请自行添加

1
2
3
4
5
6
7
8
9
10
11
int Splay::pre()
{
	int cur = ch[root][0];
	if( cur == 0 )
		return cur;
	while( ch[cur][1] )
		cur = ch[cur][1];
	
	splay(cur);
	return cur;
}

查询后继

这里插入和删除操作请自行添加

1
2
3
4
5
6
7
8
9
10
11
int Splay::next()
{
	int cur = ch[root][1];
	if( cur == 0 )
		return cur;
	while( ch[cur][0] )
		cur = ch[cur][0];
	
	splay(cur);
	return cur;
}

合并

  1. 对于合并两棵树，其中一棵树的值都小于另一棵树的值。
  2. 我们可以找到较小一棵树的最大值 x ，将其旋转到根节点。
  3. 再把较大一棵树作为 x 的右子树插入。

删除

  1. 首先将 x 转移到根节点
  2. 若 x 值不只一个，直接cnt[x]–
  3. 否则将它的左右子树合并
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
void Splay::del(int v){
	
	find_rank(v);//splay
	
	if(cnt[root]>1){
		cnt[root]--;
		maintain(root);
		return;
	}
	
	if((ch[root][0]==0)&&(ch[root][1]==0)){
		clear(root);
		root = 0;
		return;
	}
	
	if(ch[root][0]==0){
		int cur = root;
		root = ch[root][1];
		fa[root]=0;
		clear(cur);
		return;
	}
	
	if(ch[root][1]==0){
		int cur = root;
		root = ch[root][0];
		fa[root]= 0;
		clear(cur);
		return;
	}
	
	int cur = root;
	int x = pre();//splay
	
	//merge
	fa[ch[cur][1]] = x;
	ch[x][1] = ch[cur][1];
	clear(cur);
	
	maintain(root);
	
	return;
}

序列操作

按照序列建成的Splay有以下性质:

  • Splay的中序遍历相当于原序列从左到右的遍历
  • Splay上的一个节点代表序列的一个元素；Splay上的一颗子树，代表原序列的一段区间

利用Splay操作，可以快速提取出代表某个区间的Splay的子树

具体操作：
Splay 的一颗子树代表原序列的一段区间。现在想找到序列区间 [L, R] 代表的子树，只需要将代表 aL−1a_{L - 1} 的节点 Splay 到根，再将代表 aR+1a_{R + 1}的节点 splay 到根的右儿子即可。根据「Splay 的中序遍历相当于原序列从左到右的遍历」，对应 aR+1a_{R + 1} 的节点的左子树中序遍历为序列 a[L, R]，故其为区间 [L, R] 代表的子树。

一般会建立左右两个哨兵节点 0 和 n + 1，放在数列的最开头和最结尾，防止 L - 1 或 R + 1 超出数列范围。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void Splay::splay(int x, int goal = 0) {
  // 如果目标点 goal 为 0 说明旋转到根节点
  if (goal == 0) root = x;

  // 设父亲为y,祖父为z
  // 若儿子种类相同，则先转祖父，再转父亲
  // 若儿子种类不同，则先转父亲，再转祖父
  while (fa[x] != goal) {
    int i = fa[x], g = fa[i];
    if (g != goal) {
      get(i) == get(x) ? rotate(i) : rotate(x);
    }
    rotate(x);
  }
}

区间翻转

  • 一个暴力做法是每次将根节点的左右儿子交换，然后递归左右子树做同样的操作，这样复杂度为 O(n)，不可承受。
  • 可以考虑使用懒标记，先给根打上「翻转标记」并交换其左右儿子。当递归到一个带懒标记的点时，将懒标记下传即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void Splay::tagrev(int v){
	swap(ch[v][0],ch[v][1]);
	lazy[v] ^= 1;
}

void Splay::pushdown(int v){
	if(lazy[v]){
		tagrev(ch[v][0]);
		tagrev(ch[v][1]);
		lazy[v] = 0;
	}
}

void Splay::reverse(int l, int r){
	int L = find_val(l-1), R = find_val(r+1);
	splay(L), splay(R, L);
	int temp = ch[ch[L][1]][0];
	tagrev(temp);
}

将Splay用于需要区间翻转的区间维护

对于区间反转这种操作，由于原数列的顺序已经给定，所以不能按照权值排序，所以选择按照的点的编号建立BST

鸽了(我写不出来

多叉搜索树

B树

更新于：2024年5月28日

算法

评论