5
$\begingroup$

I am trying to construct a red black tree out of only black nodes. I know it is possible getting it after some deletions but I am trying to construct one only via insertion orders. Is it possible? I couldn't find a way to do so , so far even after trying to use the simulator.

*** exept of a root node being added to an empty tree.

| cite | improve this question | |
$\endgroup$
  • 1
    $\begingroup$ What have you tried? Have you tried working through some very small examples (say, exhaustively enumerating all possible insertion orders for trees of size 1, 2, and 3)? Have you tried to find a proof that it is impossible? Have you tried looking for suitable invariants that would imply it is impossible? $\endgroup$ – D.W.♦ Aug 20 '15 at 17:01
  • $\begingroup$ Hello and thank you for your comment. I have tried to do so. I couldn't find any invariants though. Can I assume it is impossible since we always insert a red node and thus an only black nodes tree is impossible to construst without a deletion after an insertion? The balancing menipulations taken on the nodes ( rotations and recoloring) don't allow that "only black" situtaion ( not reffering a single node tree). $\endgroup$ – user118972 Aug 20 '15 at 17:09
  • $\begingroup$ I am quite convinced after trying a lot of diferent insertions that it isn't possible but I can't find the invariant. $\endgroup$ – user118972 Aug 20 '15 at 17:19
  • $\begingroup$ Hints: 1) Can you quickly name a tree shape that allows you to color everything black? 2) Given any (balanced) target shape, what is a simple insertion order to obtain exactly that shape? $\endgroup$ – Raphael♦ Aug 20 '15 at 17:57
  • $\begingroup$ RBT have properties you must obey. Which of those could be violated? When? $\endgroup$ – Evil Aug 20 '15 at 18:12
3
$\begingroup$

Properties of Red Black Tree:

0) Every node is black or red. Ok, no problem.

1) Root is black. Ok, no problem.

2) All leaves (empty nodes) are black. Ok, no problem.

3) Every red node must have two black childs. Ok, no problem.

4) Every path from any node to leaf has equal number of black nodes. It seems problematic.

So now comes problems: When you insert element it's color is red. (In fact this not comes from properties but observation that adding red node does not violate $4$th rule, so it is easier to implement).

So for start you add one element, let me say 10. It is black root. Ok.

Now You add 13. It must be red, otherwise it violates rule 4.

Red Black Tree elements 10; 13

Now you add 19. Depending on implementation you can leave all black, or recolor.

Red Black Tree elements 10; 13; 19

Now adding 12 gives recoloring and comes red.

Red Black Tree elements 10; 13; 19; 12

And after several numbers

Red Black Tree elements 10; 13; 19; 12; 41; 43; 26; 10; 82

And now it starts nightmare, as you should propagate changes from one side of tree to another convincing somehow that you will change everything to black after insertion.

Basically I asked you about rules to obey, as it comes to mind that with $4$th can be fulfilled only in perfectly balanced trees.

So to answer your questions:

No you cannot with common implementations of RBT, but extending balance operation to recolor when it is possible - it does not violate rules, so it is possible. Also with extension that whenever there is $n = 2^k - 1$ nodes, restructure it to perfectly balanced tree and recolor everything to black, it would be also possible.

I did firstly answer "no" as purpose of balancing operation is to guarantee bound on worst case search / insert, and such extensions comes at price of time complexity. It does not violate rules, but is not implicitly implemented in standard RBT.

Given only root, you have it. Given three nodes inserted in order with implementation changing all to black (rather rare case and counterproductive), you can. But this is last one that is without deletions possible.

When you are about to insert element and want all tree to be black that would mean there is violated rule $4$ (so not possible) or you have to rebalance tree, which would recolor nodes, so it is not pure black anymore.

With deletions on the other hand ;)

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Well, for $n=2^k$ you can. :) $\endgroup$ – Raphael♦ Aug 21 '15 at 16:34
  • $\begingroup$ Well, not by only insertions ;) And recoloring is possible, but it needs traversing whole tree. Otherwise, if we implement such feature that perfectly balanced tree we switch all colors to black, then yes. But not for $n = 2^k$ as it must have one red node, but $n = 2^k -1$ $\endgroup$ – Evil Aug 21 '15 at 16:37
  • $\begingroup$ Right, wrong $n$. :D I understand the question to ask for the final tree being all black. Inserting the values in breadth-first order definitely gets the right shape; whether all nodes are black probably depends on the implementation (they all can be). $\endgroup$ – Raphael♦ Aug 21 '15 at 16:40
  • $\begingroup$ BFS is just level ordering, ok I am mixing two things one is impementation dependence - and one is recoloring. $n = 2^k - 1$ nodes and then it can be all black, but none existing implementation has it. $\endgroup$ – Evil Aug 21 '15 at 16:57

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.