4:04 : _The promoted child is colored black if p was black_ If p was black? How can p not be black? If p was red, what color is the child? If child is red, that is a red-red violation. If the child is black, then it means that p violates the black color depth. The only way it can not violate it is if p had 0 or 2 children. It cannot have 1 child that is black (because left and right child black depth is not the same for p). Nor can you have a black node with a single black child. I keep seeing this "node with 1 child" issue with red-black deletion. If that occurs, the node is black and the child red, period. There is no other possibility as it violates the red-black tree rules. Basically in a Red-Black tree, a node can be 0 children - Black Node 0 children - Red Node 1 child - Black Node, Red child
This is melting my brain right now... Gonna have to watch this a few times... Or I just give up and stick with AVL trees :P So much simpler (to me): there is only one kind of restructuring: rotation (with left and right variants). And there is only one situation when you need to do it: imbalance. Restructuring can cause a chain reaction, but it just bubbles up, and is pretty easy to implement.
Double black case 1 needs to cover more cases I cant seem to solve with the information provided: 1 - What happens when x y and z do not form a line ? (you mention labelling a b c from left to right but this does not make sense in this case) 2 - On the case shown, what difference there is to the relabelling of x y z to a b c from a normal right rotation at y ? 3 - What happens when both children of y are red ? 4 - What happens when z and x are red ? In this case, the transformation you mention leads to z being the red parent of two red nodes, would it then be fixed by just recoloring ? ...
They count as nodes when verifying the black depth property. Suppose a highly skewed tree in which every node only have one left child(except the bottom one) and the nodes are colored b,r,b,r... and so on. If you ignore those nil children, you would think that there is only one path down to the bottom thus this is a valid RBTree, which actually is not.
It seems like the double black comes whenever a black is deleted. To compensate for the missing black, it seems we are using a double black node. Geez, I know - 5 months later; but I'm trying to get a grasp of this myself and was going through the comments to try and see if it's just me struggling... but yeah; that's my understanding of a double black and how it's mentioned in the video above! cheers!
would it be more efficient to take the next in-order successor when a node to be deleted has two children?? That way, the node to be deleted is switched to a leaf and is then deleted rather than having to repeat deletion over and over until the last level is reached. Also: we don't always end up in case 2, sometimes we still have two children in the end, so there is not internal node left with which to replace the node to be deleted. I don't think this works at all then......
_would it be more efficient to take the next in-order successor when a node to be deleted has two children??_ Yes. That is the normal way to delete nodes with 2 children for *ANY* binary search tree. Note 1: Either the next in-order successor or predecessor will do and in deleting the designated node, the order is preserved. And this swap node will always be a node with 0 or 1 children. Note 2: In swapping the nodes, the node values are swapped but not node properties. So for Red-Black trees the colours are not swapped. For AVL trees the height differences are not swapped.
I have watched all the 3 videos related to it.. Thank you very much. Now i finally understand everything very clearly
This is the best Red Black tree explantion I ever saw thank u very much sir
: )
this is the best explanation I've come across, thank you!!
The best explanation I've ever seen. Thx :):)
Best explanation of RBT so far. Thank you very much, im sharing this to my social media :))
4:04 : _The promoted child is colored black if p was black_
If p was black? How can p not be black?
If p was red, what color is the child? If child is red, that is a red-red violation. If the child is black, then it means that p violates the black color depth. The only way it can not violate it is if p had 0 or 2 children. It cannot have 1 child that is black (because left and right child black depth is not the same for p). Nor can you have a black node with a single black child.
I keep seeing this "node with 1 child" issue with red-black deletion.
If that occurs, the node is black and the child red, period.
There is no other possibility as it violates the red-black tree rules.
Basically in a Red-Black tree, a node can be
0 children - Black Node
0 children - Red Node
1 child - Black Node, Red child
instablaster...
This is melting my brain right now... Gonna have to watch this a few times...
Or I just give up and stick with AVL trees :P So much simpler (to me): there is only one kind of restructuring: rotation (with left and right variants). And there is only one situation when you need to do it: imbalance. Restructuring can cause a chain reaction, but it just bubbles up, and is pretty easy to implement.
6:20 : Interchange the entries of p and r BUT the colour of each node at the positions does not change, just the nodes.
Double black case 1 needs to cover more cases I cant seem to solve with the information provided:
1 - What happens when x y and z do not form a line ? (you mention labelling a b c from left to right but this does not make sense in this case)
2 - On the case shown, what difference there is to the relabelling of x y z to a b c from a normal right rotation at y ?
3 - What happens when both children of y are red ?
4 - What happens when z and x are red ? In this case, the transformation you mention leads to z being the red parent of two red nodes, would it then be fixed by just recoloring ? ...
Thanks man you the boss!!!!! Totally understood everything
Your videos are great, thanks for making them
Thank you so much!!
Do you now understand it?
thank you very much for making this video very helpful ❤❤❤❤❤❤❤❤❤❤❤❤❤❤💕💕💕💕💕💕💕💕💕💕😘😘😘😘
i have a question, at 9:56, what if y has a right child being red you wouldn't be able to do a rotation
Nice and simple explanation
good stuff sir!
Excellent explanation, thank you!
The little black squares confuse me, are they supposed to represent nodes that just aren't defined, a lack of a node, or a potential node?
They count as nodes when verifying the black depth property. Suppose a highly skewed tree in which every node only have one left child(except the bottom one) and the nodes are colored b,r,b,r... and so on. If you ignore those nil children, you would think that there is only one path down to the bottom thus this is a valid RBTree, which actually is not.
They are null (ie. currNode.next == null). It just means you are at a leaf node
how do you know when to put a double black?
It seems like the double black comes whenever a black is deleted. To compensate for the missing black, it seems we are using a double black node. Geez, I know - 5 months later; but I'm trying to get a grasp of this myself and was going through the comments to try and see if it's just me struggling... but yeah; that's my understanding of a double black and how it's mentioned in the video above! cheers!
would it be more efficient to take the next in-order successor when a node to be deleted has two children?? That way, the node to be deleted is switched to a leaf and is then deleted rather than having to repeat deletion over and over until the last level is reached.
Also: we don't always end up in case 2, sometimes we still have two children in the end, so there is not internal node left with which to replace the node to be deleted. I don't think this works at all then......
_would it be more efficient to take the next in-order successor when a node to be deleted has two children??_
Yes. That is the normal way to delete nodes with 2 children for *ANY* binary search tree.
Note 1: Either the next in-order successor or predecessor will do and in deleting the designated node, the order is preserved. And this swap node will always be a node with 0 or 1 children.
Note 2: In swapping the nodes, the node values are swapped but not node properties. So for Red-Black trees the colours are not swapped. For AVL trees the height differences are not swapped.