14. Augmenting Data Structures

적-흑 트리를 보강해서 만들 수 있는 두 종류의 자료구조를 알아보자.

14.1. Dynamic order statistics

9장에서 임의의 정렬되지 않은 집합의 순서 통계량을 O(n)에 계산하는 법을 알아보았다. 적-흑 트리를 이용해 이를 O(\lg n)으로 발전시킬 수 있고, 특정 원소의 순위O(\lg n)에 알아볼 수도 있다. 순서-통계량 트리는 적-흑 트리에 x를 루트로 하는 부분 트리의 노드의 전체 수인 x.size를 같이 저장하는 트리이다. 여기서 x.size = x.left.size + x.right.size + 1, T.nil.size = 0이 된다. 트리 내의 키들이 꼭 달라야 필요는 없지만 이 경우에는 원소의 순위가 잘 정의되지 않을 수 있기 때문에, 이 경우 원소의 순위는 트리를 중위 순회했을 때 방문하는 순서로 정의한다.

Retrieving an element with a given rank

x를 루트로 하는 부분 트리의 i번째 순서 통계량은 다음 알고리즘으로 구한다.

OS-SELECT(x, i)
r = x.left.size + 1
if i == r
    return x
else if i < r
    return OS-SELECT(x.left, i)
else
    return OS-SELECT(x.right, i - r)

이의 전체 수행 시간은 트리의 높이를 넘지 않으므로, 적-흑 트리일 경우에 O(\lg n)이다.

Determining the rank of an element

순서-통계량 트리 내 특정 원소의 포인터가 있을 때, 그 원소의 순서는 다음 알고리즘으로 구한다.

OS-RANK(T, x)
r = x.left.size + 1
y = x
while y ≠ T.root
    if y == y.p.right
         r = r + y.p.left.size + 1
    y = y.p
return r

이의 전체 수행 시간은 트리의 높이를 넘지 않으므로, 적-흑 트리일 경우에 O(\lg n)이다.

Maintaining subtree sizes

위의 두 알고리즘이 정상적으로 동작하려면 적-흑 트리의 연산들 내에서 부분 트리의 크기를 보존할 수 있어야 한다. 트리에 원소를 삽입하는 것은 두 단계로 이루어진다 : 원소를 삽입하는 것과 적-흑 특성의 유지를 위해 트리를 회전하는 것. 원소를 삽입한 이후에는 루트와 그 새로 삽입된 원소를 연결하는 경로의 size를 1씩 늘린다. 트리를 회전할 때에는 최대 2개의 노드의 size만 바꿔 주면 되는데, 원소 삽입 시마다 최대 2회의 회전이 필요하므로 추가되는 수행 시간은 O(1)이다. 트리에서 원소를 삭제하는 것도 역시 두 단계로 이루어진다 : 원소를 삭제하는 것과 적-흑 특성의 유지를 위해 트리를 회전하는 것. 원소를 삭제한 이후에는 루트와 그 삭제된 원소를 연결하는 경로의 size를 1씩 줄인다. 트리를 회전할 때에는, 삽입할 때와 마찬가지로 추가되는 수행 시간은 O(1)이다. 그러므로, 순서-통계량 트리에서 삽입/삭제를 수행할 때 동적 연산의 O(\lg n) 특성을 깨지 않으면서 부분 트리 크기를 유지할 수 있다.

14.2. How to augment a data structure

기본 자료 구조를 보강하는 과정은 대개 다음과 같다.

  • 기반 자료 구조를 고른다.
  • 기반 자료 구조에 추가할 정보를 선택한다.
  • 기반 자료 구조의 기본 연산들에서 추가할 정보를 유지할 수 있음을 증명한다.
  • 새 연산들을 짠다.

Augmenting red-black trees

적-흑 트리는 보강의 대상으로 삼을 때 이점이 있다.

Theorem. (Augmenting a red-black tree) 노드 n개의 적-흑 트리 T에 대해 특성 f를 보강할 때, 각 노드 x에 대해 특성 f가 x, x.left, x.right, x.left.f, x.right.f에만 의존한다면, T의 삽입/삭제 연산에서 O(\lg n) 성능을 깨지 않고 특성 f를 보존할 수 있다.

14.3. Interval trees

폐구간 [t_{1}, t_{2}]\{t \in \mathbb{R} : t_{1} \leq t \leq t_{2}\}를 나타낸다. 개구간반개구간은 폐구간에서 끝점이 둘 다 또는 둘 중 하나가 빠진 것이다. 이 장에서 구간들은 폐구간으로 가정한다. 폐구간 i = [t_{1}, t_{2}]에 대해서 i.low = t_{1}(아래쪽 끝점), i.high = t_{2}(위쪽 끝점)으로 잡고, 구간의 교집합이 공집합이 아니면 겹친다고 한다. 구간은 다음의 구간 삼분성질을 만족한다. 즉, 구간 둘에 대해 다음 셋 중 정확히 하나가 성립한다.

  • 두 구간이 겹친다.
  • 구간 i가 구간 j의 왼쪽에 있다.
  • 구간 i가 구간 j의 오른쪽에 있다.

구간 트리는 적-흑 트리의 각 노드가 구간을 들고 있는 것이다. 이는 다음의 연산들을 지원한다.

  • INTERVAL-INSERT(T, x) : 구간 트리 T에 구간 노드 x를 추가한다.
  • INTERVAL-DELETE(T, x) : 구간 트리 T에서 구간 노드 x를 삭제한다.
  • INTERVAL-SEARCH(T, i) : 구간 트리 T에서 구간 i와 겹치는 구간 노드 x의 포인터를 리턴한다. 그런 노드가 없으면 T.nil을 리턴한다.

INTERVAL-SEARCH는 다음과 같이 정의된다.

INTERVAL-SEARCH(T, i)
x = T.root
while x ≠ T.nil and i does not overlap x.int
    if x.left ≠ T.nil and x.left.max ≥ i.low
        x = x.left
    else
        x = x.right
return x

Theorem. INTERVAL-SEARCH(T, i)는 구간 트리 T에서 구간 i와 겹치는 구간 노드가 존재할 경우 그 노드의 포인터를 리턴한다. 그런 노드가 없으면 T.nil을 리턴한다.

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중