Scapegoat
-
[ Open Data Structures ] - ScapeGoat - 2DataStructure 2021. 1. 16. 14:14
ScapeGoat를 찾는데 있어서 사용했던 Lemma에 대한 증명으로 ScapeGoat는 마무리합니다. 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이 아닌 다음과 같은 부등식을 만족한다고 해봅니다. 그리고 임의의 node u에서 root node까지의 경로를 다음과 같이 표기하기로 합니다. r은 root node임과 동시에 u_{0}이고 u_{h}는 node u 그 자체입니다. L..