서론
의문
Splay 트리의 zig-zig 연산은 x-p 회전보다 p-g 회전을 먼저 하는데, 그 이유는 뭘까?
(접근하는 노드를 x, 그 부모를 p, p의 부모 즉, x의 조부모를 g라 하자)
사실 x-p 회전 → p-g 회전으로 해도 결국 x는 루트로 잘 올라간다.
그래서 “직관적으로 어색한 p-g 회전을 먼저 하는 이유는 무엇일까?” 하는 의문이 든다.
GPT, Perplexity, Gemini 등 여러 AI에게 물어보고 검색도 해보았는데 명쾌한 답을 듣지 못했고, 나름대로 이해한 것을 정리해본다.
(지금 생각해보면, 얘네가 최선의 답을 해주었고, 그 당시 나의 이해가 부족했다.)
Splay Tree란 무엇인가?
→ 이 글의 핵심인 zig-zig 연산의 순서가 왜 그러한가에 대해 궁금하시면 skip하고 본론으로 가세요.
Splay Tree 특징
접근한 노드를 항상 루트로 끌어올림(Splaying, 한번 접근한 노드는 다음에 또 접근할 확률이 높다는 생각)
최근에 접근한 노드 주변을 빠르게 접근 가능하게 최적화
명시적 균형 정보를 저장하지 않아도 amortized O(log n) 성능 보장
Splay Tree의 회전
Splay Tree에서 루트까지 노드를 올릴 때 사용하는 회전 연산은 크게 3가지
노드를 zig-zig 또는 zig-zag 회전으로 루트 또는 루트 바로 아래 올때까지 올린다.
루트 바로 아래에 위치하게되면 zig 연산을 해서 루트로 올린다.
회전 원칙은 목표 노드가 위로 올라오게, 이진 검색 트리 구조가 유지되도록 하면 된다.
1. Zig:
x가 루트 바로 아래에 있는 경우
한 번 회전으로 x를 루트로 올림
예시
zig 회전(x-p) 전
p
/ \
x C
/ \
A B
zig 회전(x-p) 후
x
/ \
A p
/ \
B C
2. Zig-Zig:
x와 p가 같은 방향으로 내려가 있을 때
(x가 왼쪽 자식의 왼쪽 자식 OR 오른쪽 자식의 오른쪽 자식)
p-g 회전 → x-p 회전 순서로 루트로 올림
예시
zig-zig 회전 전
g
/ \
p D
/ \
x C
/ \
A B
zig-zig step1: p-g 회전
p
/ \
x g
/ \ / \
A B C D
zig-zig step2: x-p 회전
x
/ \
A p
/ \
B g
/ \
C D
3. Zig-Zag:
x와 p가 반대 방향으로 내려가 있을 때
(x가 왼쪽 자식의 오른쪽 자식 OR 오른쪽 자식의 왼쪽 자식)
x-p 회전 → x-g 회전 순서로 루트로 올림
예시
zig-zag 회전 전
g
/ \
p D
/ \
A x
/ \
B C
zig-zag step1: x-p 회전
g
/ \
x D
/ \
p C
/ \
A B
zig-zag step2: x-g 회전
x
/ \
p g
/ \ / \
A B C D
본론
직관적 이해
Splay 트리의 목적은 단순히
- 접근한 노드를 루트로 끌어올리는 것뿐아니라
- x의 서브트리 깊이를 줄이는데 유리함
- x 주변 노드까지 가는 경로가 많이 치우친 경우 이를 완화해줌
p-g 회전을 먼저해야 아래의 목적도 달성할 수 있다.
p-g 회전을 먼저 하면 유리함
x-p 회전 후 x-g 회전하는 경우: 두 번의 회전을 하면 x는 2레벨 올라오지만, x의 서브트리 중 올라가지 못하는 것이 있을 수 있다.p-g 회전 후 x-p 회전하는 경우: 두 번의 회전을 하면 x는 2레벨 올라가고, x의 서브트리는 적어도 1레벨 올라간다. zig-zag 역시 마찬가지다. 따라서 x를 루트까지 올리면 x의 서브트리는 그 레벨이 대략 절반이 된다.
즉, p-g 회전을 먼저해야 x의 서브트리 깊이를 줄이는데 유리하다.
p-g 회전 후 x-p 회전
회전 전 회전 후(올바른 zig-zig)
----------------------------------------------------
g x
/ \ / \
p D A p
/ \ / \
x C B g
/ \ / \
A B C D
x의 서브 트리 A, B는 각각 2레벨, 1레벨 올라갔다.
x-p 회전 후 x-g 회전
회전 전 회전 후(잘못된 zig-zig)
-------------------------------------------------------
g x
/ \ / \
p D A g
/ \ / \
x C p D
/ \ / \
A B B C
x의 서브 트리 A, B는 각각 2레벨, 0레벨 올라갔다.
예시
7
/
6
/
5
/
4
/
3
/
2
/
1
위 트리에서 1을 노드까지 올린다고 해보자.
잘못된 zig-zig(x-p 회전 후 x-g 회전) 적용
1
\
7
/
6
/
5
/
4
/
3
/
2
1이 루트로 가긴 하지만, 치우침이 별로 개선되지 않고, 1의 서브트리는 여전히 깊다.
올바른 zig-zig(p-g 회전 후 x-p 회전) 적용
1
\
6
/ \
4 7
/ \
2 5
\
3
1이 루트로 가고, 치우침이 개선되고, 1의 서브트리 깊이가 적어진다.
p-g 회전을 먼저하고 x-p 회전을 하면 7, 5, 3 노드처럼 삐죽 삐죽한 구조가 생기는데, 이게 치우침을 개선해준다.
그래서 그게 진짜 더 좋은거야?
그러면 이제, 의문이 든다.
뭐 대충 말고 진짜 더 좋은게 맞냐?
p-g 회전을 먼저했을 때 불리한 노드도 있을 수 있고, 치우침이 완화가 약한 경우도 있을 수 있지 않냐?
사실 그렇다.
그럼에도 p-g 회전 먼저하는게 정말로 더 유리해요.
를 설명하려면 결국 Splay Tree가 amortized O(log n) 임을 보이면 된다.
Access Lemma와 잠재함수
Splay Tree의 놀라운 점은 명시적 높이 제한이 없음에도 불구하고 amortized O(log n) 성능을 보장한다는 것이다.
이를 증명하는 핵심은 Access Lemma와 잠재함수다.
용어 정리
- size(x): 노드 x의 서브트리에 속한 노드 개수(자신 포함)
- rank(x) = log₂(size(x)): 로그의 밑은 1보다 크면 얼마이든 상관 없다.
- 잠재함수 Φ = Σ rank(x): 트리 전체의 “숨은 비용”
예시1: 균형 잡힌 트리
7
/ \
3 3
/ \ / \
1 1 1 1
(편의상 노드의 값이 아닌 노드의 size를 표기함) 이때, size의 합은 7+(3+3)+(1+1+1+1)=17이고
rank의 합 Φ은 log₂(7×3×3×1×1×1×1)=log₂63이다.
예시2: 치우친 트리
7
/
6
/
5
/
4
/
3
/
2
/
1
(편의상 노드의 값이 아닌 노드의 size를 표기함) 이때, size의 합은 7+6+5+4+3+2+1=28이고
rank의 합 Φ은 log₂(7×6×5×4×3×2×1)=log₂5040이다.
치우친 트리일수록 잠재 함수 Φ의 값이 커지는 것을 알 수 있다.
잠재함수
잠재함수는 마치 대출 같다.
- 현재 트리가 얼마나 균형잡혀있는 지 측정하는 함수이다
- 치우칠수록 증가하고 균형잡힐수록 감소한다.
- 트리가 매우 치우쳐있고 깊이 있는 노드를 탐색해야하는 경우, 이 노드를 루트로 올리기는데 많은 회전(실제 비용)이 발생한다.
- 하지만 이 과정에서 트리가 균형이 잡히면서 잠재함수(대출)이 감소하여 회전 비용을 상쇄할 수 있다.
- 따라서 분할상환비용 = 실제 비용(실제 회전 수) + 잠재함수 변화량 으로 정의된다.
예시
초기 상태
7
/
6
/
5
/
4
/
3
/
2
/
1
잠재함수 Φ = log₂(7×6×5×4×3×2×1)=log₂5040
여기에서 zig-zig을 한번 해보자.
zig-zig 1회
7
/
6
/
5
/
4
/
1
\
2
\
3이 경우 잠재함수 Φ' = log₂(7×6×5×4×3×2×1)이며 회전은 두 번 했다(p-g, x-p)
따라서 잠재함수 변화량(Φ'-Φ)은 0이고,
분할상환비용 = 2 + 0
zig-zig 2회
7
/
6
/
1
\
4
/ \
2 5
\
3이 경우 잠재함수 Φ'' = log₂(7×6×5×4×2×2×1)이며 회전은 두 번
따라서 잠재함수 변화량(Φ''-Φ')은 log₂(2/3)이고,
분할상환비용 = 2 + log₂(2/3)이다.
잠재함수 변화량이 음수인데, 트리가 더 균형잡히게 변했다는 뜻이다.
zig-zig 3회
1
\
6
/ \
4 7
/ \
2 5
\
3
이 경우 잠재함수 Φ''' = log₂(7×6×4×1×2×1×1)이며 회전은 두 번
따라서 잠재함수 변화량변화량(Φ'''-Φ'')은 log₂(1/10)이고,
분할상환비용 = 2 + log₂(1/10)이다.
마찬가지로 잠재함수 변화량이 음수, 트리가 더 균형잡히게 변했다.
모두 합치면
1을 루트로 끌어올리기 전인 초기 상태와 마지막 상태를 비교하면,
회전은 6번 일어났고, 잠재함수 변화량을 모두 더하면 0+ log₂(2/3)+log₂(1/10) 이다.
따라서 모든 분할상환비용을 더해주면
6 + log₂(2/3)+log₂(1/10)이다.
Access Lemma 증명 개요(아이디어)
분할상환비용 = 실제 비용(실제 회전 수) + 잠재함수 변화량
- 잠재함수 변화량이 작다면, 실제 회전이 많은 경우(치우친 트리)가 있더라도 모든 분할상환비용을 더할 때 이를 만회할 수 있다.
- 잠재함수를 계산할 때는 각 노드의 서브트리 개수를 세면 된다.
- 그런데 비교 전 후의 달라진 부분만 비교 하면 변화량을 알 수 있다.
- 그렇다면 zig, zig-zig, zig-zag의 경우로 케이스를 나누어, 서브트리가 달라진 부분을 비교하면 잠재함수 변화량을 계산할 수 있고, 적당한 부등식을 세워 상한을 잡을 수 있다.
사용되는 수학적 아이디어
- 적당한 부등식을 잡을 때는 루트의 rank가 다른 노드의 rank보다 크거나 같다는 자명한 사실이 사용된다.
- 고등학교 수열 단원에서 부분 분수 기억나는가? 쭉 더하면 제일 앞, 뒤만 남고 서로 상쇄되어 사라지던 것. 잠재함수의 변화량을 더할 때 이렇게 쭉 상쇄되는 성질(텔레스코핑)을 이용한다.
- 로그의 합에서 부등식을 만들 때 산술 평균, 기하 평균을 비교한 a+b >= 2√ab 부등식이 사용된다.
다음에는
- 실제 Access Lemma를 증명을 살펴보자.
- 그 전에, 이제 다시 zig-zig 회전 전 후 그림을 봐보자.
- 잠재함수 변화량을 계산하려면, rank가 달라진 노드가 누구인지 쨰려보며 된다.
- 그게 보이면, 이제 약간의 수학적 식 조작만 들어가면 Access Lemma를 증명할 수 있다.
회전 전 zig-zig 회전 후
----------------------------------------------------
g x
/ \ / \
p D A p
/ \ / \
x C B g
/ \ / \
A B C D
참고 문헌
