Insane coincidence. Got an exam tomorrow and just found out this is going to be a topic. Kinda panicked coz I had no idea what the hell red and black trees were. Funny how you posted this EXACTLY when I needed it.
It can be better if you had used P, GP and uncle's example like done in insertion and what happens if P is red , clarify this case.. overall like it .. Thank you.
You are missing a crucial point in almost all videos, If root is red, simply recolor it to black. instead of saying that this is smaller part of bigger tree... you can do this at 3.46
The author's delete_fixup function considers your case -- at the end of type 2, moving x to its parent, then we go back to while's determine statements. Because now x is the root, so we circumvent and jump over the "while", set x(root)'s color to black.
Not covered in these cases is what happens if P is red. If it is then w is automatically black and has to be a real node not a leaf node (otherwise black path count is incorrect) => P becomes black, w becomes red and delete is over (as there is now an extra black in X path fixing deficiency). delete _fixup applies to the one case that is real work => when you delete a black node and it is a leaf node and not the root node. Also Red-Black deletion fixup is a 2-prong strategy. (i) You are looking a red node in Parent, Sibling, Siblings-Children. If you find one you can via rotation and/or recolouration get the red node and move as black node to the tree that lacks a black node, delete fixup over. Red Black delete requires a maximum of 3 rotations. (ii) But what happens if Parent, Sibling, Siblings-Children are all black? Then recolour the Sibling red and the Parent is now the new node to fix. You have effectively made both sides of the tree "bad " and you are closer to root. A new set of nodes are now Parent, Sibling, Siblings-Children. And what happens if you never encounter a Red node? You arrive at the root. Then the tree is now restored, the black path count decreases by 1. You have introduced a Red node in every path. Of course suppose you do (ii) 5 times before finding a red node. The algorithm does the minimum to restore before quitting on the 6th move upwards towards the root.
I think it would have been better for you to take a more abstract approach to teaching the topic like the old videos, and introduced the code afterwards. Especially the transplanting in the last episode. I think it would be easier to have understood if you said: "There are 3 cases for deletion, if the node you want to delete has a nill left child then replace it with its right child, if it has as nill right child then replace it with its left child, else replace it with the min in its right sub tree.", and then introduced how to actually code it.
quite helpful video but you explained case 2 wrongly. check last line of your code: you should paint last x to black after you exit from cycle, so 5 should be black and there won't be two adjacent red nodes.
My college professors should take tuition from you. Thankyou so much for these easy and short explanation videos
Insane coincidence. Got an exam tomorrow and just found out this is going to be a topic. Kinda panicked coz I had no idea what the hell red and black trees were. Funny how you posted this EXACTLY when I needed it.
boom!
Wooow lol. Same here. Where are you from? :)
lol sameeee. i have an exam in 10hours and he coincidently resumed his 5yr old playlist this week. damn
@@sequbeats Germany!
@@siddhantyadav450 Same, been binging his content
This is by far the best video on the internet to explain this in such a short amount of time !!!!!!!! THANK YOU SSOOOOOO MUCHHHH SIR ❤❤❤
Those tutorials are top notch. Thanks for uploading!
A multilevel-feedback-Queue rundown would be much appreciated!
It can be better if you had used P, GP and uncle's example like done in insertion and what happens if P is red , clarify this case..
overall like it ..
Thank you.
You are missing a crucial point in almost all videos, If root is red, simply recolor it to black.
instead of saying that this is smaller part of bigger tree... you can do this at 3.46
Exactly! I made many questions wrong.
@@DCM-fo3ve is this mistake made in insert videos also?
@@ReverseGuy Yes!
@@DCM-fo3ve nope, the insertion videos are correct
The author's delete_fixup function considers your case -- at the end of type 2, moving x to its parent, then we go back to while's determine statements. Because now x is the root, so we circumvent and jump over the "while", set x(root)'s color to black.
Not covered in these cases is what happens if P is red. If it is then w is automatically black and has to be a real node not a leaf node (otherwise black path count is incorrect) => P becomes black, w becomes red and delete is over (as there is now an extra black in X path fixing deficiency).
delete _fixup applies to the one case that is real work => when you delete a black node and it is a leaf node and not the root node.
Also Red-Black deletion fixup is a 2-prong strategy.
(i) You are looking a red node in Parent, Sibling, Siblings-Children. If you find one you can via rotation and/or recolouration get the red node and move as black node to the tree that lacks a black node, delete fixup over. Red Black delete requires a maximum of 3 rotations.
(ii) But what happens if Parent, Sibling, Siblings-Children are all black? Then recolour the Sibling red and the Parent is now the new node to fix. You have effectively made both sides of the tree "bad " and you are closer to root. A new set of nodes are now Parent, Sibling, Siblings-Children.
And what happens if you never encounter a Red node? You arrive at the root. Then the tree is now restored, the black path count decreases by 1. You have introduced a Red node in every path.
Of course suppose you do (ii) 5 times before finding a red node. The algorithm does the minimum to restore before quitting on the 6th move upwards towards the root.
it is covered dumb.as
So, we call the fix up only if the y's color is black, but what is y on the example from 1:03? Thanks
Can you do a explanation on AVL Tree
I think it would have been better for you to take a more abstract approach to teaching the topic like the old videos, and introduced the code afterwards. Especially the transplanting in the last episode. I think it would be easier to have understood if you said: "There are 3 cases for deletion, if the node you want to delete has a nill left child then replace it with its right child, if it has as nill right child then replace it with its left child, else replace it with the min in its right sub tree.", and then introduced how to actually code it.
respect. would have been better, if explained why we have that logic inside each case, i mean how are we supposed to remember that? whats the idea.
quite helpful video but you explained case 2 wrongly. check last line of your code: you should paint last x to black after you exit from cycle, so 5 should be black and there won't be two adjacent red nodes.
what if x or w is nil
then we blow up
So, th cod is incorrect? We really will get null pointer exception in fix up method?
@@yipyiphooray339