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

이 챕터는 red black trees를 보강하여 우리가 구성하는 두 개의 자료구조를 이야기 한다. Section 14.1은 dynamic set에서 general order statistic operations을 지원하는 자료구조를 설명한다. 그러고나서, 우리는 그 set의 total ordering에서 주어진 element의 rank 또는 한 set에서 번째로 가장 작은 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

Chapter 9는 한 order statistic의 개념을 소개했었다. 구체적으로, 인 상황에서 개의 elements의 한 집합의 번째 order statistic은 번째로 가장 작은 key를 가진 집합에서의 element이다. 우리는 unordered set에서 에서 어떤 order statistic를 결정하는 방법을 보았었다. 이 섹션에서, time에 dynamic set에 대해 어떤 order statistic를 결정할 수 있도록 하기 위해 red-black trees를 수정하는 방법을 볼 것이다. 우리는 time에 한 element의 rank를 연산하는 방법을 또한 볼 것이다 - 이것은 set의 linear order에서의 position이다.

그림 14.1은 빠른 order-statistic operations을 지원할 수 있는 자료구조를 보여준다. order-statistic tree T는 각 node에 추가 정보가 저장된 red-black tree이다. 보통의 red-black tree attributes인 한 node x에서 x.key, x.color, x.p, x.left, 그리고 x.right외에도, 우리는 또 다른 attribute인 x.size를 갖는다. 이 특성은 x를 root로하는 subtree에서의 (internal) nodes의 개수를 포함한다 (x 그 자체를 포함해서), 즉 그 subtree의 크기. 만약 우리가 sentinel의 size를 0으로 정의한다면, 즉, 우리가 가 0으로 설정한다면 - 그러면 우리는 다음의 항등식을 갖는다

우리는 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

우리가 insertion과 deletion동안 이 size information을 유지하는 방법을 보여주기 전에, 이 부가 정보를 사용하는 두 개의 order-statistic queries의 구현을 봐보자. 우리는 주어진 rank로 한 element를 가져오는 한 연산으로 시작한다. 그 procedure 는 x를 root로 하는 subtree에서 i번째로 가장 작은 key를 포함하는 노드에 대한 포인터를 반환한다. order-statistic tree T에서 i번째로 가장 작은 key를 가진 node를 찾기 위해, 우리는 OS-SELECT(T.root,i)를 호출한다.

OS-SELECT의 line 1에서, 우리는 r를 연산한다. 이것은, x를 root로 하는 subtree내에서 node x의 rank이다. x.left.size의 값은 x를 root로하는 subtree의 inorder tree walk에서 x전에 나오는 nodes들의 개수이다. 따라서, 은 x를 root로 하는 subtree내에서의 x의 rank이다. 만약 이라면, 그러면 node x는 i번째로 가장 작은 element이고, 그래서 우리는 line 3에서 x를 반환한다. 만약 이라면, 그러면 i번째로 가장 작은 element는 x의 left subtree에 있고, 그래서 우리는 line 5에서 로 재귀한다. 만약 이라면, 그러면 i번째로 가장 작은 element는 x의 right subtree에 있다. x를 루트로 하는 subtree는 inorder tree walk에서 x의 right subtree전에 나오는 r개의 elements를 포함하기 때문에, x를 root로하는 subtree는 i번째로 가장 작은 element는 를 root로하는 subtree에서 번째로 가장 작은 element이다. Line 6은 이 element를 재귀로 결정한다.

OS-SELECT가 작동하는 방법을 보기 위해, 그림 14.1에서 order-statistic tree에 있는 17번째 smallest element에 대한 탐색을 고려해라. 우리는 x를 root로서 시작하는데, 그 key는 26이고, i = 17이다. 26의 left subtree size가 12이기 때문에, 그것의 rank는 13이다. 따라서, 우리는 rank 17의 노드는 26의 right subtree에서 번째 smallest element라는 것을 안다. 재귀 호출 이후에, x는 key 41를 가진 node이고 i = 4이다. 41의 left subtree의 size가 5이기 때문에, 그것의 subtree내에서 그것의 rank는 6이다. 따라서, 우리는 rank4를 가진 node가 41의 left subtree에 있는 4번째로 가장 작은 element라는 것을 안다. 그 재귀 함수 후에, x는 key 30를 가진 노드이고, 그것의 subtree내에서 rank는 2이다. 따라서, 우리는 key 38를 가진 node를 root로 하는 subtree에서 번째로 가장 작은 element를 찾기 위해 다시 한 번 재귀한다. 우리는 이제 그것의 left subtree가 size 1를 가진다는 것을 발견하는데, 그것이 두 번째로 가장 작은 element라는 것을 의미한다. 따라서, 그 procedure는 key 38를 가진 노드에 대한 포인터를 반환한다.

