I'm given a B-tree where the delete-operation is not implemented, but instead keys are deleted using tombstones (so they stay in the tree, but are marked as deleted). Now when at least 90% of all keys are tombstones and there are less than 400 active (so non-deleted) keys, the B-tree is completely replaced by a new one with just one top containing all the active keys.

The question is whether this structure still allows to perform all future operations (except the clean-up operation) in $O(log(n))$ time (with $n$ the amount of active keys in the tree).

I suspect that this isn't true because with this tree, it's possible to have very very much tombstones, and still more than 400 active keys (let's say 401 and 10 000 000 tombstones). But I'm not sure if my reasoning is correct. Can someone please verify this for me?

  • $\begingroup$ Yes, I think you're right, if you're not talking about amortized analysis, i.e., if you're referring to the time complexity of single operations. Of course the shape formed by the nodes with the active keys will likely not be anymore of a balanced tree, those the time complexity of the usual operations may change with respect to $n$ (which is not the "original" $n$). Now how it changes of course depends on the structure of the shape formed by the active nodes and thus by the deletion operations that you perform. $\endgroup$ – nbro Jan 5 '17 at 17:25

Your Answer

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

Browse other questions tagged or ask your own question.