Can every valid red-black tree exist?

user_562769 0
Viewed 2544

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: enter image description here

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: enter image description here enter image description here

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!

red-black-tree
6 Answers

I am not sure the answer is yes and I will say why below. If it can be done at all, it will be necessary to insert more nodes than needed then delete other nodes.

You can delete arbitrary red leaf nodes and the tree will not change shape or recolour. You can insert arbitrary red leaf nodes under black parents at the base of the tree without the tree changing shape.

If you need to make one side of the tree more bushy, it is enough to insert nodes at that spot. That will cause recolouration further up the tree first then eventually a rebalancing.

The reason why I think it cannot be done, is deleting nodes that have 2-children, the way that is done is to swap the node with successor or predecessor node (either is valid), then delete the node where it has moved to. There is a choice of successor or predecessor and the trees resulting will be different. So you would need to control this aspect of deletion and to arrive at a certain tree, it might necessary to say "delete Node A use successor", now "delete Node B use predecessor"

user_19485250

The red black tree is decomposed into flexible red cache and invariant black support. In order to keep the black height invariant, you have to move the red cache to the top, so you can adjust the height. Roughly speaking, the red capacity can be easily moved without moving the real nodes. The red capacity must be constantly swapped out to the black tree top, which generates a global red waterfall.

The red capacity moves down, and the black branches move up.

user_171427380
Related