4
$\begingroup$

Splay trees offer armotized O(log n) access to tree elements. However, if you keep repeatedly appending elements to a splay tree, without splaying any other elements, it degrades into a linked list with O(n) access. Is there a way to avoid that? I have the idea of splaying a random element during an append, but will that do any help?

$\endgroup$
1
$\begingroup$

It's true that if you consider a long sequence of operation, it's possible to point at one operation and say "that one operation might take a really long time" (e.g., $O(n)$ time). That's in some sense the essence of amortized analysis. An amortized running time of $O(\log n)$ means that the average time per operation is $O(\log n)$, but it's still true that there might be a rare operation here and there that take much more (though it will be compensated by most operations taking less time). Amortized running time bounds are only useful if you're willing to accept that limitation.

If you want worst-case running time bounds, then don't use a data structure that only offers amortized worst-case bounds; use a different data structure, one that offers worst-case running time bounds. For instance, self-balancing binary search trees (like red-black trees, AVL trees, etc.) offer worst-case running time guarantees. If amortized running time bounds aren't good enough, maybe splay trees aren't the data structure for you.

$\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.