二叉搜索树
二叉搜索树是一种二叉树的树形数据结构,其定义如下:
- 空树是二叉搜索树。
- 若二叉搜索树的左子树不为空,则其左子树上所有点的附加权值均小于其根节点的值。
- 若二叉搜索树的右子树不为空,则其右子树上所有点的附加权值均大于其根节点的值。
- 二叉搜索树的左右子树均为二叉搜索树。
二叉搜索树上的基本操作所花费的时间与这棵树的高度成正比。对于一个有 N 个结点的二叉搜索树中,这些操作的最优时间复杂度为 O(log n) ,最坏为 O(n) 。随机构造这样一棵二叉搜索树的期望高度为 O(log n) 。
替罪羊树
替罪羊树 是一种依靠重构操作维持平衡的重量平衡树。替罪羊树会在插入、删除操作时,检测途经的节点,若发现失衡,则将以该节点为根的子树重构。
Treap
treap 是一种弱平衡的二叉搜索树。treap 这个单词是 tree 和 heap 的组合,表明 treap 是一种由树和堆组合形成的数据结构。treap 的每个结点上要额外储存一个值 priority 。treap 除了要满足二叉搜索树的性质之外,还需满足父节点的 priority 大于等于两个儿子的 priority 。而 priority 是每个结点建立时随机生成的,因此 treap 是期望平衡的。
模板代码:
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
#define MAXN 500005
inline int read()
{
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
int ch[MAXN][2], val[MAXN], pri[MAXN], siz[MAXN], sz;
void update(int x)
{
siz[x] = 1 + siz[ch[x][0]] + siz[ch[x][1]];
}
int new_node(int v)
{
siz[++sz] = 1;
val[sz] = v;
pri[sz] = rand();
return sz;
}
int merge(int x, int y)
{
if (!x || !y)
return x + y;
if (pri[x] < pri[y])
{
ch[x][1] = merge(ch[x][1], y);
update(x);
return x;
}
else
{
ch[y][0] = merge(x, ch[y][0]);
update(y);
return y;
}
}
void split(int now, int k, int &x, int &y)
{
if (!now)
x = y = 0;
else
{
if (val[now] <= k)
x = now, split(ch[now][1], k, ch[now][1], y);
else
y = now, split(ch[now][0], k, x, ch[now][0]);
update(now);
}
}
int kth(int now, int k)
{
while (1)
{
if (k <= siz[ch[now][0]])
now = ch[now][0];
else if (k == siz[ch[now][0]] + 1)
return now;
else
k -= siz[ch[now][0]] + 1, now = ch[now][1];
}
}
int main()
{
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
srand(6926666);
int n, com, x, y, z, a, b, root = 0;
scanf("%d", &n);
while (n--)
{
com = read(), a = read();
if (com == 1)
{
split(root, a, x, y);
root = merge(merge(x, new_node(a)), y);
}
else if (com == 2)
{
split(root, a, x, z);
split(x, a - 1, x, y);
y = merge(ch[y][0], ch[y][1]);
root = merge(merge(x, y), z);
}
else if (com == 3)
{
split(root, a - 1, x, y);
printf("%d\n", siz[x] + 1);
root = merge(x, y);
}
else if (com == 4)
printf("%d\n", val[kth(root, a)]);
else if (com == 5)
{
split(root, a - 1, x, y);
printf("%d\n", val[kth(x, siz[x])]);
root = merge(x, y);
}
else
{
split(root, a, x, y);
printf("%d\n", val[kth(y, 1)]);
root = merge(x, y);
}
}
return 0;
}