Max. number of rotations while inserting a new element into n-element red black tree

Question

What is the maximum number of rotations while inserting a new element into n-element Red Black Tree?

If I'm correct, insertion that does not violate rules of RBT requries maximum of 2 rotations (2 cases). Assuming that's it, is O(1) also a correct answer?

If that's right, confirm it and please tell me, what requires maximum of 3 rotations?

Nikunj Banka · Accepted Answer · 2014-04-24T18:06:41.793

0

A maximum of 3 operations(or 2 rotations) are needed when implementing a Red-Black Tree correctly. For example the central BST shown in this image will need 3 operations to make it confirm to the Red Black BST's rules.

Image to show a case when 3 operations are needed

_{Image taken from Robert Sedgewick's slides from this MOOC.}.

edited Apr 24 '14 at 18:06

answered Mar 21 '14 at 12:55

Nikunj Banka

11,117
16
74
112

Max. number of rotations while inserting a new element into n-element red black tree

1 Answers1