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;
}