트리 리밸런싱 알고리즘 완벽 정리: DSW부터 동시성 스킵 리스트까지

트리 구조가 편향되면 탐색 성능이 급격히 저하됩니다. 이를 방지하기 위한 리밸런싱(Rebalancing) 알고리즘은 대표적으로 세 가지 방식으로 구현할 수 있습니다.

1. Day-Stout-Warren(DSW) 알고리즘

DSW 알고리즘은 실제 리밸런스 메서드를 구현하는 가장 고전적인 방법 중 하나입니다. 노드 수에 대해 선형 시간(O(n))으로 동작하며, 추가 메모리 없이 기존 트리를 완전히 균형 잡힌 형태로 재구성할 수 있다는 장점이 있습니다.

다음은 기본적인 DSW 알고리즘의 절차를 의사 코드 형태로 정리한 것입니다.

• 새로운 노드를 하나 할당하여 가상 루트(pseudo-root)로 만들고, 기존 트리의 실제 루트를 이 가상 루트의 오른쪽 자식으로 연결합니다.
• tree-to-vine 함수를 호출하여 가상 루트를 인자로 넘김으로써, 트리를 정렬된 연결 리스트(vine) 형태로 변환합니다.
• vine-to-tree 함수를 호출하여 가상 루트와 트리의 크기(노드 개수)를 인자로 넘김으로써, 정렬된 연결 리스트를 다시 완전히 균형 잡힌 트리로 변환합니다.
• 변환이 끝나면 가상 루트의 오른쪽 자식을 새로운 실제 루트로 지정합니다.
• 마지막으로 더 이상 필요하지 않은 가상 루트 노드를 해제(dispose)합니다.

2. "Copy On Write" 트리

선형화 가능성(linearizability)의 일부 희생을 감수할 수 있다면, 즉 값을 쓴 직후 검색했을 때 일시적으로 찾지 못하더라도 100ms~10초 내에는 반드시 반영되는 최종 일관성(eventual consistency)으로 충분하다면, 카피온라이트(Copy-On-Write) 트리 방식을 적용할 수 있습니다.

이 방식의 동작 원리는 다음과 같습니다.

• 모든 쓰기 작업(리밸런싱 포함)은 단일 쓰기 스레드에서만 수행됩니다.
• 주기적으로 트리 전체를 읽기 전용(read-only) 복사본으로 복제합니다.
• 읽기 전용 복사본은 어떠한 동시성 제어(lock) 없이도 여러 읽기 스레드가 안전하게 사용할 수 있습니다.
• 단, 새 복사본을 교체할 때는 원자적(atomic)으로 게시(publish)해야 데이터 일관성이 유지됩니다.

3. 동시성 스킵 리스트(Concurrent Skip List)

세 번째 선택지는 동시성 스킵 리스트를 구현하는 것입니다. 스킵 리스트는 평균적으로 로그 시간(logarithmic time)의 검색·삭제·삽입 성능을 제공하며, 균형 트리보다 병렬화가 훨씬 용이하다는 강력한 장점이 있습니다.

특히 Java 환경이라면 표준 라이브러리에서 락 프리(lock-free) 구현체(ConcurrentSkipListMap, ConcurrentSkipListSet)을 이미 제공하므로, 직접 구현하지 않고도 활용할 수 있습니다.

동시성 환경에 최적화된 균형 탐색 트리에 관심이 있다면 크로마틱 트리(chromatic tree)도 살펴볼 만합니다. 크로마틱 트리는 동시 리밸런싱(concurrent rebalancing)에 최적화된 이진 탐색 트리로, 여러 스레드가 동시에 삽입·삭제·재조정 작업을 수행할 수 있도록 설계되었습니다.

정리