二叉搜索树

二叉搜索树是一种二叉树的树形数据结构，其定义如下：

• 空树是二叉搜索树。
• 若二叉搜索树的左子树不为空，则其左子树上所有点的附加权值均小于其根节点的值。
• 若二叉搜索树的右子树不为空，则其右子树上所有点的附加权值均大于其根节点的值。
• 二叉搜索树的左右子树均为二叉搜索树。

二叉搜索树上的基本操作所花费的时间与这棵树的高度成正比。对于一个有 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;
}