스케이프고트 트리

스케이프고트 트리
스케이프고트 트리
종류	트리
발명일	1989
발명자	아르네 안데르손, 이갈 갈페린, 로널드 L. 리베스트
점근표기법으로 된 시간복잡도
알고리즘
알고리즘
공간
탐색
삽입
삭제

컴퓨터 과학에서 스케이프고트 트리(Scapegoat tree)는 1989년 아르네 안데르손^[2]이, 그리고 1993년 이갈 갈페린과 로널드 L. 리베스트가 다시 발명한 자가 균형 이진 탐색 트리이다.^[1] 이 트리는 최악의 경우 ${\color {Blue}O(\log n)}$ 탐색 시간(n은 엔트리 개수)과 $O(\log n)$ 의 분할 상환 삽입 및 삭제 시간을 제공한다.

최악의 경우 $O(\log n)$ 탐색 시간을 제공하는 다른 대부분의 자가 균형 이진 탐색 트리와 달리, 스케이프고트 트리는 일반적인 이진 탐색 트리에 비해 노드당 추가 메모리 오버헤드가 없다: 키와 값 외에, 노드는 자식 노드에 대한 두 개의 포인터만 저장한다. 이는 스케이프고트 트리를 구현하기 쉽게 만들고, 데이터 구조 정렬 덕분에 노드 오버헤드를 최대 3분의 1까지 줄일 수 있다.

대부분의 균형 트리 알고리즘에서 사용되는 작고 점진적인 재균형 작업 대신, 스케이프고트 트리는 드물지만 비용이 많이 드는 "희생양"을 선택하여 희생양을 뿌리로 하는 서브트리를 완전한 이진 트리로 완전히 재구성한다. 따라서 스케이프고트 트리는 최악의 경우 $O(n)$ 의 갱신 성능을 가진다.

이론

이진 탐색 트리는 노드의 절반이 루트의 왼쪽에 있고 절반이 오른쪽에 있으면 무게 균형이 잡혀 있다고 말한다. 알파-무게 균형 노드는 완화된 무게 균형 기준을 충족하는 것으로 정의된다:

size(left) ≤ α*size(node)
size(right) ≤ α*size(node)

여기서 size는 재귀적으로 정의될 수 있다:

함수 size(node) 는
    만약 node = nil 이면
        반환 0
    그렇지 않으면
        반환 size(node->left) + size(node->right) + 1
    종료
함수 종료

심지어 퇴화된 트리(연결 리스트)도 α=1이면 이 조건을 만족하지만, α=0.5이면 거의 완전 이진 트리만 일치한다.

알파-무게 균형 이진 탐색 트리는 또한 알파-높이 균형이어야 한다. 즉,

height(tree) ≤ floor(log_1/α(size(tree)))

대우에 의해, 알파-높이 균형이 아닌 트리는 알파-무게 균형이 아니다.

스케이프고트 트리는 항상 알파-무게 균형을 유지한다고 보장되지는 않지만, 항상 느슨하게 알파-높이 균형을 유지한다. 즉,

height(scapegoat tree) ≤ floor(log_1/α(size(tree))) + 1.

이 높이 균형 조건의 위반은 삽입 시점에 감지될 수 있으며, 이는 무게 균형 조건의 위반이 존재해야 함을 의미한다.

이것은 스케이프고트 트리를 레드-블랙 트리와 유사하게 만들며, 둘 다 높이에 대한 제약이 있다. 그러나 회전(또는 스케이프고트 트리의 경우, 재균형)이 발생하는 위치를 결정하는 구현 방식에서는 크게 다르다. 레드-블랙 트리는 각 노드에 추가 '색상' 정보를 저장하여 위치를 결정하는 반면, 스케이프고트 트리는 알파-무게 균형이 아닌 희생양을 찾아 재균형 작업을 수행한다. 이는 AVL 트리와 느슨하게 유사하며, 실제 회전은 노드의 '균형'에 따라 달라지지만, 균형을 결정하는 방식은 크게 다르다. AVL 트리는 모든 삽입/삭제 시 균형 값을 확인하므로 일반적으로 각 노드에 저장되지만, 스케이프고트 트리는 필요할 때만 계산할 수 있으며, 이는 희생양을 찾아야 할 때만 해당된다.

