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?