14 Augmenting Data Structures

Augmenting Data Structures14.1 Dynamic order statisticsRetrieving an element with a given rankDetermining the rank of an elementMaintaining subtree sizes14.2 How to augment a data structureAugmenting red-black trees14.3 Interval trees

Augmenting Data Structures

어떤 enginerring situations은 "textbook" data structures이상으로 요구하지 않는다 - doubly linked list, hash table, 또는 binary search tree 같이 - 그러나 많은 다른 것들은 소량의 창조성을 요구한다. 오직 희귀한 상황에서만 너는 전적으로 새로운 data structure를 만들 필요가 있을 것이다. 좀 더 종종, textbook data structure에 추가 정보를 저장하여 그 자료구조를 보강하는 것이 충분할 것이다. 너는 그러고나서 요구되는 어플리케이션을 지원하는 자료구조를 위한 새로운 연산을 프로그래밍할 수 있다. 자료구조를 보충하는 것은 항상 그러나 간단하지 않다. 그 추가된 정보가 그 자료구조에 동작하는 일반 연산에 의해 업데이트되고 유지되어야 하기 때문이다.

$i$ 번째로 가장 작은 number를 빠르게 찾을 수 있다. Section 14.2는 한 자료구조를 보강하는 과정을 추상화하고, red-black trees를 보강하는 과정을 간단하게 할 수 있는 theorem를 제공한다. Section 14.3은 time intervals같은 intervals의 dynamic set을 유지하기 위한 자료구조를 설계하는데 도움을 주기 위해 이 정리를 사용한다. 한 query interval이 주어진다면, 우리는 그것과 겹치는 set에서의 한 interval를 빠르게 찾을 수 있다.

14.1 Dynamic order statistics

$i \in \{1, 2, \dots, n \}$ $n$ $i$ $i$ $O(n)$ $O(lg\;n)$ $O(lg\;n)$ time에 한 element의 rank를 연산하는 방법을 또한 볼 것이다 - 이것은 set의 linear order에서의 position이다.

order-statistic tree $T.nil.size$ 가 0으로 설정한다면 - 그러면 우리는 다음의 항등식을 갖는다

x.size = x.left.size + x.right.size + 1

우리는 keys가 order-statistic tree에서 다를 것을 요구하지 않는다. (예를들어, 그림 14.1의 트리는 value 14가 두 개, 그리고 value 21이 두 개의 keyt를 가지고 있다.) 동일한 키의 존재 하에서, rank의 위의 개념은 잘 정의되지 않는다. 우리는 한 element의 rank를 tree의 inorder walk로 프린트될 때의 position으로서 정의하여 order-statistic tree에 대한 이 애매함을 제거한다. 그림 14.1에서, 예를들어, black node에 저장된 key 14는 rank 5를 가지고, red node에 저장된 key 14는 rank 6을 가진다.

Retrieving an element with a given rank

$OS-SELECT(x,i)$ 는 x를 root로 하는 subtree에서 i번째로 가장 작은 key를 포함하는 노드에 대한 포인터를 반환한다. order-statistic tree T에서 i번째로 가장 작은 key를 가진 node를 찾기 위해, 우리는 OS-SELECT(T.root,i)를 호출한다.


OS-SELECT(x,i)
1   r = x.left.size + 1
2   if i == r
3        return x
4   elseif i < r
5        return OS-SELECT(x.left,i)
6   else return OS-SELECT(x.right, i - r)

$x.left.size + 1$ $i = r$ $i < r$ $x.left$ $i > 4$ $x.right$ $(i - r)$ 번째로 가장 작은 element이다. Line 6은 이 element를 재귀로 결정한다.

$17-13 = 4$ $4 - 2 = 2$ 번째로 가장 작은 element를 찾기 위해 다시 한 번 재귀한다. 우리는 이제 그것의 left subtree가 size 1를 가진다는 것을 발견하는데, 그것이 두 번째로 가장 작은 element라는 것을 의미한다. 따라서, 그 procedure는 key 38를 가진 노드에 대한 포인터를 반환한다.

