Treap

Harry Huang (aka Wenyuan Huang, 黄问远)
  2024-11-07 01:35:27 2024-11-07 01:35:27 Created   2024-11-27 21:53:28 2024-11-27 21:53:28 Updated      

I will translate this blog to English ASAP.

##前置芝士 熟练掌握二叉查找（排序）树的插入、删除、求排名、求某一排名的数、求前驱、求后继等操作。 #引言 二叉查找树看似可以在 中完成任意上述操作。但若该二叉查找树退化为如下形态：

此时，在此图上操作的时间复杂度仍为 。 观察可知：二叉查找树的最优形态是平衡树，故需要一种能维持树的平衡形态的二叉查找树。

#正文 Treap又名树堆，是一种利用随机性来维持二叉查找树的平衡形态的树（相较于Splay，方便且暴力许多）。 学习Treap，首先需要了解Treap的特色旋转操作（与Splay的旋转有一定差别）。旋转操作在Treap中主要用于在不破坏二叉查找树的性质（左子树比根小，右子树比根大）的情况下，对元素的位置进行挪动。根据所需旋转的节点属于其父亲节点的左子树和右子树，可分为左旋和右旋。
###插入节点 Treap的插入操作与普通的二叉查找树如出一辙，但是为了保持平衡，每个节点会有一个随机值来保证图的形态的随机性。 ###操作步骤 #####1、从根节点开始递归； #####2、如果当前节点的值等于需插入的值，则将该节点的数值数量和该节点的子树的节点数+1； #####3、如果当前节点的值大于需插入的值，则在当前节点的左儿子中继续2、3两步；如果当前节点的值小于需插入的值，则在当前节点的右儿子中继续2、3两步。操作完成后，若子节点的随机值大于当前节点的随机值，则将当前节点向下旋转； #####4、如果当前节点为空节点，则在当前节点中建立新的节点，并赋予新节点一个随机值； ####代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void ins (int &p, int x) {
    if (!p) {
        p = ++ cnt;
        siz[p] = num[p] = 1;
        val[p] = x;
        rd[p] = rand ();
        return ;
    }
    if (val[p] == x) {
        num[p] ++;
        siz[p] ++;
        return ;
    }
    int d = (x > val[p]);
    ins (sons[p][d], x);
    if (rd[p] < rd[sons[p][d]])
        rotate (p, d ^ 1);
    pushup (p);
    return ;
}

###删除节点 删除操作和插入节点的区别在于，需要分类讨论需删除的节点的状态（左儿子存在与否、右儿子存在与否）。

#####情况一：左儿子右儿子都不存在 因为叶子节点的存在不会影响整树的平衡，所以此时可以直接删除该节点； #####情况二：左儿子存在、右儿子不存在 若直接删除节点，有可能影响树的平衡性，所以将当前节点向左儿子旋转； #####情况三：左儿子不存在，右儿子存在 与情况二大同小异，差别是要将当前节点向右儿子旋转； #####情况四：左儿子存在，右儿子存在 此时需要选择旋转左旋还是右旋。显然，若进行左/右旋，则左/右儿子会更替当前节点的位置。故为了维持树的随机性，需要将左儿子和右儿子中随机值大的点向上旋转；

点的遍历操作与插入节点的遍历如出一辙，此处不再赘述。 ####代码 

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
void del (int &p, int x) {
    if (!p)
        return ;
    if (x < val[p])
        del (sons[p][0], x);
    else if (x > val[p])
        del (sons[p][1], x);
    else {
        if (!sons[p][0] && !sons[p][1]) {
            num[p] --;
            siz[p] --;
            if (num[p] == 0)
                p = 0;
        }
        else if (sons[p][0] && !sons[p][1]) {
            rotate (p, 1);
            del (sons[p][1], x);
        }
        else if (!sons[p][0] && sons[p][1]) {
            rotate (p, 0);
            del (sons[p][0], x);
        }
        else if (sons[p][0] && sons[p][1]) {
            int d = (rd[sons[p][0]] > rd[sons[p][1]]);
            rotate (p, d);
            del (sons[p][d], x);
        }
    }
    pushup (p);
    return ;
}
----------------------------------- ###查找某个数的排名 仍然可以使用正常的二叉排序树的一般遍历方式。

###遍历操作 ###情况一：若当前节点的值等于查找的树，则返回当前节点的左子树的数量+1； ###情况二：若当前节点的值小于需查找的值，则返回 需查找的值在右子树的排名+当前节点的左子树的节点数+当前节点的数量； ###情况三：若当前节点的值大于需查找的值，则返回 需查找的值在左子树的排名；

####代码 

1
2
3
4
5
6
7
8
9
10
int ranks (int p, int x) {
    if (!p)
        return 0;
    if (x == val[p])
        return siz[sons[p][0]] + 1;
    if (val[p] < x)
        return siz[sons[p][0]] + num[p] + ranks (sons[p][1], x);
    if (val[p] > x)
        return ranks (sons[p][0], x);
}
---------------------------------------- ###查找某排名的数 本质就是逆向操作“查找某个数的排名”。