다른 대부분의 자가 균형 탐색 트리와 달리, 스케이프고트 트리는 균형에 있어 완전히 유연하다. 이들은 0.5 < α < 1인 모든 α 값을 지원한다. 높은 α 값은 재균형을 적게 발생시켜 삽입을 빠르게 하지만, 탐색과 삭제는 느려지며, 낮은 α 값은 그 반대이다. 따라서 실제 응용에서는 이러한 작업이 얼마나 자주 수행되어야 하는지에 따라 α 값을 선택할 수 있다.

작업

탐색

탐색은 표준 이진 탐색 트리에서 수정되지 않았으며, 최악의 경우 시간은 $O(\log n)$ 이다. 이는 최악의 경우 시간이 $O(n)$ 인 스플레이 트리와 대조된다. 다른 자가 균형 이진 탐색 트리에 비해 노드 메모리 오버헤드가 줄어들어 참조 국부성 및 캐싱을 더욱 향상시킬 수 있다.

삽입

삽입은 불균형 이진 탐색 트리와 동일한 기본 아이디어로 구현되지만, 몇 가지 중요한 변경 사항이 있다.

삽입 지점을 찾을 때, 새 노드의 깊이도 기록해야 한다. 이는 탐색의 각 반복 중에 증가하는 간단한 카운터를 통해 구현되며, 루트와 삽입된 노드 사이의 에지 수를 효과적으로 계산한다. 이 노드가 알파-높이 균형 속성(위에서 정의됨)을 위반하면 재균형이 필요하다.

재균형을 위해 희생양을 루트로 하는 전체 서브트리가 균형화 작업을 거친다. 희생양은 삽입된 노드의 조상 중에서 알파-무게 균형이 아닌 노드로 정의된다. 이러한 조상은 항상 하나 이상 존재한다. 그 중 하나를 재균형하면 알파-높이 균형 속성이 복원된다.

희생양을 찾는 한 가지 방법은 새 노드에서 루트로 다시 올라가서 알파-무게 균형이 아닌 첫 번째 노드를 선택하는 것이다.

루트로 다시 올라가려면 스택에 할당되거나 부모 포인터로 사용되는 $O(\log n)$ 의 저장 공간이 필요하다. 이는 각 자식을 내려갈 때 부모를 가리키게 하고, 다시 올라갈 때 수정함으로써 실제로 피할 수 있다.

잠재적인 노드가 유효한 희생양인지 확인하려면 해당 노드의 알파-무게 균형 속성을 확인해야 한다. 이를 위해 정의로 돌아갈 수 있다:

size(left) ≤ α*size(node)
size(right) ≤ α*size(node)

그러나 세 가지 크기 중 두 가지를 이미 알고 있으므로 세 번째만 계산하면 된다는 것을 깨달으면 큰 최적화를 할 수 있다.

이를 시연하기 위해 다음 예제를 고려해보자. 루트로 다시 올라간다고 가정하면:

size(parent) = size(node) + size(sibling) + 1

그러나:

size(inserted node) = 1.

이 경우는 다음과 같이 단순화된다:

size[x+1] = size[x] + size(sibling) + 1

여기서 x = 이 노드, x + 1 = 부모이며 size(sibling)이 실제로 필요한 유일한 함수 호출이다.

희생양을 찾으면 희생양을 루트로 하는 서브트리는 완전히 균형 잡힌 상태로 재구성된다.^[1] 이는 서브트리의 노드를 순회하여 정렬된 순서로 값을 찾고 재귀적으로 중앙값을 서브트리의 루트로 선택함으로써 $O(n)$ 시간 안에 수행할 수 있다.

