0
$\begingroup$

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.

Greetings

$\endgroup$

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.