[ Open Data Structures ] - ScapeGoat - 2

ScapeGoat를 찾는데 있어서 사용했던 Lemma에 대한 증명으로 ScapeGoat는 마무리합니다.

Figure 1.1

Figure 1.2

Lemma 1.  ScapeGoat Tree안에 있는 임의의 Node u가 Figure 1.2[Depth = h]를 만족한다면 u부터 root node까지 이르는 경로 상에 Figure 1.1을 만족하는 어떤 node w는 반드시 존재한다.

Proof ) 모순을 통해 증명하기 위해, 어떤 node u부터 root node까지의 경로 상의 모든 node w는 Figure 1이 아닌 다음과 같은 부등식을 만족한다고 해봅니다.

Figure 1.3

그리고 임의의 node u에서 root node까지의 경로를 다음과 같이 표기하기로 합니다.

Figure 1.4

r은 root node임과 동시에 u_{0}이고 u_{h}는 node u 그 자체입니다.

Lemma 2. ScapeGoat Tree에서 Addition Operation을 수행할 때, ScapeGoat node w를 찾고 w의 Subtree를 Rebuild하는 Time Cost는 O(size(w))이다. 

Proof ) 

마지막으로 남은 증명은 Rebuild를 m번 호출하는 Cost의 상한에 대한 것입니다.

Lemma 3. 크기가 0인 ScapeGoat Tree에 대한 m번의 Addition, Deletion, Operation은 Rebuild호출에 의한 O(mlog(m)) 의 time cost를 유발한다.

Proof )

이제 남은 것은 해당 cost가 정말 모든 Rebuild 작업을 수행할 만큼 충분하게 부여되었느냐, 입니다.

Complete Souce Code : HiddenWriter/UnbalancedBinarySearchTree at master (github.com)