재균형 작업은 $O(n)$ 시간(서브트리 노드 수에 따라 달라짐)이 걸리므로, 삽입은 최악의 경우 $O(n)$ 시간이 걸린다. 그러나 이러한 최악의 시나리오가 분산되어 있으므로 삽입은 $O(\log n)$ 의 분할 상환 시간이 걸린다.

삽입 비용 증명 스케치

노드 v의 불균형(Imbalance)을 왼쪽 노드와 오른쪽 노드의 크기 차이의 절댓값에서 1을 뺀 값 또는 0 중 큰 값으로 정의한다. 다시 말해:

$I(v)=\operatorname {max} (|\operatorname {left} (v)-\operatorname {right} (v)|-1,0)$

v를 뿌리로 하는 서브트리를 재구성한 직후, I(v) = 0이다.

보조 정리: v를 뿌리로 하는 서브트리를 재구성하기 직전,
$I(v)\in \Omega (|v|)$
( $\Omega$ 는 빅 오메가 표기법이다.)

보조 정리의 증명:

$v_{0}$ 가 재구성 직후 서브트리의 루트라고 하자. $h(v_{0})=\log(|v_{0}|+1)$ 이다. 만약 $\Omega (|v_{0}|)$ 개의 퇴화 삽입(즉, 삽입된 각 노드가 높이를 1씩 증가시키는 경우)이 있다면,
$I(v)\in \Omega (|v_{0}|)$ ,
$h(v)=h(v_{0})+\Omega (|v_{0}|)$ 이고
$\log(|v|)\leq \log(|v_{0}|+1)+1$ 이다.

재구성 전에 $I(v)\in \Omega (|v|)$ 이므로, $v$ 를 뿌리로 하는 서브트리에 $\Omega (|v|)$ 개의 삽입이 있었고, 이 삽입들은 재구성으로 이어지지 않았다. 이 삽입들은 각각 $O(\log n)$ 시간에 수행될 수 있다. 재구성을 유발하는 마지막 삽입 비용은 $O(|v|)$ 이다. 총합 분석을 사용하면 삽입의 분할 상환 비용이 $O(\log n)$ 이라는 것이 분명해진다:

${\Omega (|v|)O(\log n)+O(|v|) \over \Omega (|v|)}=O(\log n)$

삭제

스케이프고트 트리는 삭제가 삽입보다 쉽다는 점에서 특이하다. 삭제를 가능하게 하려면 스케이프고트 트리는 트리 데이터 구조와 함께 추가 값을 저장해야 한다. 이 속성을 MaxNodeCount라고 부르며, 이는 단순히 도달한 최고 NodeCount를 나타낸다. 전체 트리가 재균형될 때마다 NodeCount로 설정되며, 삽입 후에는 max(MaxNodeCount, NodeCount)로 설정된다.

삭제를 수행하려면 단순 이진 탐색 트리에서와 같이 노드를 제거하면 되지만,

NodeCount ≤ α*MaxNodeCount

이면 루트를 중심으로 전체 트리를 재균형하고, MaxNodeCount를 NodeCount로 설정하는 것을 잊지 말아야 한다.

이는 삭제에 최악의 경우 $O(n)$ 시간을 제공하며, 분할 상환 시간은 $O(\log n)$ 이다.

삭제 비용 증명 스케치

스케이프고트 트리가 $n$ 개의 요소를 가지고 방금 재구성되었다고 가정해 보자(다시 말해, 완전 이진 트리이다). 트리가 재구성되기 전에 최대 $n/2-1$ 개의 삭제가 수행될 수 있다. 이 삭제들은 각각 $O(\log n)$ 시간이 걸린다(요소를 찾고 삭제된 것으로 표시하는 데 걸리는 시간). $n/2$ 번째 삭제는 트리가 재구성되도록 하고 $O(\log n)+O(n)$ (또는 그냥 $O(n)$ ) 시간이 걸린다. 총합 분석을 사용하면 삭제의 분할 상환 비용이 $O(\log n)$ 이라는 것이 분명해진다: