I need help by understanding a theorem and its proof from a script. It says "There is a sequence of $n$ insert and delete operations in a (2,3)-tree that require $\Omega ($n log n$)$ many split and merge operations."

I actually have no idea how such a sequence looks like. I have tried to perform some insert and delete operations on a (2,3)-tree and I got different results on split and merge operations but I think there is a "special" sequence to maximize the split and merge operations.

I would be very grateful if someone can help me with this issue, so I can try to see how the proof of the theorem can be done.



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.