이 글에서는 트립(Treap) 자료구조를 C++로 구현하는 방법을 다룹니다. 트립은 기본적으로 무작위화된 이진 탐색 트리(Randomized Binary Search Tree)로, 이진 탐색 트리의 성질과 최대 힙(Max Heap)의 우선순위 성질을 동시에 만족하는 구조입니다. 여기서는 삽입(insert), 삭제(delete), 탐색(search) 세 가지 핵심 연산을 살펴보겠습니다.
주요 함수 개요
rotLeft() — 좌회전 함수 | 트리를 먼저 회전한 뒤 새 루트를 설정합니다. |
rotRight() — 우회전 함수 | 트리를 먼저 회전한 뒤 새 루트를 설정합니다. |
알고리즘 설명
1. 삽입 연산 — insertNod()
주어진 키와 우선순위를 가진 노드를 재귀적으로 트립에 삽입합니다.
루트가 nullptr이면
해당 데이터를 루트로 하여 반환한다.
주어진 데이터가 루트 노드보다 작으면
왼쪽 서브트리에 데이터를 삽입한다.
힙 속성이 깨졌다면 우회전(rotRight)을 수행한다.
그렇지 않으면
오른쪽 서브트리에 데이터를 삽입한다.
힙 속성이 깨졌다면 좌회전(rotLeft)을 수행한다.2. 탐색 연산 — searchNod()
트립에서 특정 키를 재귀적으로 검색합니다.
키가 존재하지 않으면 false를 반환한다.
키가 존재하면 true를 반환한다.
키가 루트보다 작으면 왼쪽 서브트리에서 탐색한다.
그렇지 않으면
오른쪽 서브트리에서 탐색한다.3. 삭제 연산 — deleteNod()
트립에서 특정 키를 재귀적으로 삭제합니다.
키가 존재하지 않으면 종료한다.
키가 루트보다 작으면 왼쪽 서브트리로 이동한다.
그렇지 않으면
오른쪽 서브트리로 이동한다.
키를 찾은 경우:
삭제할 노드가 리프 노드인 경우
메모리를 해제하고 루트를 null로 갱신한다.
루트를 삭제한다.
삭제할 노드에 자식이 둘 있는 경우
왼쪽 자식의 우선순위가 오른쪽 자식보다 낮으면
루트에 rotLeft()를 호출한다.
왼쪽 자식을 재귀적으로 삭제한다.
그렇지 않으면
루트에 rotRight()를 호출한다.
오른쪽 자식을 재귀적으로 삭제한다.
삭제할 노드에 자식이 하나만 있는 경우
자식 노드를 찾는다.
메모리를 해제한다.
결과를 출력한다.
종료C++ 전체 예제 코드
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
struct TreapNod { //노드 선언
int data;
int priority;
TreapNod* l, *r;
TreapNod(int d) { //생성자
this->data = d;
this->priority = rand() % 100;
this->l= this->r = nullptr;
}
};
void rotLeft(TreapNod* &root) { //좌회전
TreapNod* R = root->r;
TreapNod* X = root->r->l;
R->l = root;
root->r= X;
root = R;
}
void rotRight(TreapNod* &root) { //우회전
TreapNod* L = root->l;
TreapNod* Y = root->l->r;
L->r = root;
root->l= Y;
root = L;
}
void insertNod(TreapNod* &root, int d) { //삽입
if (root == nullptr) {
root = new TreapNod(d);
return;
}
if (d < root->data) {
insertNod(root->l, d);
if (root->l != nullptr && root->l->priority > root->priority)
rotRight(root);
} else {
insertNod(root->r, d);
if (root->r!= nullptr && root->r->priority > root->priority)
rotLeft(root);
}
}
bool searchNod(TreapNod* root, int key) {
if (root == nullptr)
return false;
if (root->data == key)
return true;
if (key < root->data)
return searchNod(root->l, key);
return searchNod(root->r, key);
}
void deleteNod(TreapNod* &root, int key) {
//삭제할 노드가 리프 노드인 경우
if (root == nullptr)
return;
if (key < root->data)
deleteNod(root->l, key);
else if (key > root->data)
deleteNod(root->r, key);
//삭제할 노드에 자식이 둘 있는 경우
else {
if (root->l ==nullptr && root->r == nullptr) {
delete root;
root = nullptr;
}
else if (root->l && root->r) {
if (root->l->priority < root->r->priority) {
rotLeft(root);
deleteNod(root->l, key);
} else {
rotRight(root);
deleteNod(root->r, key);
}
}
//삭제할 노드에 자식이 하나만 있는 경우
else {
TreapNod* child = (root->l)? root->l: root->r;
TreapNod* curr = root;
root = child;
delete curr;
}
}
}
void displayTreap(TreapNod *root, int space = 0, int height =10) { //트립 출력
if (root == nullptr)
return;
space += height;
displayTreap(root->l, space);
cout << endl;
for (int i = height; i < space; i++)
cout << ' ';
cout << root->data << "(" << root->priority << ")\n";
cout << endl;
displayTreap(root->r, space);
}
int main() {
int nums[] = {1,7,6,4,3,2,8,9,10 };
int a = sizeof(nums)/sizeof(int);
TreapNod* root = nullptr;
srand(time(nullptr));
for (int n: nums)
insertNod(root, n);
cout << "Constructed Treap:\n\n";
displayTreap(root);
cout << "\nDeleting node 8:\n\n";
deleteNod(root, 8);
displayTreap(root);
cout << "\nDeleting node 3:\n\n";
deleteNod(root, 3);
displayTreap(root);
return 0;
}실행 결과
우선순위는 rand() % 100으로 무작위 생성되므로 실행할 때마다 트리의 모양은 달라질 수 있습니다. 아래는 한 번의 실행 결과 예시입니다.
Constructed Treap: 1(12) 2(27) 3(97) 4(46) 6(75) 7(88) 8(20) 9(41) 10(25) Deleting node 8: 1(12) 2(27) 3(97) 4(46) 6(75) 7(88) 9(41) 10(25) Deleting node 3: 1(12) 2(27) 4(46) 6(75) 7(88) 9(41) 10(25)
마무리
트립은 각 노드에 무작위 우선순위를 부여해 힙 속성을 유지함으로써, 평균적으로 O(log N)의 시간 복잡도로 삽입·삭제·탐색을 보장하는 강력한 자료구조입니다. 회전 연산만 정확히 이해하면 구현 자체는 이진 탐색 트리와 크게 다르지 않으므로, 위 코드를 직접 실행해 보며 동작 원리를 익혀보시기 바랍니다.