Is the resulting red-black wood unique after insertion?

Question

Suppose I have a binary search tree that initially satisfies all red-black conditions and contains one node for every integer s in some set S. Then I want a new node; say a (which is not in S ).

Is the result of this addition unique after rebalancing?

Put another way: is there only one way to rebalance a red-black tree after inserting a node?

I believe that they are not unique, although I do not offer any evidence (and not enough confidence). I'm just wondering if anyone more knowledgeable than me can be so kind as to edify me?

Answer 1

They are not unique.

A simple proof would be to make a trivial algorithmic change, for example, to verify that we can change the root color and provide a case where this is still valid, for example:

1-B / \ 0-R 2-R 

add(3):

  1-B / \ 0-B 2-B \ 3-R 

But the new algorithm could easily get

  1-R / \ 0-B 2-B \ 3-R 

The root is a different color, but of course the trees are still valid RB trees.

This may seem a little trivial, but you can expand on the idea (if you need proof that is less trivial) to test more than just the root. You can check the O (1) level deeply to make a non-trivial but real change that would create two different algorithms with the same runtime.

For example, check that the first 10 lines are filled and black, and changing the odd lines with red will give additional permanent work (i.e. O (1)) and a new algorithm.

It should be noted that this is simply a proof of non-uniqueness, and not an estimate of the amount of non-uniqueness. That is, something trivial, as it’s enough to prove the point, but it leaves the door open for RB algorithms that differ in more fundamental ways.

Answer 2

There are no mutual alorithms.

Let's start with these two sentences:

• The number of red-black trees with 4 internal nodes - 3
• The number of red-black trees with 5 internal nodes 8

Now imagine that there is a unique algorithm to add a node to the 4 inner nodes of red-black trees. Then there should be only 3 red-black trees with 5 internal nodes, since the algorithm leads to one result.

This is absurd, because the number of red-black trees with 5 internal nodes is 8.

(cf PIGEONHOLE PRINCIPLE )

Therefore, there are several "red-black" algorithms

I hope I understand what you mean.