####代码 

1
2
3
4
5
6
7
8
9
10
int find (int p, int x) {
    if (!p)
        return 0;
    if (x <= siz[sons[p][0]])
        return find (sons[p][0], x);
    else if (x > siz[sons[p][0]] + num[p])
        return find (sons[p][1], x - siz[sons[p][0]] - num[p]);
    else
        return val[p];
}
-------------------------------------- ###求先驱、后继 过程并不复杂：在遍历过程中不断向需求先驱的数靠近，同时用当前节点的值更新答案。

####代码 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int pre (int p, int x) {
    if (!p)
        return -inf;
    if (val[p] >= x)
        return pre (sons[p][0], x);
    else
        return max (val[p], pre (sons[p][1], x));
}
int suc (int p, int x) {
    if (!p)
        return inf;
    if (val[p] <= x)
        return suc (sons[p][1], x);
    else
        return min (val[p], suc (sons[p][0], x));
}
--------------------------------------------------------------- 完整版代码： 
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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 500, inf = 2000000005;
int n, rt, val[N], siz[N], rd[N], cnt, sons[N][2], num[N];
void pushup (int x) {
    siz[x] = siz[sons[x][0]] + siz[sons[x][1]] + num[x];
    return ;
}
void rotate (int &x, int d) {
    int t = sons[x][d ^ 1];
    sons[x][d ^ 1] = sons[t][d];
    sons[t][d] = x;
    pushup (x);
    pushup (t);
    x = t;
    return ;
}
void del (int &p, int x) {
    if (!p)
        return ;
    if (x < val[p])
        del (sons[p][0], x);
    else if (x > val[p])
        del (sons[p][1], x);
    else {
        if (!sons[p][0] && !sons[p][1]) {
            num[p] --;
            siz[p] --;
            if (num[p] == 0)
                p = 0;
        }
        else if (sons[p][0] && !sons[p][1]) {
            rotate (p, 1);
            del (sons[p][1], x);
        }
        else if (!sons[p][0] && sons[p][1]) {
            rotate (p, 0);
            del (sons[p][0], x);
        }
        else if (sons[p][0] && sons[p][1]) {
            int d = (rd[sons[p][0]] > rd[sons[p][1]]);
            rotate (p, d);
            del (sons[p][d], x);
        }
    }
    pushup (p);
    return ;
}
void ins (int &p, int x) {
    if (!p) {
        p = ++ cnt;
        siz[p] = num[p] = 1;
        val[p] = x;
        rd[p] = rand ();
        return ;
    }
    if (val[p] == x) {
        num[p] ++;
        siz[p] ++;
        return ;
    }
    int d = (x > val[p]);
    ins (sons[p][d], x);
    if (rd[p] < rd[sons[p][d]])
        rotate (p, d ^ 1);
    pushup (p);
    return ;
}
int ranks (int p, int x) {
    if (!p)
        return 0;
    if (x == val[p])
        return siz[sons[p][0]] + 1;
    if (val[p] < x)
        return siz[sons[p][0]] + num[p] + ranks (sons[p][1], x);
    if (val[p] > x)
        return ranks (sons[p][0], x);
}
int find (int p, int x) {
    if (!p)
        return 0;
    if (x <= siz[sons[p][0]])
        return find (sons[p][0], x);
    else if (x > siz[sons[p][0]] + num[p])
        return find (sons[p][1], x - siz[sons[p][0]] - num[p]);
    else
        return val[p];
}
int pre (int p, int x) {
    if (!p)
        return -inf;
    if (val[p] >= x)
        return pre (sons[p][0], x);
    else
        return max (val[p], pre (sons[p][1], x));
}
int suc (int p, int x) {
    if (!p)
        return inf;
    if (val[p] <= x)
        return suc (sons[p][1], x);
    else
        return min (val[p], suc (sons[p][0], x));
}
int main () {
    scanf ("%d", &n);
    for (int i = 1; i <= n; i ++) {
        int op, x;
        scanf ("%d%d", &op, &x);
        if (op == 1)
             ins (rt, x);
        else if (op == 2)
             del (rt, x);
        else if (op == 3)
             printf ("%d\n", ranks (rt, x));
                else if (op == 4)
             printf ("%d\n", find (rt, x));
                else if (op == 5)
             printf ("%d\n", pre (rt, x));
                else if (op == 6)
             printf ("%d\n", suc (rt, x));
    }
    return 0;
}
例题推荐：LOJ #104 普通平衡树

  • Title: Treap
  • Author: Harry Huang (aka Wenyuan Huang, 黄问远)
  • Created at : 2024-11-07 01:35:27
  • Updated at : 2024-11-27 21:53:28
  • Link: https://whuang369.com/blog/2024/11/07/CS/ICPC/Treap/
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments
On this page
Treap