insert_rebalance in red-black tree

Question

insert_rebalance in rb_tree needs two rotates mostly?

I don't think so!

" 1 " is the newest insert node. It is Case 1:current node is red, father is red, uncle is red.

So we set father'color as black, uncle's color as black, father's father's color as red, and set father's father as the current node, and continue to go.

After the above operations, it is case 1 again.

Let's imagine: if it is always becomes to be case 1, the numbers of rotate will not just 2, maybe more.

My above statements are right? I want to confirm my thinking.

Answer 1

If the insert location is random then two rotates is fairly unusual.

Starting from 0 nodes:

B (0% need two rotates)

b r (25% need two rotates)

b r r (0% need two rotates)

b b b r (20% need two rotates)

b b b r r (0% need two rotates)

At the steps where two rotates is possible it is also possible to fill in the tree without requiring a second rotate. If the insert location is always the maximum rather than random then then the number of two-rotate inserts is 0, but you will rotate once about 50% of the time.