1
$\begingroup$

Is there an analysis of red-black trees using amortized analysis? I saw it mentioned somewhere as an example of amortized analysis but all the proofs that I know use a global approach ("black height") to demonstrate the O(log n) runtime of individual operations.

| cite | improve this question | | | | |
$\endgroup$
1
$\begingroup$

You may need to look at this report: https://www.cs.princeton.edu/~fiebrink/423/AmortizedAnalysisExplained_Fiebrink.pdf

Each individual operation takes $O(\log n)$ but when you apply amortized analysis to a sequence of operations, you get something interesting.

Directly from this report: "However, amortized analysis can be used to show that any sequence of $m$ insert and delete operations causes $O(m)$ structural modifications in the worst case (Cormen et al. p.428). It can similarly be shown that the total time for $m$ consecutive insertions in a tree of $n$ nodes is $O(n + m)$ (Tarjan 1985)."

| cite | improve this answer | | | | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.