FHQ 트리 구현 및 활용

FHQ 트리는 split과 merge 연산을 통해 균형을 유지하는 자료구조입니다. 이 트리는 주로 시퀀스 관리 문제에서 사용됩니다.

구조체 정의

각 노드는 왼쪽 및 오른쪽 자식 노드를 가진 이진 트리입니다. 또한 BST 특성을 유지하기 위한 값(v)과 랜덤 우선순위(k)를 저장합니다. 각 노드의 하위 트리 크기를 유지하기 위해 크기 정보(s)도 포함됩니다.

struct Node {
    Node *left, *right;
    int value, priority, size;

    Node(int val) : left(nullptr), right(nullptr), value(val), priority(rand()), size(1) {}

    void updateSize() {
        size = 1;
        if (left) size += left->size;
        if (right) size += right->size;
    }
};

Node* root = nullptr;

Split 함수

Split 함수는 특정 기준에 따라 트리를 두 개로 나눕니다. 여기서는 값 기준으로 분할하는 경우만 다룹니다.

void split(Node* current, int key, Node*& leftTree, Node*& rightTree) {
    if (!current) {
        leftTree = rightTree = nullptr;
        return;
    }

    if (current->value <= key) {
        leftTree = current;
        split(current->right, key, leftTree->right, rightTree);
    } else {
        rightTree = current;
        split(current->left, key, leftTree, rightTree->left);
    }
    current->updateSize();
}

Merge 함수

두 개의 서브트리를 하나로 합칩니다. 이때 우선순위 값을 기반으로 병합됩니다.

Node* merge(Node* leftTree, Node* rightTree) {
    if (!leftTree || !rightTree) return leftTree ? leftTree : rightTree;

    if (leftTree->priority < rightTree->priority) {
        leftTree->right = merge(leftTree->right, rightTree);
        leftTree->updateSize();
        return leftTree;
    } else {
        rightTree->left = merge(leftTree, rightTree->left);
        rightTree->updateSize();
        return rightTree;
    }
}

삽입 연산

새로운 값을 삽입하려면 먼저 해당 값을 기준으로 트리를 나누고, 새로운 노드를 생성한 후 다시 병합합니다.

void insert(int value) {
    Node* leftSubtree, *rightSubtree;
    split(root, value, leftSubtree, rightSubtree);
    root = merge(merge(leftSubtree, new Node(value)), rightSubtree);
}

삭제 연산

삭제는 삽입과 유사하지만, 삭제 대상 노드를 찾아 그 노드를 제거하고 다시 병합합니다.

void remove(int value) {
    Node* leftSubtree, *middleSubtree, *rightSubtree;
    split(root, value - 1, leftSubtree, middleSubtree);
    split(middleSubtree, value, middleSubtree, rightSubtree);

    if (middleSubtree) {
        Node* temp = merge(middleSubtree->left, middleSubtree->right);
        delete middleSubtree;
        middleSubtree = temp;
    }

    root = merge(leftSubtree, rightSubtree);
}

순위 조회

특정 값의 순위를 찾으려면 그 값보다 작은 모든 노드들의 수를 계산합니다.

int getRankOfValue(int value) {
    Node* leftSubtree, *rightSubtree;
    split(root, value - 1, leftSubtree, rightSubtree);
    int rank = (leftSubtree ? leftSubtree->size : 0) + 1;
    root = merge(leftSubtree, rightSubtree);
    return rank;
}

전체 코드

아래는 위에서 설명한 모든 연산들을 포함한 완성된 코드입니다.

#include <cstdio>
#include <cstdlib>

struct Node {
    Node *left, *right;
    int value, priority, size;

    Node(int val) : left(nullptr), right(nullptr), value(val), priority(rand()), size(1) {}

    void updateSize() {
        size = 1;
        if (left) size += left->size;
        if (right) size += right->size;
    }
};

Node* root = nullptr;

void split(Node* current, int key, Node*& leftTree, Node*& rightTree) {
    if (!current) {
        leftTree = rightTree = nullptr;
        return;
    }

    if (current->value <= key) {
        leftTree = current;
        split(current->right, key, leftTree->right, rightTree);
    } else {
        rightTree = current;
        split(current->left, key, leftTree, rightTree->left);
    }
    current->updateSize();
}

Node* merge(Node* leftTree, Node* rightTree) {
    if (!leftTree || !rightTree) return leftTree ? leftTree : rightTree;

    if (leftTree->priority < rightTree->priority) {
        leftTree->right = merge(leftTree->right, rightTree);
        leftTree->updateSize();
        return leftTree;
    } else {
        rightTree->left = merge(leftTree, rightTree->left);
        rightTree->updateSize();
        return rightTree;
    }
}

void insert(int value) {
    Node* leftSubtree, *rightSubtree;
    split(root, value, leftSubtree, rightSubtree);
    root = merge(merge(leftSubtree, new Node(value)), rightSubtree);
}

void remove(int value) {
    Node* leftSubtree, *middleSubtree, *rightSubtree;
    split(root, value - 1, leftSubtree, middleSubtree);
    split(middleSubtree, value, middleSubtree, rightSubtree);

    if (middleSubtree) {
        Node* temp = merge(middleSubtree->left, middleSubtree->right);
        delete middleSubtree;
        middleSubtree = temp;
    }

    root = merge(leftSubtree, rightSubtree);
}

int getRankOfValue(int value) {
    Node* leftSubtree, *rightSubtree;
    split(root, value - 1, leftSubtree, rightSubtree);
    int rank = (leftSubtree ? leftSubtree->size : 0) + 1;
    root = merge(leftSubtree, rightSubtree);
    return rank;
}

int main() {
    srand(388651);
    int n, operation, value;
    scanf("%d", &n);

    while (n--) {
        scanf("%d%d", &operation, &value);
        switch (operation) {
            case 1: insert(value); break;
            case 2: remove(value); break;
            case 3: printf("%d\n", getRankOfValue(value)); break;
        }
    }

    return 0;
}

태그: C++ data structures FHQ Treap

10월 16일 09:13에 게시됨