Thanks dude. I've got to be honest - I didnt put much expectations on this channel, but omg I am amazed of how amazing your explanations are. Everything is very clear and detailed. Appreciate your lecture, job awesomely done.
"Double Black Node" basically means the node is carrying a "hole". If, say for example, the black path count is 10, you delete a black leaf node, then the black path count is 9 up to that deleted node. The strategy of delete is rotate a red node from the sibling side of the tree, turn it black and restore the the black path count to 10. And if that cannot be done because all nodes are black on the sibling side, then a red node is introduced in every path of tree as you work your way to the root, and so the black path count reduces to 9 in all paths and it is again a red-black tree.
I was searching for the red black node delete everywhere! Could not find anything useful and finally I saw your video. Really helped a lot. Thanks and Keep posting more videos! :)
1:53 - 3:41 first case: we delete black 30, copy the smallest number of the bigger successors on the right (which has 1 or 0 not null ptrs, meaning less than 2 children (1 or 0)) in place of 30, that is 35. then we go down to the source red 35 (red nodes are simply deleted attaching null). 3:42 - 5:28 second case: we delete black 30, copy the smallest number of the bigger successors which are on the right side of the node to be deleted (which has 1 or 0 not null ptrs, meaning less than 2 children (1 or 0)) in place of 30, that is 35 to copy. then we go down to source black 35 (this time it is black and has a red successor). So delete the source black 35, put red successor on its place and make it black.) 6:10 there are 6 cases to delete a double black node. 6:17 - 8:25 explanation of what double black node is 8:26 - 9:35 how 6 cases of deletion work (they are applied one by one from 1 to 6 up to one of the terminal cases: 1, 4, 6) 9:35 - 11:57 double black case 4 (easiest, change color only) 12:00 - 15:10 double black case 6 (before left rotation grandparent and left child can be any color, after L-rotation left child goes to left side and becomes right child of any color.) One question: how can S become any color if it should be black after transformation. 15:11 -17:54 double black case 3 results in case 1: deletion leads to creating a double black node which becomes black, the left child changes color to RED. This colorflip pushes the double black node to go up and become root and the situation transforms into case 1, where the double black root becomes just black. 17:55 - 22:31 case 3 results in case 5: unlike the previous case double black node goes up but this time it is not root and we have case 5, which is about the LtoR rotation-dragging and changing color. Finally after rotation it is not the terminal case and we face the case 6 (22:31 - 24:31). 24:32 Deletion of the node leads to case 2, which starts in 25:00. 25:54 we make a LtoR rotation (drag from right to left) and change color of the nodes. The transformation leads to case 4, where we simply change colors (27:48). 28:38 summary 30:30 code
Tushar!! I was reading stuff in French and English everywhere on the net, but your examples are the best ones out there. It's clear, as simple as possible and straight to the point. Good vibe to you RBT teacher ;)
I simply love your work, thank you. You do it much better than Jason Galbraith. Keep the great work! You are inspiring me to learn more about algorithmic stuff.
@@sethueapen7013 : _Galbraith is a god_ Really? Here is Jason Galbraith's video on Red-Black deletion: th-cam.com/video/BIflee1rLDY/w-d-xo.html Explain to me how a Red node can have only 1 Black child and satisfy the Red-Black tree rules? Red nodes can only 0 or 2 Black children, they cannot have 1 because if they do, it immediately violates the black path count being the same. If the Left child is black, then the Right child being NULL, is 1-short on the black path count. That means that "Galbraith the god" has got it wrong. You *can* have Nodes with 1 child, but if you do, there is only one colour combination possible that satisfies the Red-Black tree rules: A Black node with a Red child. No other colour combination is possible. Here on TH-cam, I have seen countless explanations of Red-Black Tree deletion, and the moment the presenter says for the 1 child case, "either node can be Red", they have immediately revealed they don't know what they are talking about. They have not really understood the rules of Red-Black trees. There is an additional optimisation that can be done for the 2-child case and no one, bar me, talks about that. And hardly anyone has intuitive understanding of what the Red-Black deletion strategy amounts to. The Wiki explanation order can be optimised. Tushar Roy is to be commended as he gets things right.
@@sethueapen7013 I'm genuinely baffled as to how anyone can defend Galbraith's work. His video is a clear demonstration of incompetence. Anyone with a basic understanding of Red-Black Trees would know he's misleading his audience with incorrect information. It's almost laughable. Tushar Roy, however, is leagues ahead of anyone else on this platform. He's not just a presenter; he's an algorithm guru. The difference in quality is so stark, it's like comparing a master chef with someone who can't even boil water correctly. Frankly, anyone defending Galbraith after watching his misguided content is either ignorant or has a misplaced sense of loyalty. We're here to learn, not be fed lies. Maybe Galbraith should enroll in one of Tushar Roy's tutorials before embarrassing himself further. It's a shame TH-cam doesn't have a quality check for content like this.
i searched many text books and also in google, no where there is clear explanation, the notations are completely different, explnations are something and diagrams are something,from 3 days i tried in ppts and pdfs then i went for vedios , after seeing this vedio i could understand the deletion in RBT. till now never i kept comment for any vedio or anything, today i kept the comment as the vedio is very good. Thank u tushar
case 5 => P should be whatever color to actually cover all cases. Other than that thanks for the great video, the only one on TH-cam that correctly explains deletion!
Why must case 2 be done between between case 1 and case 3 ? I don't think it needs to be. I am wondering if this is taken off Wiki Red-Black tree deletion algorithm where I have raised the same issue. Basically Red-Black deletion is a 2-prong algorithm. There is a tight loop of case 1 and 3. And it amounts to "While parent, sibling and siblings children are all black, change the sibling to red and move up 1-level to the parent and loop on that, terminating if the root node is encountered". Nothing about case 1 and case 3 causes the case of 2 to be formed . Case 2 looks like case 3 but observe with case 3, the next loop round will start with the parent node. So it is not case 2. I mentioned this is a 2-prong algorithm. Cases 2, 4, 5 & 6 deal with the aftermath of finding a red node among the parent, sibling or sibling's children (the 2nd prong). In essence with rotations or color changes , the red node is used to plug the black hole on the other side of the tree. Some of the cases continue with another case but after a few steps they all halt completely. I dislike the term "double black node". Really it is hole. It is absence of a black node. The hole is pushed up 1-level at a time towards the root as long as parent, sibling and siblings children are all black. If the root is encountered, the problem is over in that you have decreased the black height of the tree uniformly by 1. case 3 introduces a red node in every path.
Yes. The parent node can be any colour but on left rotation it now becomes black. But the important point is whatever the old parent colour is , the sibling (which is now the new parent after rotation), that is now the colour of the old parent. So old parent is Red => new Parent is now Red, old Parent is now Black So old Parent is Black => new Parent is now Black, old Parent is now Black
First of all your videos are really good. Thanks a lot for the effort. My question is which case would you apply to delete 58 from the below tree and what would be the solution after deletion: 60B / \ 55R 90B / \ / \ 45B 58B 75R 120R \ 50R
In case 6 i feel after transformation x shud be made black, not keep same colour.. Coz if red then, the black count from it will be affected. Correct me if wrong
No you are wrong. In case 6 , the parent and sibling swap colours. Therefore the black count change through these nodes is zero. Since x is below these 2 nodes, whatever its colour, it is kept, to preserve the black colour zero sum. The original N node is double black. But after the rotation, an extra black is introduced by P. The old head of this system is purple and does not change colour (despite the fact that it is now a different node after rotation). Therefore case 6 is an ending situation and everything finally balances, the double black is converted into a single black (either a real black node or null).
Correct me if I'm wrong but you don't seem to point out what is the color of the replaced node. Ex, if we remove an inner black node by a red node, will it be red or black? If we replace an inner red node by a black node, will it be red or black? You seem to use the wording "delete the node 32" (which is a inner node in one of your examples) but I guess that you mean that we delete only the value and just replace the value by the successor's value? Or is it a deleted node replaced by a successor node that will be recolored the same color of the deleted node?
hi tushar, can u tell me that i have a doubt , can double-black node have null sibling ? because we always work on sibling if we found double-black node , what happened if we found sibling is null ?
_can u tell me that i have a doubt , can double-black node have null sibling?_ No because if that was true the tree breaks the black count in every path. When you deleted the black node, it was a real black node (before it became double black), therefore its sibling has to be real as well (because if it was not, the black path count to the sibling is 1 less than the n node). So the situation cannot happen. if it did => the tree is not a red-black tree, it is broken to start with, it is not obeying the rules. What can happen is the siblings children may be null (but if they are, recall that null nodes are black).
can you fix the problem case 6 but Node N is the right child not the left child and subTree with the Root S is the left child, y also the right red child of S? There is no fix in 6 cases ?
When black node with two black child is encountered ,i.e. the inorder-successor is black node with two black child , and we go on to delete it, we will get a double black node which will be a leaf node?Not while recursion but while entering a double black case it has to be a leaf ?Am I right ?Just want to be sure
No. The inorder successor will be a node (not necessarily black) with 0 or 1 child. Same with predecessor. The inorder successor is the left most node downwards of the right child. This has 3 cases: It is Black with a Red child (easy case to delete) It is Red with no child (easy case to delete) It is Black with no child (hard case to delete). It is this case that Tushar spends his most time on.
In case 5, since the path PSX has 2 black nodes (not counting the NULL nodes), and the path PSY has 3 black nodes, is it actually possible to get that case? Unless I'm wrong thinking that those rectangles are NULL nodes?
Yes it is possible but not on the 1st step. The 1st time round, y is a NULL node. It has to be otherwise the black path count to y is 1 greater before n is deleted. But if y is a null node, it is regarded as black. x being red exists but does not affect the black path count. Now recall there is case 3 which pushes the double black up one level (it is a loop). So if you had case 3 followed by case 5, now y could be real. But in this case the old n is further below somewhere (deleted) and its parent is now the new n node.
Quick question man. In this, i.imgur.com/RxjgVDx.jpg if 60 is deleted, I end up with a red red violation. 60's marked for deletion, it's a case 3 (black parent, sibling, and siblings kids), I recolor 94 to red and go again on 84. 84 is the exact same, case 3 (black parent, sibling, and siblings kids), I recolor 84 to red and go again on 72 (root). I hit case 1 and stop. But now I have a red red violation. What's wrong?
After you recolor 94 and go on 84, it become a mirror of case 3 (all cases except case 1 have mirrors, so there should be 11 cases), so you then recolor 37 to red, and root 72 stays the same.
I have written down the Red-Black trees insertion and deletion in a PDF format as explained by Tushar Roy. check that link for downloading: drive.google.com/file/d/1BbQAoMEpy-UxOJB1tFDsSRFLFkCpyzd-/view?usp=sharing
Today I have read the code about delete in the back tree on algs4.cs.princeton.edu/33balanced/RedBlackBST.java.html I am confused about the function delete, because it does not detect the situation from these 6 cases you have showed in the video.But make sure to change the key deleted to be red.
@@haili9296 : The java code you showed is for maintaining left-leaning red-black trees, Robert Sedgewick champions these. The code is smaller than a regular delete. What Robert does not state, is that left-leaning red-black will doing a lot more colour changes and rotations to maintain the additional left-leaning property. For Tushar's algorithm, standard Red-black delete, there is a maximum of O(log N) + 2 colour changes + max of 3 rotations.
@@XXX1234ABC : Initially the black node deleted is null and double black. But suppose this node is quite far from the root and its parent, sibling and siblings children are all black. Then case 3 applies, the sibling becomes red, and the parent is now considered the new working node. This is double black and non-null. It is possible to have an entire tree all black nodes (if symmetric) and it is a red-black tree. Case 3 basically says "I cannot solve the double black on this side of the tree (no red nodes). But if I make the sibling red, the problem is now on both sides of the tree and the parent is now the new double black node". And basically if you keep not finding red nodes, case 3 keeps applying until you encounter the root. And if you encounter the root, the tree is now red-black. The moment you encounter a red node, cases 2, 4, 5 & 6 apply and then deletion halts shortly after that.
In the video you explained that for case 5 the parent should be black which is wrong, the parent can be red or black. I had to struggle for 2 days straight because of this until I checked your code on github. Please fix this in the video. Thanks
I assume you get confused about case number 5. If yes, you need to notice that the parent can be any color (either red or black) because after rotation, the color of x is black, and whatever the parent's color will not violate the properties.
Yes you can. In fact you can have a Red-Black tree consisting entirely of Black nodes providing it is symmetric. So A B C with all nodes black is Red-black is a case 3 if you delete B. C's children are NULL nodes but they are regard as black and so it is case 3. If the tree was bigger and you repeated case 3 more than once deleting a leaf node, then the 2nd, 3rd, 4th etc case 3 will have real sibling nodes.
Thanks dude. I've got to be honest - I didnt put much expectations on this channel, but omg I am amazed of how amazing your explanations are. Everything is very clear and detailed. Appreciate your lecture, job awesomely done.
I never understood the concept of "Double Black Node"clearly. But after watching this video I realized its significance. Thank you.
welcome
bullshit !
"Double Black Node" basically means the node is carrying a "hole". If, say for example, the black path count is 10, you delete a black leaf node, then the black path count is 9 up to that deleted node. The strategy of delete is rotate a red node from the sibling side of the tree, turn it black and restore the the black path count to 10.
And if that cannot be done because all nodes are black on the sibling side, then a red node is introduced in every path of tree as you work your way to the root, and so the black path count reduces to 9 in all paths and it is again a red-black tree.
Trying to implement a red black tree in C++ and I'm pulling my hair out
son u need python
@@vikrant4666 It's hard no matter which language.
I implemented it in python.
@@gomes8335 share the code please
thank you
Jon Deaton and we were asked to use only c
This is the best RBT deletion video from all the others I've seen. Great job and go Seahawks!
I was searching for the red black node delete everywhere! Could not find anything useful and finally I saw your video. Really helped a lot. Thanks and Keep posting more videos! :)
I made it to minute 2:58, had an epiphany, went back to my code, and solved my bug. Seriously, it was that clear. Thank you! I owe you one, mate. ;)
Great explanation, very clear. One mistake though, in case 5 P should be purple.
Exactly! Wish I had read this, would have saved me some headaches
Thanks! :)
Exactly.
Thanks
Thanks! I found that one situation in case 2 doesn't fall into any other case. With your correction, everything became covered.
1:53 - 3:41 first case: we delete black 30, copy the smallest number of the bigger successors on the right (which has 1 or 0 not null ptrs, meaning less than 2 children (1 or 0)) in place of 30, that is 35.
then we go down to the source red 35 (red nodes are simply deleted attaching null).
3:42 - 5:28 second case: we delete black 30, copy the smallest number of the bigger successors which are on the right side of the node to be deleted (which has 1 or 0 not null ptrs, meaning less than 2 children (1 or 0)) in place of 30, that is 35 to copy.
then we go down to source black 35 (this time it is black and has a red successor). So delete the source black 35, put red successor on its place and make it black.)
6:10 there are 6 cases to delete a double black node.
6:17 - 8:25 explanation of what double black node is
8:26 - 9:35 how 6 cases of deletion work (they are applied one by one from 1 to 6 up to one of the terminal cases: 1, 4, 6)
9:35 - 11:57 double black case 4 (easiest, change color only)
12:00 - 15:10 double black case 6 (before left rotation grandparent and left child can be any color, after L-rotation left child goes to left side and becomes right child of any color.) One question: how can S become any color if it should be black after transformation.
15:11 -17:54 double black case 3 results in case 1: deletion leads to creating a double black node which becomes black, the left child changes color to RED. This colorflip pushes the double black node to go up and become root and the situation transforms into case 1, where the double black root becomes just black.
17:55 - 22:31 case 3 results in case 5: unlike the previous case double black node goes up but this time it is not root and we have case 5, which is about the LtoR rotation-dragging and changing color. Finally after rotation it is not the terminal case and we face the case 6 (22:31 - 24:31).
24:32 Deletion of the node leads to case 2, which starts in 25:00. 25:54 we make a LtoR rotation (drag from right to left) and change color of the nodes. The transformation leads to case 4, where we simply change colors (27:48).
28:38 summary
30:30 code
Tushar!! I was reading stuff in French and English everywhere on the net, but your examples are the best ones out there. It's clear, as simple as possible and straight to the point. Good vibe to you RBT teacher ;)
I simply love your work, thank you. You do it much better than Jason Galbraith. Keep the great work! You are inspiring me to learn more about algorithmic stuff.
You're wrong. Galbraith is a god.
@@sethueapen7013 : _Galbraith is a god_
Really? Here is Jason Galbraith's video on Red-Black deletion:
th-cam.com/video/BIflee1rLDY/w-d-xo.html
Explain to me how a Red node can have only 1 Black child and satisfy the Red-Black tree rules?
Red nodes can only 0 or 2 Black children, they cannot have 1 because if they do, it immediately violates the black path count being the same.
If the Left child is black, then the Right child being NULL, is 1-short on the black path count.
That means that "Galbraith the god" has got it wrong.
You *can* have Nodes with 1 child, but if you do, there is only one colour combination possible that satisfies the Red-Black tree rules:
A Black node with a Red child. No other colour combination is possible.
Here on TH-cam, I have seen countless explanations of Red-Black Tree deletion, and the moment the presenter says for the 1 child case, "either node can be Red", they have immediately revealed they don't know what they are talking about. They have not really understood the rules of Red-Black trees.
There is an additional optimisation that can be done for the 2-child case and no one, bar me, talks about that.
And hardly anyone has intuitive understanding of what the Red-Black deletion strategy amounts to.
The Wiki explanation order can be optimised.
Tushar Roy is to be commended as he gets things right.
@@sethueapen7013
I'm genuinely baffled as to how anyone can defend Galbraith's work. His video is a clear demonstration of incompetence. Anyone with a basic understanding of Red-Black Trees would know he's misleading his audience with incorrect information. It's almost laughable.
Tushar Roy, however, is leagues ahead of anyone else on this platform. He's not just a presenter; he's an algorithm guru. The difference in quality is so stark, it's like comparing a master chef with someone who can't even boil water correctly.
Frankly, anyone defending Galbraith after watching his misguided content is either ignorant or has a misplaced sense of loyalty. We're here to learn, not be fed lies. Maybe Galbraith should enroll in one of Tushar Roy's tutorials before embarrassing himself further. It's a shame TH-cam doesn't have a quality check for content like this.
Thank you Sir, for clearing my doubt before exam night. Continue this type of work.
welcome
i searched many text books and also in google, no where there is clear explanation, the notations are completely different, explnations are something and diagrams are something,from 3 days i tried in ppts and pdfs then i went for vedios , after seeing this vedio i could understand the deletion in RBT. till now never i kept comment for any vedio or anything, today i kept the comment as the vedio is very good. Thank u tushar
Kudos. You manage to explain a complex topic really well and comprehensibly!
Great! I am very much impressed how you explained deletion process. Its beautiful learning. Thanks a lot mate.
As always ..clean,correct and to the point ......thank u very much
Case 5: parent can be of any color.
I have an exam today, this video helped the most
case 5 => P should be whatever color to actually cover all cases.
Other than that thanks for the great video, the only one on TH-cam that correctly explains deletion!
yes you are right, found out during testing
This was an awesome explanation, it really helped me understanding well! Thank you very much for your effort and sharing!
Awesome tutorial, man. Keep up the good work!
In case 5 parent can be both red and black, not just black.
Great explanation of a very complex data structure. I'm trying to understand this to become a better programmer, so thanks for the tutorial!
as always clear explanation!! great work
Thank you so much, very complete and clear explanation
You made it very smooth and easy to learn. Thank you sir. 😊
you're welcome, my pleasure
Why must case 2 be done between between case 1 and case 3 ? I don't think it needs to be. I am wondering if this is taken off Wiki Red-Black tree deletion algorithm where I have raised the same issue.
Basically Red-Black deletion is a 2-prong algorithm. There is a tight loop of case 1 and 3. And it amounts to "While parent, sibling and siblings children are all black, change the sibling to red and move up 1-level to the parent and loop on that, terminating if the root node is encountered". Nothing about case 1 and case 3 causes the case of 2 to be formed . Case 2 looks like case 3 but observe with case 3, the next loop round will start with the parent node. So it is not case 2. I mentioned this is a 2-prong algorithm. Cases 2, 4, 5 & 6 deal with the aftermath of finding a red node among the parent, sibling or sibling's children (the 2nd prong). In essence with rotations or color changes , the red node is used to plug the black hole on the other side of the tree. Some of the cases continue with another case but after a few steps they all halt completely.
I dislike the term "double black node". Really it is hole. It is absence of a black node. The hole is pushed up 1-level at a time towards the root as long as parent, sibling and siblings children are all black. If the root is encountered, the problem is over in that you have decreased the black height of the tree uniformly by 1. case 3 introduces a red node in every path.
Helped a lot while implementing them in JS. Thanks!
at 14:14 you said it doesn't matter what color 10 is it becomes black. So if that color was red it becomes black?
Yes. The parent node can be any colour but on left rotation it now becomes black.
But the important point is whatever the old parent colour is , the sibling (which is now the new parent after rotation), that is now the colour of the old parent.
So old parent is Red => new Parent is now Red, old Parent is now Black
So old Parent is Black => new Parent is now Black, old Parent is now Black
Good explanation, thank you! Your video helped visualize process of deletion.
very great explanation, clear, you have make this difficult one easy brother..
First of all your videos are really good. Thanks a lot for the effort.
My question is which case would you apply to delete 58 from the below tree and what would be the solution after deletion:
60B
/ \
55R 90B
/ \ / \
45B 58B 75R 120R
\
50R
It seems like one case he didnt mention but 5 would work with upper one left red
so in case 5 the upper one should be just black or red instead black only
You are insanely good! Thank you so much :)
Thank you so much. You made it so much easier to understand!
you're welcome, my pleasure
Thank you, its so helpful and necessary.....
But i think it would have taken a lot of time to you also to prepare this😉
the case (P=red, N=double black, x=red, y=black) does not seem to be included in the 6 cases above.
It is case 5. There is a mistake in the diagram. P is purple which means it can be either red or black. And afterwards it is the same colour.
left rotation or right rotation ?
which rotation we need to perform in the cases in which we are performing rotation .
These explanations are very clear thank u!!!
Great explanation sir very clear u madr my day
What to do if there is DB on right side of tree??
Missed this one
In case 6 i feel after transformation x shud be made black, not keep same colour.. Coz if red then, the black count from it will be affected. Correct me if wrong
No you are wrong. In case 6 , the parent and sibling swap colours. Therefore the black count change through these nodes is zero. Since x is below these 2 nodes, whatever its colour, it is kept, to preserve the black colour zero sum.
The original N node is double black. But after the rotation, an extra black is introduced by P. The old head of this system is purple and does not change colour (despite the fact that it is now a different node after rotation). Therefore case 6 is an ending situation and everything finally balances, the double black is converted into a single black (either a real black node or null).
Allert! In case 5 parent can be both red and black, not just black. Accept this awesome - works right
you are wrong in counting height of black node , we dont count root node for black height
i believe he is counting the nil node not the root
you can count or not, that depends on your convention.
yup, #tushar is right
tushar is also right, why bcoz root node is always black, therefore height increase by 1 for every subtree.
We do count the root node. People vary as to whether nil nodes (conventionally black) of leaf nodes are counted. I don't.
Correct me if I'm wrong but you don't seem to point out what is the color of the replaced node. Ex, if we remove an inner black node by a red node, will it be red or black? If we replace an inner red node by a black node, will it be red or black? You seem to use the wording "delete the node 32" (which is a inner node in one of your examples) but I guess that you mean that we delete only the value and just replace the value by the successor's value? Or is it a deleted node replaced by a successor node that will be recolored the same color of the deleted node?
+Tushar Roy k, thanks for the clarification :)
hi tushar, can u tell me that i have a doubt , can double-black node have null sibling ? because we always work on sibling if we found double-black node , what happened if we found sibling is null ?
_can u tell me that i have a doubt , can double-black node have null sibling?_
No because if that was true the tree breaks the black count in every path.
When you deleted the black node, it was a real black node (before it became double black), therefore its sibling has to be real as well (because if it was not, the black path count to the sibling is 1 less than the n node).
So the situation cannot happen. if it did => the tree is not a red-black tree, it is broken to start with, it is not obeying the rules. What can happen is the siblings children may be null (but if they are, recall that null nodes are black).
You Indians! You know what to do! Greatings from Turkey!
what will be happened when deleted node is double-black but it's sibling is null?????????? pl reply I am stuck herer...
can you fix the problem case 6 but Node N is the right child not the left child and subTree with the Root S is the left child, y also the right red child of S? There is no fix in 6 cases ?
🙏🏻😭😭🙏🏻THANKS A LOT SIR
When black node with two black child is encountered ,i.e. the inorder-successor is black node with two black child , and we go on to delete it, we will get a double black node which will be a leaf node?Not while recursion but while entering a double black case it has to be a leaf ?Am I right ?Just want to be sure
No. The inorder successor will be a node (not necessarily black) with 0 or 1 child. Same with predecessor.
The inorder successor is the left most node downwards of the right child.
This has 3 cases:
It is Black with a Red child (easy case to delete)
It is Red with no child (easy case to delete)
It is Black with no child (hard case to delete). It is this case that Tushar spends his most time on.
Very Clear Explaination Sir Thanks :)
In case 5, since the path PSX has 2 black nodes (not counting the NULL nodes), and the path PSY has 3 black nodes, is it actually possible to get that case? Unless I'm wrong thinking that those rectangles are NULL nodes?
Yes it is possible but not on the 1st step. The 1st time round, y is a NULL node. It has to be otherwise the black path count to y is 1 greater before n is deleted. But if y is a null node, it is regarded as black. x being red exists but does not affect the black path count.
Now recall there is case 3 which pushes the double black up one level (it is a loop).
So if you had case 3 followed by case 5, now y could be real. But in this case the old n is further below somewhere (deleted) and its parent is now the new n node.
What does 0 not null means, does it mean 2 null children ?
Do we also add the null in counting the black height????????
okk thnx for very early response..... *****
Thanks a lot Tushar!!!
you're welcome
Hey dude your videos are awesome.
Please can you do a series on tries data structure?
It will help us alot in the interviews
no
thanks very much.I really want to know how to concluded this six cases
Quick question man. In this, i.imgur.com/RxjgVDx.jpg if 60 is deleted, I end up with a red red violation. 60's marked for deletion, it's a case 3 (black parent, sibling, and siblings kids), I recolor 94 to red and go again on 84. 84 is the exact same, case 3 (black parent, sibling, and siblings kids), I recolor 84 to red and go again on 72 (root). I hit case 1 and stop. But now I have a red red violation. What's wrong?
After you recolor 94 and go on 84, it become a mirror of case 3 (all cases except case 1 have mirrors, so there should be 11 cases), so you then recolor 37 to red, and root 72 stays the same.
I have written down the Red-Black trees insertion and deletion in a PDF format as explained by Tushar Roy. check that link for downloading: drive.google.com/file/d/1BbQAoMEpy-UxOJB1tFDsSRFLFkCpyzd-/view?usp=sharing
Great video, explains it well
Is this a 2-3 or 4 B red black tree? PS: It is 4B tree, never mind :D
Thank you Tushar!
Thanks this was a great explanation
Can I just write one algorithms that I do not need to detect the situation to solve all the six situations???
Today I have read the code about delete in the back tree on algs4.cs.princeton.edu/33balanced/RedBlackBST.java.html
I am confused about the function delete, because it does not detect the situation from these 6 cases you have showed in the video.But make sure to change the key deleted to be red.
@@haili9296 : The java code you showed is for maintaining left-leaning red-black trees, Robert Sedgewick champions these. The code is smaller than a regular delete. What Robert does not state, is that left-leaning red-black will doing a lot more colour changes and rotations to maintain the additional left-leaning property.
For Tushar's algorithm, standard Red-black delete, there is a maximum of O(log N) + 2 colour changes + max of 3 rotations.
grt very nice :)
I tried by books and got confused :P now this solved all
what if the node to be deleted is RED but has one Black child?
+S. S This case is not possible as it violates the condition of red black tree.
Hats off! It's Amazing what you do!
thanks. work at apple.
@@tusharroy2525 He meant to say what you do (teaching on TH-cam ) is awesome😂
how can the double black node you created have child null nodes??
null nodes are considered at black node.
i also dont get it. isnt double black nodes null already?
@@XXX1234ABC : Initially the black node deleted is null and double black.
But suppose this node is quite far from the root and its parent, sibling and siblings children are all black. Then case 3 applies, the sibling becomes red, and the parent is now considered the new working node. This is double black and non-null. It is possible to have an entire tree all black nodes (if symmetric) and it is a red-black tree. Case 3 basically says "I cannot solve the double black on this side of the tree (no red nodes). But if I make the sibling red, the problem is now on both sides of the tree and the parent is now the new double black node".
And basically if you keep not finding red nodes, case 3 keeps applying until you encounter the root. And if you encounter the root, the tree is now red-black.
The moment you encounter a red node, cases 2, 4, 5 & 6 apply and then deletion halts shortly after that.
The best explanation!
nic vedio....relly helpfull...very well explained.. :)
thanks
great explanation. thanks
In the video you explained that for case 5 the parent should be black which is wrong, the parent can be red or black. I had to struggle for 2 days straight because of this until I checked your code on github. Please fix this in the video. Thanks
이 사람 발음 진짜 잘들려 ㅋㅋ 뭔가 콩글리쉬 같네
Introduction 😲
😂😂Red Blaack treee😂
Great work......Thanks alot
This Top-down method?
tushar can u upload vedio of m-way tree
Great video! Thanks
I actually love you dude!
you dont even know him
What if parent is red and x is red , rest all are black. You didnt consider this case sir.
Two red nodes cannot be adjacent。
@@yxyize they are not adjacent
After case 5 you always need to apply case 6. Am i right?
That's correct.
what if p is red, x is red and y is black?
I assume you get confused about case number 5. If yes, you need to notice that the parent can be any color (either red or black) because after rotation, the color of x is black, and whatever the parent's color will not violate the properties.
I think that case 3 is impossible, cause, no matter how you implement, you cant have all black nodes for case 3 implementation.. pls explain
Yes you can. In fact you can have a Red-Black tree consisting entirely of Black nodes providing it is symmetric.
So
A
B C
with all nodes black is Red-black is a case 3 if you delete B. C's children are NULL nodes but they are regard as black and so it is case 3. If the tree was bigger and you repeated case 3 more than once deleting a leaf node, then the 2nd, 3rd, 4th etc case 3 will have real sibling nodes.
i know this video gonna be amazing when i looked into his eyes :' )
Your videos are awesome but your mic sucks :) learnt a lot from you .. I really admire your efforts
gracias mi buen amigo indú
SALVOU MINHA VIDA PRA CARALHO!!! HAHAHAHA THANKS! :)
👍👍👍💯💯💯
For better results read cormen after this video then again watch this video.
3:00 thoo null nodes
well explained
really gooood!!!!
sir, please make a video on interval tree
no
You are a god man, thanks
great explain！！！
joss
Thank you :)
Thanks a lot!
please add Tutorial of Heap Sort Asap !
you're a saint
sir u make the simple topic tough ..... plz explain in a systematic way
thank you so much ...