Is a resultant red-black tree after insertion unique?

Question

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

Is the result of this addition, after rebalancing, unique?

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 offer no proof (and little confidence). I'm just wondering if someone more knowledgeable than myself might be so kind as to edify me?

Answer 1

They are not unique.

A simple proof would be to make a trivial algorithmic change, like check that we can change the root's colour, and provide a case where that 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 quite as easily yield

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

The root is a different colour but of course the trees are both still valid RB trees.

This may seem a little trivial, but you can extend the idea (if you want a proof that is less trivial) to check for more than just the root. You could check O(1) levels deep to make a non-trivial but valid change, which would generate two different algorithms with the same running times.

For example, check that the first 10 rows are full and black, and change the odd ones to red, would yield an additional constant work (i.e. O(1)), and a new algorithm.

I should note that this is simply a proof of non-uniqueness, not a bound on the amount of non-uniqueness. I.e. something trivial like this is enough to prove the point, but it leaves the door open for RB algorithms that differ in more fundamental ways.

Answer 2

No there are mutliple alorithms.

Let start with this 2 propositions:

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

Now, imagine there is a unique alorithm to add a node to a 4 internal node red-black Tree. Then there should be only 3 red-black Trees with 5 internal nodes, since the algorithm leads to one single result.

That's absurd as the number of red-black trees with 5 internal nodes is 8.

(cf PIGEONHOLE PRINCIPLE )

Therefore there are multiple "red-black" algorithm

Hope I understood what you meant.