# Splay Tree 스터디 노트 = 2025 11 29 = 오늘 배운 것: - Splay Tree의 기본 개념과 자가 조정(self-adjusting) 메커니즘 - Splay 연산의 세 가지 케이스: Zig, Zig-Zig, Zig-Zag - 접근한 노드를 루트로 올리는 독특한 전략 - AVL, Red-Black Tree와의 차이점 ## 0. 들어가며: Splay Tree를 접한 소감 B-Tree를 공부한 직후 Splay Tree를 보니, 그 대조적인 설계 철학이 무척 흥미로웠다. B-Tree가 디스크 I/O 효율을 위해 `넓고 낮게` 설계되었다면, Splay Tree는 자주 사용하는 데이터를 메모리상에서 더 빠르게 찾기 위해 `자주 쓰는 걸 위로 올리는 전략`을 사용한다. AVL이나 Red-Black Tree처럼 노드에 균형 정보(높이, 색상)를 따로 저장하지 않는다는 점이 가장 큰 특징이었다. 그저 특정 노드에 접근할 때마다 그 노드를 루트로 '끌어올리는' 단순한 연산 하나로 스스로 균형을 맞춰나간다. 처음엔 "이게 정말 효율적일까?" 의구심이 들었지만, Amortized Analysis를 통해 평균적으로 O(log n) 성능이 보장된다는 것을 알고 나니 더욱 흥미롭게 다가왔다. 특히 데이터 접근에 지역성(Locality)이 존재할 때, 예를 들어 동일한 데이터를 반복적으로 찾을 때, 마치 캐시처럼 동작하여 엄청난 효율을 보인다는 점이 인상 깊었다. 단순함 속에 숨겨진 우아함과 실용성을 동시에 느낄 수 있는 자료구조였다. --- ## 1. Splay Tree의 탄생 배경 Splay Tree는 1985년 Daniel Sleator와 Robert Tarjan이 개발한 **자가 조정(Self-adjusting) 이진 탐색 트리**다. 기존의 균형 트리(AVL, Red-Black)들이 노드에 별도의 **균형 정보**를 저장하고, 이를 유지하기 위해 복잡한 규칙을 따랐던 것과 달리, Splay Tree는 발상의 전환을 보여주었다. - AVL Tree: 각 노드에 높이(또는 균형 인수) 저장 - Red-Black Tree: 각 노드에 색깔(Red/Black) 저장 Splay Tree는 이러한 추가 정보를 **전혀 저장하지 않는다**. 대신, 아래의 단순한 규칙 하나를 따른다. > **"어떤 노드에 접근했다면, 그 노드를 트리의 루트(Root)로 만든다."** 이 아이디어의 기저에는 **참조 지역성(Locality of Reference)** 원리가 있다. > **"방금 접근했던 데이터는 가까운 미래에 다시 접근될 확률이 높다."** 이 간단한 원칙 하나로 복잡한 균형 로직 없이도 평균적으로 뛰어난 성능을 내는 효율적인 자료구조를 만들어낸 것이다. --- ## 2. Splay 연산: 핵심 메커니즘 Splay Tree의 모든 연산(탐색, 삽입, 삭제)은 **Splay**라는 핵심 연산을 통해 이루어진다. **Splay란?** 특정 노드 `X`를 루트로 만드는 일련의 회전(Rotation) 과정이다. 중요한 점은, 단순히 `X`를 루트까지 반복해서 회전시키는 것이 아니라, `X`와 부모(`P`), 조부모(`G`)의 관계에 따라 세 가지 다른 회전 방식을 사용한다는 것이다. ### Case 1: Zig `X`의 부모 `P`가 루트일 때. **단 한 번의 회전**으로 `X`가 새로운 루트가 된다. ``` P (root) X (root) / \ X --> P (X가 P의 왼쪽 자식일 경우) ``` ### Case 2: Zig-Zig `X`, `P`, `G`가 **일직선** 관계일 때 (Left-Left 또는 Right-Right). ``` G X / \ P --> P / \ X G (Left-Left Case 기준) 1. 조부모 `G`를 회전시킨다. (P가 G의 자리를 차지) 2. 부모 `P`를 회전시킨다. (X가 P의 자리를 차지) ``` **중요**: 이 순서는 단순히 `X`를 위로 두 번 올리는 것과 다르다. `G`를 먼저 회전시킴으로써 트리의 깊이를 효과적으로 줄여준다. ### Case 3: Zig-Zag `X`, `P`, `G`가 **꺾인 선** 관계일 때 (Left-Right 또는 Right-Left). ``` G X / / \ P --> P G \ X (Left-Right Case 기준) 1. 부모 `P`를 회전시킨다. (X가 P의 자리를 차지) 2. 조부모 `G`를 회전시킨다. (X가 G의 자리를 차지) ``` 이 경우는 AVL 트리의 이중 회전(Double Rotation)과 동일하다. ### 왜 이렇게 복잡한 회전을 할까? 만약 단순 회전만 반복해서 `X`를 루트로 올린다면, 특정 상황에서 트리가 여전히 길쭉한 형태로 남게 된다. (링크드리스트와 다를 바 없음) 하지만 Zig-Zig, Zig-Zag 방식을 사용하면 트리가 훨씬 균형 잡힌 형태로 재구성된다. **예시**: `1-2-3-4-5` 순서로 데이터가 삽입되어 한쪽으로 치우친 트리에서 `1`을 탐색한다고 가정해보자. - **단순 회전만 사용하면:** `1`이 루트가 되긴 하지만, 트리는 여전히 깊고 비효율적인 구조를 가질 확률이 높다. - **Splay 연산을 사용하면:** Zig-Zig 회전이 반복 적용되면서 트리가 훨씬 넓고 얕은 구조로 재편성된다. 마치 트리를 한번 흔들어서(Splay) 재배치하는 느낌이다. (한국말로 하면 와리가리 트리로 번역해도 되지 않을까) --- ## 3. 주요 연산의 구현 ### Search (탐색) 1. 일반적인 이진 탐색 트리(BST)처럼 대상 노드를 탐색한다. 2. 노드를 **찾았다면**, 해당 노드를 Splay한다. 3. 노드를 **못 찾았다면**, 탐색이 끝난 지점의 마지막 노드를 Splay한다. **핵심**: 탐색의 성공 여부와 관계없이 **반드시 Splay 연산이 동반된다**. 이 덕분에 자주 찾는 데이터는 항상 루트 가까이에 위치하게 된다. ### Insert (삽입) 1. BST처럼 삽입할 위치를 탐색한다. 2. 새 노드를 해당 위치에 삽입한다. 3. **새 노드를 Splay한다.** 새로 추가된 데이터가 가장 최근 데이터이므로, 곧바로 루트로 옮겨와 후속 접근에 대비하는 것이다. ### Delete (삭제) 삭제는 조금 더 창의적인 방법이 사용된다. 1. 삭제할 노드 `X`를 Splay하여 루트로 만든다. 2. 루트가 된 `X`를 제거하면, 트리는 왼쪽 서브트리(`L`)와 오른쪽 서브트리(`R`)로 분리된다. 3. 왼쪽 서브트리 `L`에서 가장 큰 원소 `M`을 찾는다. (이 원소는 `L`의 모든 원소보다 크거나 같다) 4. `M`을 `L`의 루트로 Splay한다. 이 때 `M`은 오른쪽 자식이 없다. 5. `M`의 오른쪽 자식으로 오른쪽 서브트리 `R`을 연결한다. 이 방식의 장점은 `L`의 모든 원소는 `R`의 모든 원소보다 작다는 BST의 속성을 활용하여, 추가적인 재구성 없이 두 트리를 효율적으로 합칠 수 있다는 점이다. --- ## 4. 다른 균형 트리와의 비교 | 특징 | Splay Tree | AVL Tree | Red-Black Tree | B-Tree | |---|---|---|---|---| | **균형 정보 저장** | **✗ 없음** | ✓ 높이 | ✓ 색깔 | ✓ 차수 | | **최악 시간 복잡도** | O(n) | O(log n) | O(log n) | O(log n) | | **Amortized 복잡도** | **O(log n)** | O(log n) | O(log n) | O(log n) | | **참조 지역성 활용** | **✓✓✓ (최상)** | ✗ | ✗ | △ | | **구현 복잡도** | 중간 | 높음 | 매우 높음 | 높음 | | **메모리 오버헤드** | **낮음** | 중간 | 중간 | 높음 | ### Splay Tree의 장점 1. **단순한 구조와 구현**: 균형 정보를 저장할 별도 공간이 필요 없고, 회전 규칙도 상대적으로 직관적이다. 2. **참조 지역성에 강함**: 자주 접근하는 데이터에 대한 탐색 속도가 거의 O(1)에 가까워진다. 캐시와 유사한 성능을 보인다. 3. **메모리 효율성**: 노드당 오버헤드가 적어 메모리가 제한적인 환경에서 유리하다. 4. **뛰어난 평균 성능**: Amortized O(log n)이 보장되므로, 대부분의 실용적인 시나리오에서 좋은 성능을 낸다. ### Splay Tree의 단점 1. **최악의 경우 O(n)**: 드물지만, 특정 접근 패턴(예: 정렬된 순서로 순차 접근)에서는 성능이 급격히 저하될 수 있다. 2. **빈번한 구조 변경**: 읽기 연산(탐색)조차 트리 구조를 변경하므로, 이로 인한 오버헤드가 발생할 수 있다. 3. **동시성(Concurrency) 문제**: 읽기 연산 때문에 공유 자원(트리 구조)에 락을 걸어야 하므로 병목 현상이 발생하기 쉽다. --- ## 5. Splay Tree는 언제 사용할까? ### 사용하면 좋은 경우 - **데이터 접근 편향이 심할 때**: 소수의 데이터에 접근이 집중되는 워크로드 (Zipf 분포 등) - **LRU 캐시와 유사한 로직이 필요할 때**: 가장 최근에 사용된 항목을 빠르게 찾아야 할 경우 - **메모리 사용량이 중요할 때**: 임베디드 시스템이나 노드 개수가 매우 많은 경우 - **구현의 단순성이 중요할 때**: 복잡한 균형 트리보다 빠르고 간단하게 구현해야 할 경우 ### 사용을 피해야 할 경우 - **실시간 시스템**: 최악의 경우(O(n))가 치명적인 시스템에서는 부적합하다. (AVL, RB-Tree가 대안) - **데이터 접근이 균등할 때**: 모든 노드에 대한 접근 확률이 비슷하다면 Splay의 이점을 살릴 수 없고 불필요한 회전 비용만 발생한다. - **높은 동시성이 요구되는 멀티스레드 환경**: 읽기 연산 때문에 공유 자원(트리 구조)에 락을 걸어야 하므로 병목 현상이 발생하기 쉽다. --- ## 6. 실제 사용 사례 - **과거 Linux 커널**: 가상 메모리 영역(VMA) 관리에 사용. 프로세스는 특정 메모리 영역을 집중적으로 접근하는 경향이 있어 Splay Tree가 효과적이었다. https://www.osronline.com/article.cfm%5Earticle=516.htm - **GCC 컴파일러**: 심볼 테이블 관리. 컴파일러는 소스코드의 특정 변수나 함수 이름을 반복적으로 참조하므로 지역성이 강하다. - **네트워크 라우터**: 라우팅 테이블 관리. 자주 사용되는 경로가 루트 가까이에 위치하여 패킷 포워딩 속도를 높일 수 있다. --- ## 7. Amortized Analysis에 대한 직관적 이해 "최악의 경우 O(n)인데 어떻게 평균 O(log n)이 보장될까?" 이 부분이 가장 이해하기 어려운 지점이었다. 핵심은 **"비싼 연산은 스스로를 포함한 미래의 연산 비용까지 미리 지불한다"** 는 개념이다. 1. **최악의 상황**: 한쪽으로 길게 늘어선 트리에서 가장 깊은 노드를 탐색하는 데 O(n)의 비용이 들었다고 가정하자. 2. **구조 개선**: 이 비싼 연산의 대가로, Splay는 트리를 훨씬 균형 잡힌 형태로 재구성한다. 3. **미래의 이득**: 이제 트리는 더 이상 최악의 형태가 아니므로, 이후의 연산들은 훨씬 저렴한 비용(예: O(log n))으로 수행될 수 있다. 즉, 한 번의 O(n) 연산이 발생하면, 그 연산이 트리를 '건강하게' 만들어 주기 때문에 **연속적으로 O(n) 연산이 발생하는 것은 불가능하다**. 비싼 연산 한 번이 다음 연산들의 비용을 '할인'해주는 셈이다. 이것이 M개의 연산을 수행했을 때, 총비용이 O(M log N)으로 수렴하는 이유다. --- ## 8. 코드 실행 및 손으로 그려보기 ### 컴파일 및 실행 ```bash cd java-datastructures javac SplayTree/*.java java SplayTree.SplayTreeDemo ``` 실행 결과를 보면, 연산이 수행될 때마다 대상 노드가 루트로 올라오는 것을 명확히 확인할 수 있다. ### 직접 그려보기 **예제: [10, 20, 30] 순서로 삽입** 1. `10` 삽입: `10` (루트) 2. `20` 삽입: `20`을 `10`의 오른쪽에 삽입 후 Splay. (Zig) ``` 20 / 10 ``` 3. `30` 삽입: `30`을 `20`의 오른쪽에 삽입 후 Splay. (Zig-Zig) ``` 30 / 20 / 10 ``` **이제 이 상태에서 `10`을 탐색하면?** - `10`을 Splay (Zig-Zig 적용) ``` 10 \ 20 \ 30 ``` 여전히 일직선이지만, 구조가 반전되었다. **다시 여기서 `20`을 탐색하면?** - `20`을 Splay (Zig-Zag 적용) ``` 20 / \ 10 30 ``` 마침내 균형 잡힌 트리가 만들어졌다. 이처럼 Splay Tree는 연산이 계속됨에 따라 스스로 최적의 구조를 찾아간다. ## 9. Amortized Analysis ### Amortized vs Average: 자주 혼동하는 개념 | | Average Case | Amortized | |---|---|---| | 정의 | 랜덤 입력의 기댓값 | 연속 연산의 평균 비용 | | 입력 가정 | 확률 분포 필요 | **어떤 입력이든 성립** | | 예시 | QuickSort: 평균 O(n log n) | Dynamic Array: Amortized O(1) 삽입 | **Splay Tree의 핵심**: - Average O(log n): 랜덤 접근일 때만 보장 - **Amortized O(log n): 최악의 접근 패턴에서도 보장**