알고리즘 대회나 시스템 설계에서 정렬된 데이터를 다루다 보면, 삽입·삭제·검색이 모두 빠른 균형 이진 탐색 트리가 필요해진다. 레드-블랙 트리나 AVL 트리가 대표적이지만 회전 규칙과 색상 관리가 복잡해 직접 구현하기는 부담스럽다. 트립(Treap)은 이 문제를 전혀 다른 방식으로 푼다. 이름 그대로 트리(tree)와 힙(heap)을 합친 자료구조로, 1989년 라이문트 자이델(Raimund Siedel)과 세실리아 아라곤(Cecilia Aragon)이 제안했다. cp-algorithms의 해설을 바탕으로 트립의 작동 원리와 실무에서의 쓸모, 그리고 한계를 정리해 본다.
무작위 우선순위가 균형을 만든다
트립은 각 노드에 두 개의 값, 키 $X$와 우선순위 $Y$를 함께 저장한다. 트리는 $X$에 대해서는 이진 탐색 트리 성질을, $Y$에 대해서는 이진 힙 성질을 동시에 만족한다. 즉 어떤 노드의 왼쪽 서브트리는 모두 작은 키를, 오른쪽은 큰 키를 가지면서, 자식들의 우선순위는 부모보다 작거나 같다. 핵심은 우선순위를 난수로 부여한다는 점이다. 우선순위가 없다면 같은 키 집합이 수많은 형태의 트리로 만들어질 수 있고, 운이 나쁘면 연결 리스트처럼 한쪽으로 늘어져 모든 연산이 $O(N)$으로 느려진다. 반면 우선순위가 서로 다르면 트리 모양이 유일하게 결정되고, 그 값을 무작위로 고르면 평균적으로 치우치지 않은 트리가 만들어져 주요 연산이 $O(\log N)$에 수행된다. 트립이 '무작위 이진 탐색 트리'라고도 불리는 이유다.
모든 연산은 Split과 Merge로 환원된다
트립 구현의 우아함은 거의 모든 기능을 두 개의 보조 연산으로 처리한다는 데 있다. Split($T$, $X$)는 트리를 키 $X$를 기준으로, $X$ 이하를 담은 왼쪽 트리와 $X$ 초과를 담은 오른쪽 트리로 쪼갠다. Merge($T_1$, $T_2$)는 왼쪽 트리의 모든 키가 오른쪽보다 작다는 전제 아래 두 트리를 합치되, 우선순위가 더 높은 쪽을 루트로 삼아 재귀적으로 병합함으로써 힙 성질을 깨지 않는다. 두 연산 모두 $O(\log N)$이다. 삽입은 트리를 $X$로 쪼갠 뒤 새 노드를 사이에 두고 두 번 병합하면 되고, 삭제는 지울 노드의 두 자식을 병합해 그 자리에 넣으면 된다. 복잡한 회전 규칙 대신 '쪼개고 합친다'는 단순한 사고만으로 자료구조 전체를 다룰 수 있다.
이 재귀 구조는 처음 보면 혼란스럽다. 특히 C++ 구현에서 Split은 포인터와 포인터에 대한 참조를 함께 쓰기 때문에 더욱 그렇다. 원문이 권하는 이해법은 귀납적 접근이다. 재귀 호출을 머릿속에서 끝없이 펼치려 하지 말고, 빈 트리에서 동작이 맞다고 가정한 뒤 노드 한 개, 두 개짜리 트리로 차근차근 범위를 넓혀가며 '작은 트리에서 맞으니 큰 트리에서도 맞다'는 식으로 확인하는 것이다. 이 사고법은 트립뿐 아니라 재귀적 트리 연산 전반을 읽을 때 유용하다.
순위 질의와 더 빠른 생성
각 노드에 서브트리의 노드 개수를 저장하는 cnt 필드를 추가하면 트립의 활용 범위가 넓어진다. 이 값으로 K번째로 큰 원소를 찾거나 정렬된 목록에서 특정 원소의 순위를 구하는 연산을 모두 $O(\log N)$에 처리할 수 있다. 트리가 바뀔 때마다 cnt를 갱신해야 하므로, 자식의 값이 이미 갱신되었다고 가정하고 현재 노드를 갱신하는 함수를 삽입·삭제·Split·Merge 끝에 호출하는 방식으로 일관성을 유지한다. 또한 키가 이미 정렬되어 있다면 하나씩 삽입하는 $O(N \log N)$ 대신, 균형 잡힌 트리를 선형 시간에 세우고 무작위 우선순위만 $O(N)$에 힙 정렬하는 방식으로 더 빠르게 만들 수 있다. 다만 이 방법은 완벽한 균형을 주는 대신 처음 부여한 우선순위를 보존하지 못한다는 제약이 있다.
우선순위가 무작위가 아니라 문제에서 주어진 값일 때는 이야기가 달라진다. 주어진 $(x_i, y_i)$ 쌍으로 카르테시안 트리를 세우는 문제에서는 노드를 하나씩 삽입하면 최악의 경우 제곱 시간이 될 수 있다. 이때는 각 원소에 대해 좌우에서 자신보다 우선순위가 작은 가장 가까운 원소를 찾고 그중 우선순위가 큰 쪽을 부모로 삼으면 되는데, 최소 스택을 변형하면 선형 시간에 전체 트리를 구성할 수 있다.
암시적 트립: 배열을 트리로 다루기
트립의 가장 강력한 변형은 암시적 트립(implicit treap)이다. 키를 배열에서의 0 기반 인덱스로 삼되, 그 인덱스를 노드에 직접 저장하지 않는 것이 핵심이다. 만약 인덱스를 명시적으로 저장하면 중간에 원소 하나를 삽입할 때마다 $O(N)$개 노드의 키를 바꿔야 하기 때문이다. 대신 각 노드의 암시적 키는 왼쪽 서브트리의 크기와 조상들로부터 누적된 값으로 트리를 내려가며 계산한다. 이렇게 하면 임의 위치 삽입·삭제, 구간 뒤집기 같은 배열 연산을 모두 온라인으로 $O(\log N)$에 수행하는, 사실상 '빠른 배열'을 얻게 된다. 구간 반전 같은 연산까지 지원하는 이 구조는 일반 배열로는 불가능한 효율을 낸다.
정리하면 트립은 구현 난도와 성능의 균형이 뛰어난 선택지다. Split과 Merge라는 두 개념만 이해하면 정렬 집합, 순위 질의, 구간 조작까지 폭넓게 커버할 수 있다. 다만 성능 보장이 난수에 기대고 있어 엄밀한 최악 시간 보장이 필요한 환경에서는 결정론적 균형 트리가 더 적합할 수 있고, 주어진 우선순위를 다루거나 순위 질의가 필요한 경우에는 앞서 설명한 별도 기법을 함께 써야 한다는 점을 염두에 둘 필요가 있다.