Analysis of Correctness and Running-Time

Understand the need of correctness and running time to implement scapegoat trees.

In this module, we analyze the correctness and amortized running time of operations on a ScapegoatTree.

Correctness

We first prove the correctness by showing that, when the add(x) operation results in a node that violates Condition (1 as discussed previously), then we can always find a scapegoat:

Lemma 1: Let uu be a node of depth h>log3/2\text{depth } h > \log_{3/2} q in a ScapegoatTree. Then there exists a node ww on the path from uu to the root such that.

size(w)size(parent(w))>2/3\frac{\text{size}(w)}{\text{size}(\text{parent}(w))} > 2/3

Proof: Suppose, for the sake of contradiction, that this is not the case, and

size(w)size(parent(w))2/3\frac{\text{size}(w)}{\text{size}(\text{parent}(w))} \leq 2/3

for all nodes ww on the path from uu to the root. Denote the path from the root to uu as rr = u0,...,uh=uu_0,...,u_{h} = u . Then, we have size(u0)=n,size(u1)23n,size(u2)49n\text{size}(u_{0} ) =n,\text{size}(u_{1}) \leq \frac{2}{3} n, \text{size} \left ( u_{2} \right ) \leq \frac{4}{9} n and, more generally,

size(ui)(23)in\text{size}(u_{i}) \leq \left ( \frac{2}{3} \right )^{i} n

But this gives a contradiction, since size(u)1\text{size}(u) \ge 1, hence

1size(u)(23)hn<(23)log3/2qn(23)log3/2nn=(1n)n=11 \leq \text{size}(u) \leq \left ( \frac{2}{3} \right )^{h} n < \left ( \frac{2}{3} \right )^{log_{3/2}q} n \le \left(\frac{2}{3}\right)^{\log_{3/2} n} n = \left ( \frac{1}{n} \right ) n=1

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy