이진 검색 트리 구현

typedef int KeyType;

struct Node {
    KeyType key;
    Node* left, *right;
    int priority;
    int size;
    Node(const KeyType& _key) :key(_key), left(NULL), right(NULL), priority(rand()), size(1), {

    }
    void setLeft(Node *newLeft) {
        left=newLeft;
        countSize();
    }
    void setRight(Node* newRight) {
        right = newRight;
        countSize();
    }
    void countSize() {
        size = 1;
        size += left->size;
        size += right->size;
    }
};

typedef pair<Node*, Node*> NodePair;

NodePair split(Node* root, KeyType key) {
    if (root == NULL)return NodePair(NULL, NULL);

    if (root->key < key) {
        NodePair rs = split(root->right, key);
        root->setRight(rs.first);
        return NodePair(root, rs.second);
    }
    NodePair ls = split(root->left, key);
    root->setLeft(ls.second);
    return NodePair(ls.first, root);

}

Node* insert(Node* root, Node* node) {

    if (root == NULL)return node;

    if (root->priority < node->priority) {
        NodePair splitted = split(root, node->key);
        node->left = splitted.first;
        node->right = splitted.second;
        return node;
    }
    else if (node->key < root->key)
        root->setLeft(insert(root->left, node));
    else
        root->setRight(insert(root->right, node));
    return node;
}

//max(a) < min(b) 일 경우 합침.
Node* merge(Node* a, Node* b) {
    if (a == NULL)return b;
    if (b == NULL)return a;

    if (a->priority < b->priority) {
        b->setLeft(merge(a, b->left));
        return b;
    }
    a->setRight(merge(b, a->right));
    return a;
}
Node* kth(Node* root, int k) {
    int leftSize = 0;
    if (root->left != NULL)leftSize = root->left->size;
    if(k<=leftSize) return kth(root->left, k);
    if (k == leftSize + 1)return root;
    return kth(root->right, k - leftSize - 1);
}

int countLessThan(Node* root, KeyType key) {
    if (root == NULL)return 0;
    if (root->key >= key) {
        return countLessThan(root->left, key);
    }
    int ls = (root->left ? root->left->size : 0);
    return ls + 1 + countLessThan(root->right, key);
}

• 종만북에 그대로 있는 코드들을 합쳐놓은 코드이다.

• 정리를 위해 여러 코드를 통합해놓았다.

• Tree와 heap을 합친 트립이라는 자료구조를 구현해놓은 것이다.