트립이란

이진 검색 트리는 한 쪽으로 쏠린 형태가 되면 비효율적인 연산이 나타나게 된다. 레드 블랙 트리와 AVL트리 같이 복잡한 트리 구조를 설계하면 항상 일정한 균형성을 보장한 이진 검색 트리를 만들 수 있다. 그러나 이는 실제로 설계하기 매우 어려우므로 가장 간단한 구조로 균형성을 보장하는 이진 검색 트리가 트립이다.
C++의 표준 라이브러리에는 map, set 클래스가 있는데, 이 클래스들은 레드 블랙 트리로 만들어진 구조기 때문에 균형성이 있고 쉽게 사용할 수 있다. 그러나 이 클래스들은 특정 위치의 원소를 찾거나 특정 값보다 작은 값을 가진 원소의 수를 세는 것과 같은 연산을 제공하지 않는다. 알고리즘 문제 해결 과정에서 이러한 연산이 필요할 때가 있는데, 트립은 이러한 연산을 제공하기 때문에 유용하다.

트립의 구현

typedef int KeyType;

struct Node {
    KeyType key;
    int priority, size;
    Node* left, *right;
    Node(const KeyType& _key) : key(_key), priority(rand()), size(1), left(NULL), right(NULL){}
    void setLeft(Node* newLeft) { left = newLeft; calcSize(); }
    void setRight(Node* newRight) { right = newRight; calcSize(); }
    void calcSize() {
        size = 1;
        if (left) size += left->size;
        if (right) size += right->size;
    }
};

기본적인 이진 검색 트리의 노드 원소 이외에도 트립의 노드는 priority, size값을 갖는데, 이는 균형잡힌 구조를 만들어 주고 특정 원소의 위치를 찾는데 사용된다.
priority의 경우 랜덤하게 생성되는데 priority를 기준으로 노드의 위치가 결정된다. 부모 노드는 반드시 자식 노드에 비해 높은 priority를 가지고 있어야 한다. 따라서 랜덤으로 부여되는 priority 때문에 균형잡힌 구조가 만들어질 가능성이 훨씬 높아진다.

struct의 생성자로 주어진 key값, 랜덤으로 부여된 priority, 자기 자신을 루트로 하는 size 1이 설정된 모습을 볼 수 있다.

트립 함수

노드 삭제와 합치기