平衡树相关知识：

$小知识：C++的STL中的set容器内部封装为平衡树$

1. 二叉搜索树(BST)

特点：

• $左子树中的元素一定小于根节点，右子树的元素一定大于根节点，若有相同数则用cnt++记忆即可$
• $其中序遍历一定为从小到大排序$

本质：

$动态维护一个有序序列$

时间复杂度：

• $和树的高度成正比，当数据越有序，时间复杂度越差，一般O(logn)最坏O(n),$
  $当数据完全升序或降序时，退化成一条链，时间复杂度O(n)$

用法：

1. $插入$
2. $删除$
3. $找前驱/后继（中序遍历的前一个位置，后一个位置）$
4. $找最大/最小$
5. $某个值(key)的排名（排名：该子树中小于该值key的节点的个数+1)$
6. $排名是rank的数是哪一个$
7. $比某个数(key)小的最大值$
8. $比某个数(key)大的最小值$

$注：STL中的set也支持前4个操作$

2. treap

低压成套开关设备 CCC认证企业技术负责人知识读本

pdf 0星 超过10%的资源 30.76MB

下载

简介：

• $Treap（树堆）是一种弱平衡的二叉搜索树。它同时符合二叉搜索树和堆的性质，$
  $故，其名字也因此为tree（树）和heap（堆）的组合。$

为什么引入treap:

• $treap完全包含BST,且比BST更优$
• $一组数据经过堆的维护可以形成确定唯一的treap结构$

核心思想：

$让BST变得随机,从而避免使时间复杂度维持为O(logn)$

核心操作：

$旋转操作$

$旋转操作的含义：$

• $在不影响搜索树性质的前提下，把和旋转方向相反的子树变成根节点$
  $（如左旋，就是把右子树变成根节点）$
• $不影响性质，并且在旋转过后，跟旋转方向相同的子节点变成了原来的根节点$
  $（如左旋，旋转完之后的左子节点是旋转前的根节点）$
• $例子：$

下面各操作看代码实现即可：

例题：

平衡树基本操作

代码及注释如下：

#include 
#include 
#include 

using namespace std;

const int N = 100010, INF = 1e8;

int n;

struct Node
{
    int l, r;
    int key, val; // 实际的值 堆（大根堆）中的编号（便于打乱）
    int cnt, size; // 此数的数量 该子树中的数的数量
}tr[N];

int root, idx;

// 子节点更新父节点信息
void pushup(int p)
{
    tr[p].size = tr[tr[p].l].size + tr[tr[p].r].size + tr[p].cnt;
}

// 创建新节点
int get_node(int key)
{
    idx ++;
    tr[idx].key = key;
    tr[idx].val = rand();
    tr[idx].cnt = tr[idx].size = 1;
    return idx;
}

void zig(int &p)    // 右旋（将根节点变为左子树）
{
    int q = tr[p].l;
    tr[p].l = tr[q].r, tr[q].r = p, p = q;
    pushup(tr[p].r), pushup(p);
}

void zag(int &p)    // 左旋（将根节点变为右子树）
{
    int q = tr[p].r;
    tr[p].r = tr[q].l, tr[q].l = p, p = q;
    pushup(tr[p].l), pushup(p);
}

// 初始化根节点，同时初始化两个哨兵 -INF 和 INF
void build()
{
    get_node(-INF), get_node(INF);
    root = 1, tr[1].r = 2;
    pushup(root);
    
    if(tr[1].val < tr[2].val) zag(root);
}

void insert(int &p, int key)
{
    if(!p) p = get_node(key); // 树种节点为0，创建新节点即可
    else if(tr[p].key == key) tr[p].cnt ++; // 子树的根节点恰好为key，令 key 的 cnt ++ 即可
    else if(tr[p].key > key) 
    {
        insert(tr[p].l, key); // 递归插入key
        
        // 若新插入的左子树的key > 根节点的key则，右旋，令左子树为根
        if(tr[tr[p].l].val > tr[p].val) zig(p); 
    }
    else 
    {
        insert(tr[p].r, key); // 递归插入key
        
        // 若新插入的右子树的key > 根节点的key则，左旋，令右子树为根
        if(tr[tr[p].r].val > tr[p].val) zag(p);
    }
    pushup(p);
}

// 一直左旋或右旋直到叶子节点，然后删去即可
void remove0(int &p, int key)
{
    if(!p) return ;
    if(tr[p].key == key)
    {
        if(tr[p].cnt > 1) tr[p].cnt --;
        else if(tr[p].l || tr[p].r)
        {
            // 若右节点不存在，或左节点在堆的val > 右节点的val
            if(!tr[p].r || tr[tr[p].l].val > tr[tr[p].r].val)
            {
                // 先右旋，使左节点为根节点保证大根堆
                zig(p); 
                // 此时根节点旋转至右节点，原函数等效于删除右节点
                remove0(tr[p].r, key); 
            }
            else // 若左节点不存在，或右节点在堆的val > 右节点的val
            {
                // 先左旋，使右节点为根节点保证大根堆
                zag(p);
                // 此时根节点旋转至左节点，原函数等效于删除左节点
                remove0(tr[p].l, key);
            }
        }
        else p = 0; // 找到叶子节点p，令其 == 0 即为删除
    }
    else if(tr[p].key > key) remove0(tr[p].l, key); // 没找到递归左子树
    else remove0(tr[p].r, key); // 没找到递归右子树
    
    pushup(p);
}

int get_rank_by_key(int p, int key) // 根据值求排名
{
    if(!p) return 0; // 本题不存在此情况
    if(tr[p].key == key) return tr[tr[p].l].size + 1;
    else if(tr[p].key > key) return get_rank_by_key(tr[p].l, key);
    else return tr[tr[p].l].size + tr[p].cnt + get_rank_by_key(tr[p].r, key);
}

int get_key_by_rank(int p, int rank) // 根据排名求值
{
    if(!p) return INF;
    if(tr[tr[p].l].size >= rank) return get_key_by_rank(tr[p].l, rank);
    else if(tr[tr[p].l].size + tr[p].cnt >= rank) return tr[p].key;
    else return get_key_by_rank(tr[p].r, rank - tr[tr[p].l].size - tr[p].cnt);
}

int get_prev(int p, int key) // 找到严格小于key的数
{
    if(!p) return -INF;
    if(tr[p].key >= key) return get_prev(tr[p].l, key);
    return max(tr[p].key, get_prev(tr[p].r, key));
}

int get_next(int p, int key) // 找到严格大于key的数
{
    if(!p) return INF;
    if(tr[p].key <= key) return get_next(tr[p].r, key);
    return min(tr[p].key, get_next(tr[p].l, key));
}

int main()
{
    build();
    
    scanf("%d", &n);
    
    int opt, x;
    for (int i = 1; i <= n; i ++ )
    {
        scanf("%d%d", &opt, &x);
        if (opt == 1) insert(root, x);
        else if (opt == 2) remove0(root, x);
        else if (opt == 3) printf("%d\n", get_rank_by_key(root, x) - 1); // 初始化哨兵-INF，要 - 1
        else if (opt == 4) printf("%d\n", get_key_by_rank(root, x + 1)); // 有哨兵-INF，要 + 1
        else if (opt == 5) printf("%d\n", get_prev(root, x));
        else printf("%d\n", get_next(root, x));
    }
    
    return 0;
}
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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163