대회에서는 BBST 짤 일이 크게 3가지가 있는데


(1) merge, split이 필요한 경우
(2) k-th, lazy propagation이 필요한 경우
(3) 대회에서 사용하지 못하게 하는 경우 (삼성)


(2)는 RB, AVL 같은 걸 짤 수 있다면 짜도 되지만, (1)은 해당 연산을 효율적으로 해주는 특별한 BBST를 짜야함.
그런데 (1)을 만족하는 자료구조는 보통 (2)도 쉽게 구현할 수 있음, 즉 RB, AVL을 따로 배울 필요가 없다는 이야기.
대회에서는, 속도가 중요하지 않으면 코딩이 편한 Treap을, 속도가 빨라야 하거나 parent가 필요하면 Splay tree를 짠다.


Treap은 무작위의 성질을 이용해서 BST를 최대한 Balanced하게 만드는 자료구조임.
각 노드는 random number를 하나 들고 있어서, random number는 max-heap 순서를 따르고, 그냥 숫자는 BST 순서를 따르게 하는 거임
이러면 좋은 점이 merge와 split을 매우 쉽게 작성할 수 있음.


일단 node를 작성해보자.


struct node {
    node *l, *r;
    int val;
    uint32_t t;

    node() = default;
    node(int v) : val(v) {
        l = r = nullptr;
        t = rng();
    }
    ~node() {
        delete l;
        delete r;
    }
};
typedef node *pnode;


그리고 merge와 split을 재귀적으로,


pnode treap_merge(pnode left, pnode right) {
    if (!left) return right;
    if (!right) return left;
    if (left->t > right->t) {
        left->r = treap_merge(left->r, right);
        return left;
    }
    right->l = treap_merge(left, right->l);
    return right;
}

void treap_split(pnode root, int k, pnode &left, pnode &right) {
    if (!root) {
        left = nullptr;
        right = nullptr;
    } else if (root->val < k) {
        treap_split(root->r, k, root->r, right);
        left = root;
    } else {
        treap_split(root->l, k, left, root->l);
        right = root;
    }
}


이걸 이용해서 insert와 remove를,


class Treap {
    pnode root = nullptr;
public:
    void insert(int p) {
        pnode left, right;
        treap_split(root, p, left, right);
        root = treap_merge(treap_merge(left, new node(p)), right);
    }

    void remove(int p) {
        pnode left, mid, right;
        treap_split(root, p, left, mid);
        treap_split(mid, p + 1, mid, right);
        root = treap_merge(left, right);
        delete mid;
    }
};


이런식으로 100줄도 안되는 편안함으로 BBST를 작성할 수 있다.


전체 코드: https://gist.github.com/0xrgb/b9cf9f752cf94f5e917c0b8758492d30