각 recursive call이 order-statistic tree에서 한 단계 아래로 내려가기 때문에, OS-SELECT에 대한 total time은 worst에서 tree의 높이에 비례한다. tree는 red-black tree이기 때문에, 그것의 높이는 이다. 여기에서 n은 노드들의 개수이다. 따라서, OS-SELECT의 running time은 n개의 elements의 dynamic set에 대해 이다.

Determining the rank of an element

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

그 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: 처음의 반복 이전에, line 1은 x를 root로 하는 subtree에서 r를 x.key의 rank로 설정한다. line 2에서 로 설정하는 것은 line 3에서 test가 실행하는 처음에 그 invariant를 true로 만든다.

Maintenanace: while loop의 매 반복의 끝에, 우리는 로 설정한다. 따라서, 우리는 만약 이 loop body의 시작 때 y를 root로 하는 subtree에서 의 rank라면, 그러면 loop body의 끝에서 y.p를 root로 하는 subtree에서 x.key의 rank를 보여주어야 한다. while loop의 매 반복에서, 우리는 y.p를 root로하는 subtree를 고려한다. 우리는 이미 inorder walk에서 x에 선행하는 node y를 root로 하는 subtree에서 nodes의 개수를 세었고, 그래서 우리는 inorder walk에서 x를 선택하는 y의 sibling을 root로하는 subtree의 노드들을 추가해야만 한다. 그리고 만약 y.p가 x를 또한 선행한다면 거기에 1를 더해주어야 한다. 만약 y가 left child라면, 그러면 y.p와 y.p의 right subtree에 있는 어떠한 노드들은 x를 선행하지 않는다. 그래서 우리는 r를 그대로 둔다. 만약 그렇지 않다면, y는 right child이고, y.p의 left subtree에 있는 모든 노드들은 x를 선행한다. y.p 자체도 그렇듯이. 따라서, line 5에서 우리는 r의 현재 값에 를 추가한다.

Termination: 일 때, 그 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 loop의 각 반복은 time이 걸리고, y는 매 반복마다 tree에서 한 level 위로 가기 때문에, OS-RANK의 running time은 worst에 tree의 높이와 비례한다: 즉, n개의 노드를 가진 order-statistic tree에서 이다.

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을 수행하는 것이다.

첫 번째 단계에서 subtree sizes를 유지하기 위해, 우리는 그 leaves를 따라 root에서 내려가는 탐색되는 simple path에서 각 노드 x에 대해 x.size를 증가시킨다. 그 추가된 새로운 노드는 1의 size를 가진다. 탐색된 경로에서 의 nodes들이 있기 때문에, 그 size attributes를 유지하는 추가 비용은 이다.

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

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

최대 두 개의 rotations이 red-black tree로의 insertion동안 수행되기 때문에, second phase에서 size attributes를 업데이트 하는데 오직 additional time이 소비된다. 따라서, 한 n-node order-statistic tree에 대한 insertion을 위한 총 시간은 이고, 이것은 보통의 red-black tree에 대한 asymptotically하게 같다.

