Let's assume the following definition of a red-black tree:
- It is a binary search tree.
- Each node is colored either red or black. The root is black.
- Two nodes connected by an edge cannot be red at the same time.
- Here should be a good definition of a NIL leaf, like on wiki. The NIL leaf is colored black.
- A path from the root to any NIL leaf contains the same number of black nodes.
Suppose that you have implemented the
delete operations for the red-black tree. Now, if you are given a valid red-black tree, is there always a sequence of
delete operations that constructs it?
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
delete operations that constructs it. However,
- I do not know how to accurately prove that
- I am also interested in the more general case