Analysis of Correctness and Running-Time

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

We'll cover the following

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