If you search for a node in a semi-splay tree, it's basically to push certain nodes closer to the root, to reduce future search operations.

My course also says that if you search for a node and the node is not in the semi-splay tree, you still have to perform semi-play on the search path in the tree.
But isn't that basically pushing nodes to the root that aren't actually have been searched for?

So my question would be : why do you still have to perform semi-splay even if the node you search for is not in the tree?


To complete the search process for an element $x$ that is not in the tree, you have to go all the way to a leaf node to confirm that $x$ is not in the tree. If you repeatedly search for such an element $x$, you have to splay on an unsuccessful search, otherwise the query time for $x$ could indefinitely remain as bad as $\Theta(n)$, even in an amortized sense.

  • $\begingroup$ Aah, i hadn't thought of that. Makes perfectly sense, thanks! $\endgroup$ – Aerus Jan 17 '11 at 16:58

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.