Problem:
Suppose we relax the third invariant of red-black trees to the property that there are no three reds in a row. That is, if a node and its parent are both red, then both of its children must be black. Call these relaxed red-black trees. Which of the following statements is not true?
Solution:
(Option 1) There is a relaxed red-black tree that is not also a red-black tree.
This statement is true - red -left-> red -left-> black is such a tree
(Option 2) The height of every relaxed red-black tree with n nodes is $ O(\log{n}) $
This statement is true as well. Since there are no three red node in a row, the longest path can have at most 3 times more nodes, and everything else as the proof said proceed as usual.
(Option 3) Every red-black tree is also a relaxed red-black tree.
Yeah, this is almost by definition.
(Option 4) Every binary search tree can be turned into a relaxed red-black tree (via some coloring of the nodes as black or red).
Nope, this binary search tree cannot be turned into a relaxed red-black-tree through coloring
1 -right-> 2 -right-> 3
If we wanted to not violate rule 4 we have to color them all black, but then that violate violate rule 3.
As an aside, I just hate function asking about negation, except from tricking people that do no good at all.
Suppose we relax the third invariant of red-black trees to the property that there are no three reds in a row. That is, if a node and its parent are both red, then both of its children must be black. Call these relaxed red-black trees. Which of the following statements is not true?
Solution:
(Option 1) There is a relaxed red-black tree that is not also a red-black tree.
This statement is true - red -left-> red -left-> black is such a tree
(Option 2) The height of every relaxed red-black tree with n nodes is $ O(\log{n}) $
This statement is true as well. Since there are no three red node in a row, the longest path can have at most 3 times more nodes, and everything else as the proof said proceed as usual.
(Option 3) Every red-black tree is also a relaxed red-black tree.
Yeah, this is almost by definition.
(Option 4) Every binary search tree can be turned into a relaxed red-black tree (via some coloring of the nodes as black or red).
Nope, this binary search tree cannot be turned into a relaxed red-black-tree through coloring
1 -right-> 2 -right-> 3
If we wanted to not violate rule 4 we have to color them all black, but then that violate violate rule 3.
As an aside, I just hate function asking about negation, except from tricking people that do no good at all.
No comments:
Post a Comment