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 be a node of q in a ScapegoatTree
. Then
there exists a node on the path from to the root such that.
Proof: Suppose, for the sake of contradiction, that this is not the case, and
for all nodes on the path from to the root. Denote the path from the root to as = . Then, we have and, more generally,
But this gives a contradiction, since , hence
Create a free account to access the full course.
By signing up, you agree to Educative's Terms of Service and Privacy Policy