지난 글 요약
-
Splay 트리와 기본 연산(zig, zig-zig, zig-zag)에 대해 소개했다.
-
zig-zig 연산을 할 때 x-p 회전보다 p-g 회전을 먼저 하는 것에 대한 의문을 제기했다.
-
p-g 연산을 먼저하면 아래와 같은 장점이 있음을 구체적인 예시를 통해 확인해보았다.
- 극단적으로 치우친 경우 트리가 더 균형잡힌다.
- 접근한 노드의 서브트리가 훨씬 루트에 가깝게 올라온다.
-
잠재함수와 관련 용어를 소개하고 구체적인 예시에서 확인해보았다.
- size(x): 노드 x의 서브트리에 속한 노드 개수(자신 포함)
- rank(x) = log₂(size(x)): 로그의 밑은 1보다 크면 얼마이든 상관 없다.
- 잠재함수 Φ = Σ rank(x): 트리 전체의 “숨은 비용”, 트리가 균형잡히면 작아지고, 치우치면 커진다.
- 분할상환비용 = 실제 비용(실제 회전 수) + 잠재함수 변화량
본론
Access Lemma
루트 노드가 root인 트리에서 노드 x를 splay 하는 분할상환비용은
3(rank(root) - 3rank(x)) + 1
이하이다.
- x를 splay 한다는 것은 splay 기본 연산을 반복적으로 적용하여 x를 루트까지 올린다는 것이다.
- 위 결과를 rank 가 아닌 size를 이용해 나타내고, big-O 표기법을 이용하면 분할상환비용이
O(log(size(root)/size(x))) 임을 알 수 있다. - 아래 증명을 시작하기 전에 분할상환비용 = 실제 비용(실제 회전 수) + 잠재함수 변화량
임을 기억하자.
잠재함수 변화량 분석
zig 연산
회전 전 회전 후
----------------------------------------------------
p x'
/ \ / \
x C A' p'
/ \ / \
A B B' C'
-
rank(node) 는 node 자신을 포함하여 그 아래에 있는 모든 노드의 개수에 로그를 취한 값이다.
-
그런데 A, B, C는 zig 연산 전, 후에 아래에 달린 것?이 그대로임을 알 수 있다.
-
그러니까 p, g만 rank가 변한다.
-
따라서
(잠재함수 변화량 ΔΦ )
= rank(x') + rank(p') - rank(x) - rank(p)
= rank(p') - rank(x)
≤ rank(x') - rank(x)
이다. -
왜냐면, 변화 전 후에 루트 노드의 rank는 일정하며, 트리에서 루트 노드의 rank가 가장 크기 때문이다.
zig-zig 연산
회전 전 회전 후(올바른 zig-zig)
----------------------------------------------------
g x'
/ \ / \
p D A' p'
/ \ / \
x C B' g'
/ \ / \
A B C' D'
-
마찬가지로, 노드 x에 zig-zig 연산을 했을 때 잠재함수 변화량에 대한 부등식을 x에 대한 rank로 나타내보자.
ΔΦ
= rank(x') + rank(p') + rank(g') - rank(x) - rank(p) - rank(g)
= (rank(p') - rank(p)) + (rank(g') - rank(x))
≤ 3(rank(x') - rank(x)) - 2
이 되는데 설명이 필요할 것이다. -
1) 첫번째 등식에서 g, x' 이 루트노드로 rank(g) = rank(x') 이라 상쇄되어
ΔΦ
= rank(p') + rank(g') - rank(x) - rank(p)
- 2) rank(p), rank(p') 을 rank(x), rank(x') 으로 표현하자.
자식의 rank 값이 더 작으므로 rank(x) ≤ rank(p), rank(p') ≤ rank(x') 이므로
ΔΦ
≤ rank(x') + rank(g') - rank(x) - rank(x)
= rank(x') + rank(g') - 2rank(x)
- 3) rank(g') 을 rank(x') 로 표현하자.
먼저, 산술기하 부등식에 의해
log₂a + log₂b ≤ 2log₂((a+b)/2) 임을 알 수 있다.
그런데 size(x) + size(g') ≤ size(x') 이므로
rank(x) + rank(g')
= log₂(size(x)) + log₂(size(g'))
≤ 2log₂((size(x) + size(g') / 2)
≤ 2log₂(size(x') / 2)
= 2log₂(size(x')) - 2
= 2rank(x') - 2
따라서 rank(g') ≤ 2rank(x') - rank(x) - 2 이고 이를 2)에서 구한 식에 적용하면
ΔΦ
≤ rank(x') + rank(g') - 2rank(x)
≤ 3rank(x') - 3rank(x) - 2
zig-zag 연산
은 zig-zig과 비슷하므로 생략하겠다.
결과는 마찬가지로
ΔΦ ≤ 3rank(x') - 3rank(x) - 2
splay 분할상환비용
zig의 분할상환비용
- zig은 회전 1회이므로 실제 비용 1
- zig의 ΔΦ ≤ rank(x') - rank(x)
- zig의 분할상환비용
≤ 1 + rank(x') - rank(x)
≤ 1 + 3(rank(x') - rank(x))
zig-zig의 분할상환비용
- zig-zig은 회전 2회이므로 실제 비용 2
- zig-zig의 ΔΦ ≤ 3rank(x') - 3rank(x) - 2
- zig-zig의 분할상환비용
≤ 3(rank(x') - rank(x))
zig-zag의 분할상환비용
- zig-zig과 마찬가지로
- zig-zag의 분할상환비용
≤ 3(rank(x') - rank(x))
결과적으로 spaly 분할상환비용
- x노드를 루트까지 올리기 위해 zig, zig-zig, zig-zag을 반복적으로 적용할 때,
- 이번 스텝에서 rank(x')이 다음 스텝에서의 rank(x)가 된다.
- 따라서 중간 항들은 모두 소거가 되고,
- x를 루트까지 올리기 위한 분할상환비용 즉,
- 각 스텝에서 연산의 분할상환비용의 합 은
- 3(rank(root)-rank(x)) + 1 이하이다.
증명을 완료했다... 다 쓰고 검색해보니까 Velog도 latex 문법으로 수식을 쓸 수 있구나...
다음에는
- splay 트리의 다른 재밌는 성질들을 알아볼까?
- B트리 계열의 트리에 대해 살펴볼까?
- 외울게 많아 어려운 UNIX, 리눅스를 어떻게 공부하면 좋을지 고민해볼까?
참고 문헌
