알고리즘 면접에서는 안 나오지만, 현실에서 쓰이는 독특한 트리 자료구조 이야기

트리, 이진 탐색 트리 말고 뭐가 있을까요?

개발자라면 누구나 트리(Tree) 자료구조를 배워요. 이진 탐색 트리(BST), 힙(Heap), AVL 트리 정도는 알고리즘 공부하면서 한 번쯤 만나보셨을 거예요. 그런데 컴퓨터 과학의 세계에는 이런 교과서적인 트리 말고도, 특수한 문제를 기가 막히게 풀어내는 독특한 트리 자료구조들이 꽤 많아요. 이런 트리들은 코딩 테스트에서는 잘 안 나오지만, 데이터베이스 엔진이나 네트워크 라우터, 텍스트 에디터 같은 실제 시스템의 내부에서 묵묵히 일하고 있거든요.

오늘은 그중에서도 특히 흥미로운 트리 자료구조 몇 가지를 소개해볼게요. 각 트리가 어떤 문제를 풀기 위해 만들어졌고, 어디에서 실제로 쓰이는지를 중심으로 이야기해 볼게요.

Splay Tree: "최근에 쓴 걸 또 쓸 거야"

스플레이 트리(Splay Tree)는 이진 탐색 트리의 변형인데요, 핵심 아이디어가 아주 직관적이에요. 가장 최근에 접근한 노드를 트리의 루트로 올려버리는 거예요. 이게 뭐냐면, 우리가 데이터를 사용하는 패턴을 떠올려 보면, 방금 찾아본 데이터를 곧 다시 찾아볼 확률이 높잖아요? 이걸 '시간적 지역성(Temporal Locality)'이라고 하는데, 스플레이 트리는 이 성질을 구조 자체에 녹여낸 거예요.

노드에 접근할 때마다 회전(rotation) 연산을 통해 해당 노드를 루트까지 끌어올리는데, 신기한 건 이렇게 하면 자주 접근하는 노드들은 항상 트리 상단에 위치하게 돼서, 평균적으로 아주 빠른 접근이 가능해져요. 최악의 경우 한 번의 연산은 O(n)이 될 수 있지만, 연속된 m번의 연산을 보면 전체가 O(m log n)으로 수렴하는 '상각 분석(Amortized Analysis)' 관점에서 효율적이에요. 캐시 시스템이나 가비지 컬렉터 내부에서 활용되는 경우가 있어요.

Treap: 트리 + 힙의 합체

트립(Treap)은 이름부터 재미있는데, Tree + Heap을 합친 거예요. 각 노드가 키(key)와 우선순위(priority) 두 가지 값을 갖고 있어요. 키 기준으로는 이진 탐색 트리 성질을 유지하고, 우선순위 기준으로는 힙 성질을 유지해요. 우선순위는 보통 랜덤하게 부여하는데, 이렇게 하면 트리가 자연스럽게 균형을 이루게 돼요.

이게 왜 똑똑한 설계냐면, AVL 트리나 레드-블랙 트리처럼 복잡한 균형 유지 로직을 짤 필요 없이, 랜덤 우선순위 하나만으로 확률적으로 균형 잡힌 트리를 만들 수 있기 때문이에요. 구현도 상대적으로 간단해서 프로그래밍 대회(CP)에서 인기가 많고, 실무에서도 인메모리 정렬 컨테이너로 쓰이는 경우가 있어요.

Finger Tree: 양쪽 끝 접근이 빠른 만능 시퀀스

핑거 트리(Finger Tree)는 함수형 프로그래밍 세계에서 태어난 자료구조예요. 이게 뭐냐면, 시퀀스(리스트)의 양쪽 끝에서의 삽입과 삭제가 O(1) 상각 시간에 가능한 트리인데요, 동시에 중간 지점에서의 분할(split)과 병합(merge)도 효율적으로 지원해요.

일반적인 배열은 앞쪽 삽입이 느리고, 연결 리스트는 인덱스 접근이 느린데, 핑거 트리는 이 두 가지를 모두 잘 처리해요. Haskell의 Data.Sequence 같은 표준 라이브러리가 내부적으로 핑거 트리를 사용하고 있어요. 텍스트 에디터에서 커서 양쪽의 텍스트를 효율적으로 관리하는 데 쓰이기도 하고, 우선순위 큐나 정렬된 시퀀스를 핑거 트리 위에 구현할 수도 있어서 정말 다재다능한 구조예요.