red-black tree로부터의 Deletion은 또한 두 단계로 구성된다: 처음에 underlying search tree에 작동하고, 그 두 번째는 최대 세 번의 회전을 발생시키고, 그렇지 않다면 어떠한 구조적 변화를 수행하지 않는다. (See Section 13.4.) 그 첫 번 째 phase는 tree로부터 한 node y를 제거하거나, 그것을 tree내에서 위로 움직이게 한다. 그 subtree sizes를 업데이트하기 위해, 우리는 간단히 node y에서 root로 가는 simple path를 탐색하고, 그 경로에 있는 각 노드의 size attribute를 1개 줄인다. 이 경로는 n-node red-black tree에서 을 갖기 때문에, 그 첫 번째 pahse에서 size attributes를 유지하는데 쓰인 additional time은 이다. 우리는 insertion에서와 마찬가지로 같은 방식으로 deletion의 second phase에서 rotations을 처리한다. 따라서, insertion과 deletion둘 다, size attributes를 유지하는 것을 포함해서, n-node order-statistic tree에 대해 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의 그것들의 효율적인 지원으로부터 온다.

step 2에 대해, 우리는 size attribute를 추가했는데, 거기에서 각 node x는 x를 root로하는 subtree의 size를 저장한다. 일반적으로, 그 추가 정보는 operations을 더 효율적으로 만든다. 예르륻렁, 우리는 tree에서 저장된 keys를 사용하여 OS-SELECT와 OS-RANK를 구현할 수 있었지만, 그것들은 time에 작동하지 않을 것이다. 가끔씩, 추가 정보는 data라기 보다는 pointer information이다, Exercise 14.2-1에서 처럼.

step 3에 대해, 우리는 insertion과 deletion이 time에 여전히 작동하면서 size attributes를 유지할 수 있게 보장했었다. 이상적으로, 우리는 추가 정보를 유지하기 위해 자료구조의 몇 가지 elements만을 업데이트할 필요가 있따. 예를들어, 만약 우리가 tree에 각 node에서 그것의 rank를 간단하게 저장했다면, 그 OS-SELECT와 OS-RANK procedures는 빠르게 작동할 것이지만, 새로운 minimum element를 넣는 것은 그 tree의 모든 노드에 있는 정보를 바꾸도록 할 것이다. 우리가 subtree sizes를 대신 저장할 때, 새로운 element를 넣는 것은 오직 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)

가 n개의 nodes를 가진 red-black tree T를 보강하는 attribute라고 하고, 각 노드 x에 대한 f의 값이 nodes의 x, x.left, 그리고 x.right 정보만을 의존한다고 가정하자, x.left.f와 x.right.f도 포함하여. 그러고 나서, 우리는 T의 모든 노드들에 있는 f의 값을 유지할 수 있다, insertion과 deletion동안, asymptotically하게 이러한 연산들의 performance에 영향을 미치지 않고.

Proof 그 증명의 주된 아이디어는 node xdptjdml attribute에 대한 변화는 tree에서 x의 조상들에게만 전파된다는 것이다. 즉, x.f를 바꾸는 것은 x.p.f만 업데이트 되는 것을 요구한다; x.p.f를 업데이트 하는 것은 x.p.p.f만을 업데이트 하는 것을 요구할지도 모른다. 그리고 tree를 올라가면서 등등. 우리가 T.root.f를 업데이트 했다면, 어떤 다른 노드들도 그 새로운 값에 의존하지 않을 것이고, 그래서 그 프로세스는 종료된다. red-black tree의 높이는 이기 떄문에, 한 노드에 있는 attribute를 바꾸는 것은 그 변화에 의존하는 모든 노드들을 업데이트 하는데 time을 사용한다.

T에 한 node x를 넣는 것은 두 단계로 구성된다. (See Section 13.3.) 그 첫 번째 단계는 한 존재하는 노드 x.p의 자식으로서 x를 넣는다. 우리는 time에 x.f의 값을 연산할 수 있는데, 그것이 x 자체의 다른 attributes에 있는 정보와 x의 자식들의 정보에만 의존하지만, x의 자식들은 둘 다 sentinel 이라는 추정으로. 우리가 x.f를 연산했다면, 그 변화는 트리를 타고 위로 전파된다. 따라서, insertion의 첫 번째 단계에 대한 전체 시간은 이다. second phase동안, tree에 대한 유일한 구조적 변화는 rotations로부터 온다. 오직 두 개의 노드들만이 한 rotation에서 바뀌기 떄문에, f attributes를 업데이트하기 위한 전체 시간은 rotation당 이다. insertion동안 rotations의 개수는 최대 2이므로, insertion의 total time은 이다.

