Treap

Tree와 Heap의 합성어인 Treap은 확률적인 BST이다.

Red-Black Tree, AVL Tree 등은 모든 연산에서 O(log N)의 시간복잡도를 보인다.

Splay Tree 등은 평균적으로, amortized O(log N)의 시간복잡도를 보인다.

Treap은 평균적으로 O(log N)이나, 최악의 경우 O(N)의 시간복잡도를 가진다.

이는 Problem Solving에서 생각보다 유용한데, 대부분의 데이터는 랜덤하게 만들기 때문에 최악의 경우가 나오기 쉽지 않다.

또한 이러한 Treap이나, 문자열의 hashing같은 경우 푸는 사람들이 사용할 소수나 알고리즘을 예측할 수 없기 때문에 임의로 최악의 경우를 만들기도 힘들다.

이제 treap이 무엇인지 설명하겠다.

Treap이란 Binary Search Tree의 일종으로, 각 노드에 '우선순위(priority)'가 정해져있다.

BST의 일종이기 때문에 검색은 다른 BST와 같이 하면 되고, 삽입/삭제 또한 유사하다.

그러나 treap만의 특징은,

모든 노드에 대해 자신의 priority는 자식들의 priority보다 작다는 heap의 성질을 만족한다.

삽입/삭제 시 이러한 조건이 만족되도록 노드들을 회전(rotation)해주는 과정이 핵심이다.

이러한 우선순위를 정할 때, 순서대로 1,2,3 이런 식으로 주면 최악의 경우 O(N)이 될 수 있기 때문에,

pseudo-random하게 정해주면 높은 확률로 O(lg N)이 된다.

아래는 구현체이다.

node에서 부모로 향하는 포인터를 일부러 주지 않고, 재귀로 구현해보았다.

자식 노드가 바뀌는 일을 처리하기 위해 chf라는 변수를 정의하여,

'이 노드가 있던 위치에는 새로운 노드가 와야 한다'라는 내용을 지정했다.

같은 원소가 여러 개 삽입될 수 있는지, 그 때의 lower bound는 어떻게 되는지, 아직 불확실하게 구현하긴 했지만, 전체적으로 이런 느낌이구나 하는 것은 알 수 있었다.

template<typename T> struct node {
    T value;
    int pr;
    node *l, *r;
    bool chf;
    node *newnode;
    node(T v){
        value=v;
        pr=nextP();
        l=r=0;
        chf=false;
    }
    ~node(){
        if(l) delete l;
        if(r) delete r;
    }
};

template<typename T> struct bst {
    node<T> *root;
    bst(){
        root=0;
    }
    void insert(T x,node<T> *pos){
        if(pos->value <= x){
            if(pos->r){
                insert(x,pos->r);
                if(pos->r->chf) pos->r->chf=false, pos->r=pos->r->newnode;
            } else {
                pos->r=new node<T>(x);
            }
            if(pos->pr > pos->r->pr){
                node<T>* np=pos->r;
                pos->r=np->l;
                np->l=pos;
                pos->chf=true;
                pos->newnode=np;
            }
        } else {
            if(pos->l){
                insert(x,pos->l);
                if(pos->l->chf) pos->l->chf=false, pos->l=pos->l->newnode;
            } else {
                pos->l=new node<T>(x);
            }
            if(pos->pr > pos->l->pr){
                node<T>* np=pos->l;
                pos->l=np->l;
                np->l=pos;
                pos->chf=true;
                pos->newnode=np;
            }
        }
    }
    void insert(T x){
        if(root==0) root=new node<T>(x);
        else {
            insert(x,root);
            if(root->chf){
                root->chf=false;
                root=root->newnode;
            }
        }
    }
    ~bst(){
        delete root;
    }
    node<T>* lower_bound(T x,node<T>* pos){
        if(pos->value <= x){
            if(pos->r == 0) return 0;
            else {
                return lower_bound(x,pos->r);
            }
        } else {
            if(pos->l == 0) return pos;
            else {
                node<T> *tmp = lower_bound(x,pos->l);
                if(tmp) return tmp;
                else return pos;
            }
        }
    }
    node<T>* lower_bound(T x){
        return lower_bound(x,root);
    }
};

R-B tree, AVL tree와 비교되는 장점으로는 구현이 간단하다는 것이 있다.

직접 구현해보니 재밌었다. Splay Tree도 다음에 구현해봐야지.