非旋转Treap

非旋转Treap

通过节点的优先级来维护树的平衡, 下面是普通非旋转Treap (弱平衡,

性质

  1. Treap是笛卡尔树的一种,只是 节点优先级是随机的
  2. $Tree+Heap$: 二叉搜索树+堆的性质
  3. 2个核心操作 分裂+合并

分裂 split

按照 节点权值分裂或者值的排名分裂

  1. $split_val$

    将一颗treap分裂成2个treap,第一个treap所有节点的权值$\le key$ , 第二个treap所有节点的权值$\gt key$

    判断节点权值$val[index]$ 是否 $\le key$,

    1. 若$val[index]\le key$,则第一个$treap$就是 $index$及其左子树, 但右子树可能还有节点权值$\le key$,所以再去$index$的右子树去分裂
    2. 若$val[index] \gt key$,则第二个$treap$就是$index$及其右子树.但左子树可能还有节点权值$\gt key$ ,所以再去$index$左子树去分裂
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    // oi-wiki 上的指针版
    pair<node *, node *> split(node *u, int key) {
      if (u == nullptr) {
        return make_pair(nullptr, nullptr);
      }
      if (key < u->key) {
        pair<node *, node *> o = split(u->lch, key);
        u->lch = o.second;
        return make_pair(o.first, u);
      } else {
        pair<node *, node *> o = split(u->rch, key);
        u->rch = o.first;
        return make_pair(u, o.second);
      }
    }

  2. $split_kth$

    和$split_val$一样, 注意一下去了右子树减去前面所有排名

合并 merge

合并2个$treap$是有顺序的,子树$x$的中序遍历3,5,7,子树$y$的中序遍历1,4,8,那么合并$(x,y)$后$treap$的中序遍历为3,5,7,1,4,8, 将$y$树代表的序列拼接到$x$树代表的序列

为了保持平衡, 根据节点的优先级来合并

例如$merge(x,y)$,判断节点的优先级$priority$

  1. $priority[x] < priority[y]$ ,那么$x$作为根节点，$y$和$x$的右子树去合并 (因为$y$要接在$x$序列后面,根据中序遍历的性质,所有要去$x$的右子树)
  2. $priority[x] \ge priority[y]$,那么$y$作为根节点, $x$和$y$的左子树去合并,(因为中序遍历的性质,去$y$的左子树)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// oi-wiki 指针版
node *merge(node *u, node *v) {
  if (u == nullptr) {
    return v;
  }
  if (v == nullptr) {
    return u;
  }
  if (u->priority > v->priority) {
    u->rch = merge(u->rch, v);
    return u;
  } else {
    v->lch = merge(u, v->lch);
    return v;
  }
}

其他操作 (都是基于分裂和合并)

  1. 建树(我现在只会一个一个插入)
  2. $insert(val) = split_val + new_node + merge$
  3. $delete(val) = split_val + split_kth + merge$
  4. $rank(val) = split_val + merge$
  5. $kth(k) = split_kth*2 + merge$
  6. $pre(val) = split_val + split_kth + merge$
  7. $nxt(val) = split_val + split_kth +merge$

Luogu 平衡树

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;

int ch[maxn][2],size[maxn],val[maxn],priority[maxn];
int tot,root;

void maintain(int x) { size[x] = size[ch[x][0]] + size[ch[x][1]] + 1; }

void split_val(int index,int value,int &x,int &y) {
    if (!index) {
        x = y = 0;
        return ;
    }
    if (val[index] <= value) {
        x = index;
        split_val(ch[index][1],value,ch[index][1],y);
    } else {
        y = index;
        split_val(ch[index][0],value,x,ch[index][0]);
    }
    maintain(index);
}

void split_kth(int index,int k,int &x,int &y) {
    if (!index) {
        x = y = 0;
        return ;
    }
    if (k <= size[ch[index][0]]) {
        y = index;
        split_kth(ch[index][0],k,x,ch[index][0]);
    } else {
        x = index;
        split_kth(ch[index][1],k-1-size[ch[index][0]],ch[index][1],y);
    }
    maintain(index);
}

int merge(int x,int y) { // 合并x 和 节点,y接在x后面
    if (!x || !y) return x + y;
    if (priority[x] < priority[y]) {
        // x 作为根节点,要满足中序遍历则,去x的右子树
        ch[x][1] = merge(ch[x][1],y);
        // 回溯时维护大小
        maintain(x);
        return x;
    } else { // y 作为根节点,为了满足中序遍历,x去左子树
        ch[y][0] = merge(x,ch[y][0]);
        maintain(y);
        return y;
    }
}

int new_node(int value) {
    val[++tot] = value;
    size[tot] = 1;
    return tot; // 返回节点编号
}

// 初始化节点的优先级
void init() {
    srand(time(0));
    for (int i=0; i<maxn-1; ++i)
        priority[i] = rand();
}

int n,i,x,r1,r2;

int main() {
    init();
    scanf("%d",&n);
    while (n--) {
        scanf("%d%d",&i,&x);
        if (i == 1) {
            // 在恰当的分裂 合并新的点
            split_val(root,x,root,r1);
            root = merge(root,merge(new_node(x),r1));
        }
        if (i == 2) { // 删除一个x值
            split_val(root,x-1,root,r1);
            split_kth(r1,1,r2,r1);
            root = merge(root,r1);
        }
        if (i == 3) { // x值的排名
            split_val(root,x-1,root,r1);
            printf("%d\n",size[root]+1);
            root = merge(root,r1);
        }
        if (i == 4) { // 查询排名为x的值
            split_kth(root,x-1,root,r1);
            split_kth(r1,1,r1,r2);
            printf("%d\n",val[r1]);
            root = merge(root,merge(r1,r2));
        }
        if (i == 5) { // x 的前驱
            split_val(root,x-1,root,r1);
            split_kth(root,size[root]-1,root,r2);
            printf("%d\n",val[r2]);
            root = merge(root,merge(r2,r1)); // 合并的时候注意r2,r1的顺序
        }
        if (i == 6) { // x 的后继
            split_val(root,x,root,r1);
            split_kth(r1,1,r1,r2);
            printf("%d\n",val[r1]);
            root = merge(root,merge(r1,r2));
        }
    }
    return 0;
}

oi-wiki Treap

%%%% 大佬非旋Treap
杂: 1天+1早上

算法
非旋转Treap

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！