CODEWITHSUNDEEP
red-black-tree
Martin Thoma
Martin Thoma

Reputation: 136635

Can every valid red-black tree exist?

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

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.

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!

Upvotes: 13

Views: 3060

Answers (6)

SJHowe
SJHowe

Reputation: 776

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"

Upvotes: 0

cheeseandtomato
cheeseandtomato

Reputation: 25

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.

Upvotes: -1

amdn
amdn

Reputation: 11582

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.

Upvotes: 5

Patrick M
Patrick M

Reputation: 10989

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.

Upvotes: 4

Kishor Sharma
Kishor Sharma

Reputation: 599

if a tree follow these 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.

It will be a balanced binary tree and can be called red-black tree.

Red-Black tree insertion and deletion have special condition and rules. If tree as in your example follow the algorithm of RB tree insertion and deletion, it will always be a RB tree. During insertion and deletion, an unbalanced binary tree will always restored to a balanced tree by changing node color, Rotating node or branch.

Upvotes: 2

gmlime
gmlime

Reputation: 1017

I think the branch of math that deals with that type of problem is graph theory, and looking into some graph theory papers that verify properities of red black and other balanced trees, I'm led to this paper: http://www.math.unipd.it/~baldan/Papers/Soft-copy-pdf/cosmicah05.pdf and http://www.math.unipd.it/~baldan/Papers/Soft-copy-pdf/cosmicah05.pdf and this paper http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.87.1161&rep=rep1&type=pdf , they should be able to answer your queries on the abstract properties. Or at least help you phrase your question in a way that leads to even better resources.

Upvotes: 3

Related Questions