insertion처럼, deletion은 두 단계를 가진다. (See Section 13.4.) 그 첫 번째 단계에서, tree에 대한 변화는 deleted node가 tree에서 제거될 때 발생한다. 만약 그 제거된 노드가 그 때 두 자식을 가졌따면, 그러면 그것의 successor가 그 deleted node의 위치로 움직인다. 이러한 변화에 의해 발생한 f에 대한 업데이트를 전파하는 것은 최대 를 쓰게 되는데, 그 변화가 tree를 locally하게 수정하기 때문이다. second phase동안 red-black tree를 fixing up하는 것은 최대 3개의 rotations을 요구하고, 각 rotation은 f에 대한 updates를 전파하는데 최대 time을 요구한다. 따라서, insertion처럼, deletion을 위한 전체 시간은 이다.

order-statistic trees에서 size attributes를 유지하는 것 같은 많은 경우에, 회전 이후에 업데이트 하는 비용은 이다, Theorem 14.1의 증명에서 도출된 라기 보다. Exercise 14.2-3이 한 예시를 준다.

14.3 Interval trees

이 섹션에서, 우리는 intervals의 dynamic sets에 대한 operations을 지원하기 위해 red-black trees를 보강할 것이다. closed interval은 실수 의 한 순서가 있는 쌍인데, 이다. 그 구간 는 집합 를 나타낸다. 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를 유지하기 위한 효율적인 수단을 제공한다.

우리는 한 interval 를 한 object 로 나타낼 수 있고, (the low endpoint) 그리고 (the the high endpoint)를 가진 것으로 할 수 있다. 우리는 intervals 와 가 만약 라면 overlap (겹친다)고 말한다. 즉, 만약 이고 라면 말이다. 그림 14.3에서 보여주듯이, 어떤 두 개의 intervals 와 는 interval trichotomy를 만족한다. 즉, 다음의 세 개의 properties중의 하나가 유효하다는 것이다:

와 겹친다.
는 의 왼쪽에 있다. (즉, )
는 의 오른쪽에 있다. (즉, )
한 interval tree는 각 element가 한 interval 를 포함하는 elements의 한 dynamic set을 유지하는 red-black tree이다. Interval trees는 다음의 연산을 지원한다.

INTERVAL-INSERT(T,x)는 interval tree T에 element x를 넣는데, 그 attribute는 interval를 포함한다고 가정된다.

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

INTERVAL-SEARCH(T,i)는 interval tree T에서 가 interval 와 겹치는 element x에 대한 포인터를 반환하거나, 만약 그러한 element가 집합에 없다면 sentinel T.nil에 대한 포인터를 반환한다.

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

Step 1 : Underlying data structure

우리는 각 노드 x가 interval 를 포함하고 의 key가 그 interval의 인 low end point인 red-black tree를 선택한다. 따라서, 그 자료구조의 inorder tree walk는 low end point로 정렬된 순서로 intervals를 열거한다.

Step 2: Additional information

intervals 그 자체 외에도, 각 노드 x는 value 를 포함하는데, 이것은 x를 root로 하는 subtree에 저장된 interval endpoint의 maximum value이다.

Step 3: Maintaining the information

우리는 insertion과 deletion이 n개의 nodes를 가진 interval tree에 time이 걸리는지를 증명해야 한다. 우리는 interval 가 주어진다면 를 결정할 수 결정할 수 있고, node x의 children의 max values를 결정할 수 있다:

따라서 Theorem 14.1에 의해, insertion과 deletion은 time에 작동한다. 사실, 우리는 Exercise 14.2-3과 14.3-1에서 보여주듯이, time에 rotation이후에 max attributes를 업데이트할 수 있다.

Step 4: Developing new operations

우리가 필요한 그 유일한 새 연산은 INTERVAL-SEARCH(T,i)인데, 이것은 tree T에서 interval이 interval 와 겹치는 노드를 찾는 것이다. 만약 tree에서 와 겹치는 어떠한 interval이 없다면, 그 procedure는 sentinel T.nil에 대한 포인터를 반환한다.

