Red Black Tree - max number of rotations needed for K insertions and K deletions?

Question

What's the maximum number of rotations required after K insertions and K deletions in a Red Black tree?

I'm thinking its 3K as in the worst case scenario for insertion we perform 2 rotations for every insertion and 1 rotation for every deletion. Am i on the right track here?

Answer 1

In contrast to AVL trees where rotations for deletions may propagate up to the root (although having at most one (double-)rotation for insert), RB trees require a constant (at most 2 for insert, at most 3 for deletion) number of rotations. What can take logarithmically much time during deletion in an RB tree is the recoloring which may propagate up to the root, which means insert and delete have the same asymptotics for both AVL and RB trees.

(If interested, you can find an analysis of these things in this script.)

Regarding your question, at most 3K is correct (but apparently rotations are counted a little differently from the linked script).