0:48 : This video is wrong straight away. Consider the case on the right. How can you have a parent that is red with a single black child? That immediately violates the black tree height for the red node. *A red node either has 0 black children or 2 black children* . *It cannot have 1 black child because to do so is a violation of black tree height* . In this case the left side has black height 1, the right side with no child has black height 0. If you add NULL black nodes all round, that means a left side with black height 2 and a right side with black height 1
@stephenhowe41074 жыл бұрын
0:18 How can v a RED node have a single black child node u? Path through v to the left child has +1 real black nodes. Path through v to the right child is 0 real black nodes. So the black path count differs. So this cannot be a Red Black Tree. All red nodes in Red Black Trees either have 0 black children or 2 black children. They cannot have 1 black child. Can a REd Black Tree have nodes with 1 child? Yes, but in every case they are a black node with a red child. No other colour combination is possible.
@balramSing3664 жыл бұрын
Yrr apna pic full screen pe ka rhe ho very irritating but nice explanation