Can every valid red-black tree exist?

Question

Suppose you have a red-black tree that is a valid binary search tree and does not violate any of those rules:

• A node is either red or black.
• The root is black.
• All leaves (NIL) are black.
• Both children of every red node are black.
• Every simple path from a given node to any of its descendant leaves contains the same number of black nodes.

Such an red-black tree looks like this:

Does every possible tree that meets these restrictions have a sequence of insertions and deletions so that the red-black tree is generated?

_{I am asking this question, because I think about writing a blog article about red-black-trees and I would like to give some examples.}

If you want to test a counter-example: Here is a red-black tree implementation in python with an implemented function to generate the image.

To clarify the question: We make a game.

• I draw a red-black tree, that meets all the restrictions.
• You have to find a sequence of insertions and deletions, so that you end up with my red black tree.

Can I draw a red-black tree so that you can't win?

The colors are important! If the tree has a different shape or different colors, it is not the same red-black tree.

You should at least know how to generate these two red-black-trees:

Note that this is only a check for you if it could work. If you only know how to get these two red-black trees, you can't answer this question!

Answer 1

I believe inserting the nodes in breadth-first (level-order) traversal will yield any red-black tree.

http://en.wikipedia.org/wiki/Tree_traversal#Queue-based_level_order_traversal

Because you insert them in level order you can't have a tree that is less balanced than the original tree. No deletions are necessary, and no rotations are needed during insertion. In your example you should insert them in the following order:

13,8,17,1,11,15,25,6,22,27

Edit: While this will generate a binary search tree with the proper values and shape this may not generate the proper colors... it depends on the implementation of the insert function. The reason is the definition of red-black trees allow for variations in the color of nodes when the tree has more than one node and is full and all leaves are at the same depth - following Wikipedia's definition this is a "perfect" binary tree:

http://en.wikipedia.org/wiki/Binary_tree#Types_of_binary_trees

Suppose the tree has three nodes with values {1,2,3} where "2" is the root and is, by definition, black. Nodes {1,3} could be either both black or both red without violating the red-black rules. So a perfectly valid implementation of a red-black insertion could detect when the tree is "perfect" and color every node black. Such an implementation would prevent ever being able to construct a tree that, for example, alternates black and red at each level.

Edit 2: Given that both red-black trees are possible inputs (all three nodes black, and nodes 1 and 3 red) this settles the question about whether deletions are needed, if there is a solution then deletions are necessary. The question in my mind now is whether there is only one way to implement a red-black tree insertion/deletion. If there is more than one, and if they yield different trees, then the player of the game would have to understand the implementation in order specify the order of insertions and deletions to construct a given red-black tree. I don't know enough about the implementation of red-black trees to answer the question of whether there is only one way to implement them or whether there is more than one.

Answer 2

I think what you're asking for here is a formal proof of whether or not any arbitrary, legitimate red-black tree can be constructed by a series of insertions and deletions provided the tree is rebalanced after each operation. I'm not going to attempt such a proof, but I think I have an idea for how you could construct such a proof.

I would exhaustively cover all possible sub trees involving all legal permutations around single node and prove that it can be constructed. So:

• black node
  • no parent
    • left child null
      • right child null
      • right child not null
    • left child not null
      • right child null
      • right child not null
  • is the left child
    • same as above
  • is the right child
    • same as above
• red node (can't have no parent)
  • is the left child
    • same as above
  • is the right child
    • same as above

And then you have to create an inductive step showing that any arbitrary tree is a permutation of the cases shown above. It seems pretty straight forward, when I put it that way, but like I mentioned in my comment, I'm way too rusty to tackle the actual proof.