$O(lg\;n)$ $O(lg\;n)$ 이다.

Determining the rank of an element

order-statistic tree T에서 한 node x에 대한 포인터가 주어진다면, 그 procedure OS-RANK는 T의 inroder tree walk로 결정된 linear order에서 x의 positions을 반환한다.


xxxxxxxxxx
OS-RANK(T,x)
1   r = x.left.size + 1
2   y = x
3   while y != T.root
4`      if y == y.p.right
5           r = r + y.p.left.size + 1
6       y = y.p
7   return r

그 procedure는 다음과 같이 작동한다. 우리는 node x의 rank를 inorder tree walk에서 x 전에 잇는 nodes들의 개수로서 생각할 수 있고, x 그 자체에 대해 1를 더한다. OS-RANK는 다음의 loop invariant를 유지한다:

lines 3-6의 while loop의 각 반복의 시작에서, r는 node y를 root로 하는 subtree에서 x.key의 rank이다.

우리는 OS-RARANK 다음과 같이 정확하게 작동하는 것을 보여주기 위해 이 loop invariant를 사용한다.

Initialization: $y = x$ 로 설정하는 것은 line 3에서 test가 실행하는 처음에 그 invariant를 true로 만든다.

Maintenanace:while $y = y.p$ $r$ $x.key$ while $y.p.left.size + 1$ 를 추가한다.

Termination: $y = T.root$ 일 때, 그 loop는 종료한다. 이것은 y를 root로 하는 subtree가 entire tree가 되도록 하기 위해서이다. 따라서 r의 value는 전체 tree에서의 x.key의 rank이다.

한 예제로서, 우리가 그림 14.1의 order-statistic tree에서 key 38를 가진 노드의 rank를 찾기 위해 OS-RANK를 실행할 때, 우리는 while loop의 맨 위에서 y.key와 r의 다음의 연속을 가진 값들은 얻는다:

iteration	y.key	r
1	38	2
2	30	4
3	41	4
4	26	17

그 procedure는 rank 17을 반환한다.

while $O(1)$ $O(lg\;n)$ 이다.

Maintaining subtree sizes

각 node에서 size attribute가 주어진다면, OS-SELECT와 OS-RANK는 order-statistic infromation을 빠르게 연산할 수 있다. 그러나, 만약 우리가 red-black trees에 대한 기본 수정 연산들 내에서 이러한 attributes를 효율적으로 유지할 수 없다면, 우리의 작업은 무가치 한 것이 될 것이다. 우리는 operation의 asymptotic running time에 영향을 미치지 않고 삽입과 삭제 둘 다에 대해 subtree sizes를 유지하는 방법을 보여줄 것이다.

우리는 Section 13.3에서, red-balck tree에 대한 삽입이 두 개의 phases를 구성한다는 것을 보았었다. 그 첫 번째 단계는 root에서 treeㅇ를 내려가서, 존재하는 노드의 child로서 새로운 노드를 넣는 것이다. 그 두 번째 단계는 tree를 올라가서, colors를 바꾸고, red-black properties를 유지하기 위해 rotations을 수행하는 것이다.

$O(lg\;n)$ $O(lg\;n)$ 이다.

두 번째 단계에서, 밑의 red-black tree에 대한 유일한 구조적 변화는 회전에 의해 발생하고, 최대 두 개가 있다. 게다가, 한 회전은 local operation이다 : 즉, 오직 두 개의 노드들만이 그것들의 size attributes를 invalidated되게 한다. 그 rotation이 수행되는 link는 이러한 두 노드들에 대한 incident이다. Section 13.2에 있는 LEFT-ROTATE(T,x)의 코드를 참조하여, 우리는 다음의 lines들을 추가한다:


xxxxxxxxxx
13  y.size = x.size
14  x.size = x.left.size + x.right.size + 1

그림 14.2는 그 attributes가 업데이트 되는 방법을 보여준다. RIGHT-ROTATE에 대한 변화는 대칭적이다.

$O(1)$ $O(lg\;n)$ 이고, 이것은 보통의 red-black tree에 대한 asymptotically하게 같다.

$O(lg\;n)$ size $O(lg\;n)$ $O(1)$ $O(lg\;n)$ time이 거린다.

14.2 How to augment a data structure

추가 기능을 지원하기 위해 기본 자료 구조를 보강하는 과정은 알고리즘 설계에서 꽤 자주 발생한다. 우리는 intervals에 대한 연산을 지원하는 자료구조를 설계하기 위해 다음 섹션에서 그것을 다시 사용할 것이다. 이 섹션에서, 우리는 그러한 보강과 관련된 단계들을 조사한다. 우리는 또한 많은 경우에 red-black trees를 쉽게 보강하게 해주는 theorem을 증명할 것이다.

우리는 자료구조를 보강하는 과정을 4단계로 나눌 수 있다:

underlying data structure를 선택해라.
그 underlaying data structure에서 유지할 추가 정보를 결정해라.
underlying data structure에 대한 basic modifying operations에 대해 추가 정보를 유지할 수 있는지를 검증해라.
새로운 연산을 개발해라.

어떤 규범적인 설계 방법과 함꼐, 너는 주어진 순서대로 그 단계들을 맹목적으로 따라서느 안된다. 대부분의 선계 작업은 시도와 실패를 포함하고, 모든 단계에서의 진행은 보통 병렬로 진행된다. 예르륻ㄹ어 추가 정보를 결정하고 새로운 연산을 만드는 데 있어서 어떠한 요점이 없다 (steps 2와 4), 만약 우리가 추가 정보를 효율적으로 유지할 수 없다면. 그럼에도 불구하고, 이 4단계 방법은 자료 구조를 보강하는 것에 있어서 너의 노력에 대한 좋은 초점을 제공한다. 그래서 보강된 자료구조의 에 대한 문서화를 정리하는 것은 좋은 방법이다.

우리는 우리의 order-statistic trees를 설계하기 위해 Section 14.1에서 이러한 단계들을 따랐었다. step 1에 대해, 우리는 underlying data structure로서 red-black trees를 선택했다. red-black trees의 적합성에 대한 단서는 MINIMUM, MAXIMUM, SUCCESSOR, and PREDECESSOR같은 전체 순서에 대한 다른 dynamic set operations의 그것들의 효율적인 지원으로부터 온다.

$O(lg\;n)$ time에 작동하지 않을 것이다. 가끔씩, 추가 정보는 data라기 보다는 pointer information이다, Exercise 14.2-1에서 처럼.

$O(lg\;n)$ $O(lg\;n)$ nodes에 있는 정보만을 바꾸게 한다.

step 4에 대해, 우리는 OS-SELECT와 OS-RANK 연산들을 개발했었다. 결국, 새로운 연산들에 대한 필요는 우리가 처음에 자료구조를 보강하려고 하는가 이다. 때때로, 새로운 연산을 개발하기 보다, 우리는 Exercise 14.2-1에서 처럼, 존재하는 것을 가속하기위해 추가 정보를 사용한다.

Augmenting red-black trees

red-black trees가 augment data structure를 기반으로 쓸 때, 우리는 insertion와 deletion이 항상 효율적으로 추가 정보의 어떤 종류든지 유지할 수 있다는 것을 증명할 수 있고 ,그것으로 인해 step 3를 매우 쉽게 만든다. 다음의 정리의 증명은 Section 14.1의 주장과 유사한데, 우리가 order-statistic trees를 위한 size attribute를 유지할 수 있다는 것이다.

Theorem 14.1 (Augmenting a red-black tree)

$f$ $O(lg\;n)$ performance에 영향을 미치지 않고.

Proof $f$ $O(lg\;n)$ $f$ $O(lg\;n)$ time을 사용한다.

$O(1)$ $T.nil$ $O(lg\;n)$ $O(lg\;n)$ $O(lg\;n)$ 이다.

$O(lg\;n)$ $O(lg\;n)$ $O(lg\;n)$ 이다.

size $O(1)$ $O(lg\;n)$ 라기 보다. Exercise 14.2-3이 한 예시를 준다.

14.3 Interval trees

closed interval $[t_1, t_2]$ $t_1 \leq t_2$ $[t_1, t_2]$ $\{t \in \mathbb{R} : t_1 \leq t \leq t_2\}$ 를 나타낸다. Open and half-open intervals은 그 집합으로부터 end points의 둘 다 또는 한 개를 각각 생략한다. 이 섹션에서, 우리는 intervals이 closed되어 있다고 가정할 것이다; 즉, 그 결과를 open and half-open intervals로 확장하는 것은 개념적으로 간단하다.

Intervals은 한 event가 연속적인 시간의 주기를 차지하는 events들을 나타내는데 편리하다. 예를들어, 우리는 주어진 interval동안 무슨 events가 발생했는지를 발견하기 위해 time intervals의 database를 query하고 싶을지도 모른다. 이 섹션에서 그 자료구조는 그러한 interval database를 유지하기 위한 효율적인 수단을 제공한다.

$[t_1, t_2]$ $i$ $i.low = t_1$ low endpoint $i.high = t_2$ the high endpoint $i$ $i'$ $i \cap i' \neq \emptyset$ overlap $i.low \leq i'.high$ $i'.low \leq i.high$ $i$ $i'$ 는 interval trichotomy를 만족한다. 즉, 다음의 세 개의 properties중의 하나가 유효하다는 것이다:

$i$ $i'$ 겹친다.
$i$ $i'$ $i.high < i'.low$ )
$i$ $i'$ $i'.high < i.low$ )
interval tree $x.int$ 를 포함하는 elements의 한 dynamic set을 유지하는 red-black tree이다. Interval trees는 다음의 연산을 지원한다.

$int$ attribute는 interval를 포함한다고 가정된다.

INERTVAL-DELETE(T,x)는 interval tree T로부터 element x를 제거한다.

$x.int$ $i$ 와 겹치는 element x에 대한 포인터를 반환하거나, 만약 그러한 element가 집합에 없다면 sentinel T.nil에 대한 포인터를 반환한다.

그림 14.4는 interval tree가 intervals의 한 집합을 어떻게 나타내는지를 보여준다. 우리는 Section 14.2로부터 4단계 메소드를 따를 것인데, 우리가 interval tree의 설계와 그것에 작동하는 연산들을 리뷰하듯이.

Step 1 : Underlying data structure

$x.int$ $x$ $x.int.low$ 인 low end point인 red-black tree를 선택한다. 따라서, 그 자료구조의 inorder tree walk는 low end point로 정렬된 순서로 intervals를 열거한다.

Step 2: Additional information

$x.max$ 를 포함하는데, 이것은 x를 root로 하는 subtree에 저장된 interval endpoint의 maximum value이다.

Step 3: Maintaining the information

$O(lg\;n)$ $x.int$ $x.max$ 를 결정할 수 결정할 수 있고, node x의 children의 max values를 결정할 수 있다:


xxxxxxxxxx
x.max = max(x.int.high, x.left.max, x.right.max).

$O(lg\;n)$ $O(1)$ time에 rotation이후에 max attributes를 업데이트할 수 있다.

Step 4: Developing new operations

$i$ $i$ 와 겹치는 어떠한 interval이 없다면, 그 procedure는 sentinel T.nil에 대한 포인터를 반환한다.


xxxxxxxxxx
INSERT-SEARCH(T,i)
1   x = T.root
2   while x != T.nil and i does not overap x.int
3       if  x.left != T.nil and x.left.max >= i.low
4               x = x.left
5       else    x = x.right
6   return x

$O(1)$ $O(lg\;n)$ $O(lg\;n)$ time이 걸린다.

$i = [22, 25]$ $[16, 21]$ $x.left.max = 23$ $i.low = 22$ 보다 더 크기 때문에, 그 loop는 root의 left child로서 x와 함께 계쏙 한다 - [8, 9]를 포함하는 노드인데, i와 또한 겹치지 않는다. 이번에, x.left.max = 10은 i.low = 22보다 더 작고, 그래서 그 loop는 x의 right child를 새로운 x로서 시작한다. 이 node에 저장된 그 interval [15,23]은 i와 겹치기 때문에, 그 procedure는 이 노드를 반환한다.

$i = [11,14]$ $x.left.max = 23$ $i.low = 11$ $[8,9]$ $x.left.max = 10$ $i.low = 11$ $i$ $T.nil$ 이다. 그래서 다시, 우리는 right로 가고, 그 loop는 종료하고, 우리는 sentinel T.nil를 반환한다.

INTERVAL-SEARCH가 왜 올바른지를 알기 위해, 우리는 root로 부터의 single path를 조사하는 것이 충분한 이유를 이해해야 한다. 그 기본 아이디어는, 어떤 노드 x에서, 만약 x.int가 i랑 겹치지 않다면, 그 탐색은 항상 안전한 방향으로 진행된다는 것이다: 그 탐색은 명백히 그 트리가 한 겹치는 구간이 있다면 그것을 명백히 찾을 것이다. 다음의 정리는 이 property를 좀 더 정확하게 명시한다.

Theorem 14.2

INTERVAL-SEARCH(T,i)의 어떤 실행은 interval이 i와 겹치는 한 노드를 반환하거나, interval이 i랑 겹치는 노드가 tree T가 갖고 있지 않다면 T.nil를 반환한다.

Proofwhile $x = T.nil$ $i$ $x.int$ while $x = T.nil$ 이기 떄문에 종료된다.

우리는 lines 2-5의 while loop에 대해 다음의 invariant를 사용한다:

만약 tree T가 i와 겹치는 interval를 가진다면, 그러면 x를 root로 하는 subtree는 그러한 interval를 포함한다.

우리는 이 loop invariant를 다음으로서 상요한다:

Initialization: 첫 번째 반복 이전에, line 1은 x를 T의 root로 설정하고, 그 invariant는 유효하다.

Maintenance: 그 while loop의 매 반복은 line 4또는 line 5를 실행한다. 우리는 두 cases들이 loop invariant를 유지한다는 것을 보여줄 것이다.

$x.left == T.nil$ $x.left.max < i.low$ $x.left = T.nil$ $x.left$ $x.left \neq T.nil$ $x.left.max < i.low$ $i'$ 에 대해 우리는 다음을 갖는다

\begin{split} i'.high & \leq x.left. max \\ & < i.low \end{split}

$i'$ $i$ 는 겹치지 않는다. 따라서, x의 left subtree는 i와 겹치는 어떻나 구간을 포함하지 않아서, x를 x.right로 설정하는 것은 invariant를 유지한다.

$x.left$ $x.left.max \geq i.low$ $i'$ 를 포함해야 한다

\begin{split} i'.high & = x.left.max \\ & \geq i.low. \end{split}

$i'.high < i.low$ $i.high < i'.low$ $i''$ 이 다음이라는 것을 암시한다

\begin{split} i.high & < i'.low \\ & \leq i''.low. \end{split}

interval trichotomy에 의해, i와 i''는 겹치지 않는다. 우리는 x의 left subtree에 어떠한 interval이 i와 겹치거나 말거나, x를 x.left로 설정하는 것이 그 invariant를 유지한다고 결론을 내린다.

Termination: $x = T.nil$ $x = T.nil$ 를 반환하는 것은 올바르다.

따라서, INTERVAL-SEARCH procedure는 올바르게 작동한다.

chan blog

Post Lists

2020년 11월 22일 일요일