Van Emde Boas Tree: 정수 집합 연산의 끝판왕

반 엠데 보아스 트리(Van Emde Boas Tree, 줄여서 vEB 트리)는 이름부터 어려워 보이는데, 하는 일은 명확해요. 정수 집합에 대한 삽입, 삭제, 검색, 전임자/후임자 찾기를 O(log log n) 시간에 처리해요. 보통 O(log n)도 빠르다고 하는데, O(log log n)은 차원이 다른 빠르기예요. 예를 들어 원소가 100만 개면 log n은 약 20인데, log log n은 약 4밖에 안 돼요.

비결은 키의 범위(universe)를 재귀적으로 √ 크기씩 쪼개는 거예요. 0부터 15까지의 정수를 다룬다면, 이걸 4개씩 4그룹으로 나누고, 각 그룹을 다시 같은 방식으로 나누는 식이에요. 대신 메모리를 많이 쓰는 게 단점이라, 키의 범위가 미리 정해져 있고 빠른 전임자/후임자 쿼리가 중요한 네트워크 라우팅 테이블 같은 곳에서 활용돼요.

Link-Cut Tree: 동적으로 변하는 숲을 다루는 마법

링크-컷 트리(Link-Cut Tree)는 Sleator와 Tarjan이 만든 자료구조인데요, 트리들의 집합(포레스트)에서 간선을 동적으로 추가하거나 제거하면서도 두 노드 사이의 경로 질의를 효율적으로 처리할 수 있어요. 이게 언제 필요하냐면, 네트워크 토폴로지가 실시간으로 바뀌는 상황을 생각해 보세요. 노드가 연결되었다가 끊어졌다가 하는 동적 그래프에서 "이 두 노드가 같은 트리에 속해 있나?", "이 경로의 가중치 합은 얼마인가?" 같은 질문에 빠르게 답할 수 있어요.

내부적으로 앞서 말한 스플레이 트리를 보조 자료구조로 사용하는데, 모든 연산이 O(log n) 상각 시간에 동작해요. 알고리즘 대회의 고난이도 문제나 네트워크 최적화 분야에서 가끔 등장해요.

업계 맥락: 왜 이런 자료구조를 알아야 할까요?

솔직히 이런 트리들을 일상적인 웹 개발에서 직접 구현할 일은 거의 없어요. 하지만 이런 자료구조들이 중요한 이유는, 우리가 매일 쓰는 시스템의 내부에서 이미 동작하고 있기 때문이에요. 데이터베이스의 B+ 트리, Git의 Merkle 트리, 리눅스 커널 스케줄러의 레드-블랙 트리처럼요. 내부 구조를 이해하면 시스템의 성능 특성을 직관적으로 파악할 수 있고, 병목이 어디서 생기는지 추론하는 데도 큰 도움이 돼요.

또한 이런 자료구조들은 각각 특정 접근 패턴이나 연산 패턴에 최적화되어 있다는 공통점이 있어요. 스플레이 트리는 시간적 지역성, vEB 트리는 정수 키의 범위 제한, 핑거 트리는 양 끝 접근 패턴에 맞춰져 있죠. "어떤 자료구조를 쓸까"를 고민할 때 데이터의 접근 패턴을 먼저 분석한다는 사고방식 자체가 실력 있는 개발자의 핵심 역량이에요.

한국 개발자에게 주는 시사점

코딩 테스트 준비할 때 기본 자료구조만 반복하다 보면 시야가 좁아지기 쉬운데요, 이런 독특한 트리들을 공부해 보면 자료구조 설계의 원리 자체를 더 깊이 이해할 수 있어요. 특히 트립은 구현이 비교적 쉬워서 백준이나 코드포스 같은 대회 문제에서 직접 써볼 수 있고, 스플레이 트리는 캐시 최적화의 원리를 이해하는 데 좋은 출발점이에요.

시스템 프로그래밍이나 데이터베이스 엔진 개발에 관심 있는 분이라면, 이런 자료구조들의 동작 원리를 한 번쯤 깊이 파보는 걸 추천해요. 면접에서 "Redis의 Sorted Set은 내부적으로 어떤 자료구조를 쓰나요?" 같은 질문이 나왔을 때, 스킵 리스트와 트립의 차이까지 설명할 수 있다면 확실히 차별화될 거예요.