40
$\begingroup$

Let's assume the following definition of a red-black tree:

  1. It is a binary search tree.
  2. Each node is colored either red or black. The root is black.
  3. Two nodes connected by an edge cannot be red at the same time.
  4. Here should be a good definition of a NIL leaf, like on wiki. The NIL leaf is colored black.
  5. A path from the root to any NIL leaf contains the same number of black nodes.


Question

Suppose that you have implemented the insert and delete operations for the red-black tree. Now, if you are given a valid red-black tree, is there always a sequence of insert and delete operations that constructs it?


Motivation

This question is motivated by this question and by the discussion from this question.

Personally, I do believe that if you imagine a valid red-black tree consisting only of black nodes (which implies that you are imagining a perfectly balanced tree), there is a sequence of insert and delete operations that constructs it. However,

  1. I do not know how to accurately prove that
  2. I am also interested in the more general case
$\endgroup$
  • $\begingroup$ Your question sounds a bit circular... any set of insert and delete operations will construct a red-black tree... literally anything, since red-black is only a definition. Is your question limited to a purely black tree? $\endgroup$ – JOX Oct 29 '15 at 21:19
  • 2
    $\begingroup$ No, I think you misnderstand. Of course, any set of inserts and deletes constructs some red-black tree. The question is this: is any tree that fits the definition constructible by some sequence of inserts and deletes? If you are given some tree, can you recreate a sequence of inserts and deletes? $\endgroup$ – alisianoi Oct 30 '15 at 1:25
  • 2
    $\begingroup$ @all3fox Yes, you are right. There is an algorithm which uses the operation insert and delete to construct a valid red-black tree consisting only of black nodes. It uses $(h + 2) \cdot 2^h - 1$ insertions/deletions to create a tree of height $h$. First, we can create a perfectly balanced red-black tree in breadth-first manner using $2^{h+1} - 1$ insertions, then using $h * 2^{h-1}$ insertions and the same amount of deletions repaint it into a completely black tree. The trick here is to move up $h$ times the lowest red layer up the tree until it reaches the root. $\endgroup$ – Anton Trunov Dec 18 '15 at 16:01
  • 1
    $\begingroup$ @AntonTrunov thank you, I sort of understand that. How about the case of a general Red-Black Tree though? What do you think, is it possible to construct any given Red-Black Tree with insert and delete operations? $\endgroup$ – alisianoi Dec 18 '15 at 16:13
  • 2
    $\begingroup$ a) The answer will depend on the precise implementation of insert and delete; there may be several ways to do these operations. b) Since RB trees are essentially B-trees of order 4, one can look there for inspiration. The details may prove tricky since the mapping from RB to B (and/or backwards) is not unique. $\endgroup$ – Raphael Mar 24 '16 at 13:37
3
$\begingroup$

The insert and delete operations in a red-black tree include the balancing needed to maintain the red-black properties.

The problem with non(left- or right-) leaning red black trees is that there are multiple ways to restore the red-blackness after the basic delete or insert.
It is not the insert or the delete that transforms the tree, but the rebalancing and rotation that happens afterwards to preserve/restore the red blackness of the tree.

The basic description of the red-black tree does not prescribe which of the possible routes to take.
It may not be possible to figure out how to exactly reconstruct a given red black tree, because the rebalancing need not be deterministic.

This has been 'solved' with left-leaning red black trees.
There is only one way the balancing is done. So any given leaning red black tree can be reconstructed using inserts and deletes, because the rebalancing/rotations are done in a specific deterministic way.

This does not mean that left-leaning RB-trees are better or more efficient, what they gain on one hand by using deterministic balancing rules, they lose on the other by more complex balancing code.

As per @Anton's comment:
There is an algorithm which uses the operation insert and delete to construct a valid red-black tree consisting only of black nodes. It uses $(h+2)⋅2^{h}−1$ insertions/deletions to create a tree of height $h$. First, we can create a perfectly balanced red-black tree in breadth-first manner using $2^{h+1}−1$ insertions, then using $h∗2^{h-1}$ insertions and the same amount of deletions repaint it into a completely black tree. The trick here is to move up $h$ times the lowest red layer up the tree until it reaches the root.

I think a complete balancing algorithm like Day-Stout-Warren would be more efficient though.

$\endgroup$
  • 1
    $\begingroup$ Using the operations insert and delete from the CLRS book you can build a valid RB tree consisting only of black nodes. The trick is to insert more nodes than needed and then delete excessive ones. The algorithm will eliminate red nodes. $\endgroup$ – Anton Trunov May 1 '16 at 8:17
  • $\begingroup$ @AntonTrunov, do you have a link for that algorithm, it would be nice to include it in the answer. I can't find it using my google-fu. $\endgroup$ – Johan May 1 '16 at 9:56
  • 1
    $\begingroup$ Unfortunately I don't have a link. I tried to answer the question at the time, and came up with an algorithm for the special case of all black RB trees. I sort of described it in that comment, but didn't provide a proof. $\endgroup$ – Anton Trunov May 1 '16 at 10:09
  • $\begingroup$ What do you mean by "This has been 'solved' with left-leaning red black trees.". Even a left-leaning red black tree have multiple ways of storing the same items. $\endgroup$ – user239558 Jul 19 '18 at 22:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.