i와 겹치는 interval에 대한 탐색은 tree의 root에서 x와 함꼐 시작하고, 아래로 진행한다. 그것은 겹치는 interval를 찾거나 sentinel T.nil에 대한 포인터를 찾을 때 종료된다. 그 기본 loop의 각 iteration이 time이 걸리고, n-node re-black tree의 높이는 이기 떄문에, INTERVAL-SEARCH procedure는 time이 걸린다.

우리가 INTERVAL-SEARCH가 왜 옳은지를 보기 이전에, 그림 14.4에서 interval tree에 대해 그것이 어떻게 작동하는지를 조사해보자. 우리가 interval 와 겹치는 한 interval를 찾고 싶다고 가정하자. 우리는 root로서 x와 함께 시작하고, 그것은 를 포함하고, i와 겹치지 않는다. 이 보다 더 크기 때문에, 그 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는 이 노드를 반환한다.

성공적이지 않은 탐색의 한 예시는, 우리가 그림 14.4의 interval tree에서 와 겹치는 interval를 찾고 싶다고 가정하자. 우리는 또 다시, root인 x와 시작한다. 그 root의 interval [16, 21]은 i와 겹치지 않고, 은 보다 더 크기 떄문에, 우리는 를 포함하는 노드쪽 왼쪽으로 간다. Interval [8,9]는 i와 겹치지 않고, 이 보다 더 작기 떄문에, 우리는 오른쪽으로 간다. (left subtree에서 어떠한 interval이 i와 겹치지 않는 것에 주목해라.) Interval [15, 23]은 와 겹치지 않고, 그것의 left child는 이다. 그래서 다시, 우리는 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를 반환한다.

Proof lines 2-5의 while loop는 이거나 가 와 겹칠 때 종료된다. 후자의 경우, 확실히 x를 반환하는 것이 올바르다. 그러므로, 우리는 전자의 케이스에 집중하다. 거기에서, 그 while loop는 이기 떄문에 종료된다.

우리는 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를 유지한다는 것을 보여줄 것이다.

만약 line 5가 실행된다면, 그러면 line 3에 있는 branch condition 때문에, 우리는 이거나 를 갖게된다. 만약 이라면, 를 root로 하는 subtree에는 명백히 i와 겹치는 어떠한 구간을 포함하지 않는다. 그래서 x를 x.right를 설정하는 것은 그 invariant를 유지한다. 그러므로, 이고 라고 가정해라. 그림 14.5(a)가 보여주듯이, x의 left subtree에 있는 각 interval 에 대해 우리는 다음을 갖는다

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

만약, 반면에, line 4가 실행된다면, 그러고나서 우리는 그 loop invariant의 contrapositive (명제에서 대우)가 유효하다는 것을 보여줄 것이다. 즉, 만약 를 root로 하는 subtree가 i와 겹치는 interval를 포함하지 않는다면, 그러면 tree의 어느 곳에서 어떤 interval과 i는 겹치지 않는다. line 4가 실행되었기 때문에, line 3에서 branch condition 때문에, 우리는 를 가지게 된다. 게다가, 그 max attribute의 정의에 의해, x의 left subtree는 다음의 조건을 만족하는 interval 를 포함해야 한다

(그림 14.5(b)는 그 상황을 보여준다.) i와 i'는 겹치지 않기 때문에, 그리고 가 아니기 떄문에, interval trichotomy에 따라 가 된다. Interval trees는 intervals의 low endpoints를 key로 하고, 따라서 search-tree property는 x의 right subtree에 있는 어떤 interval 이 다음이라는 것을 암시한다

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

Termination: 만약 loop가 일 때 끝난다면, 그러면 x를 root로 하는 subtree는 i와 겹치는 어떠한 interval를 포함하지 않는다. 그 loop invariant의 대우는 T가 i와 겹치는 어떠한 구간도 포함하지 않는 다는 것을 암시한다. 그러므로, 를 반환하는 것은 올바르다.

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

14 Augmenting Data Structures

댓글