Red-black trees in 6 minutes — Delete Fixes

Examples of delete fixes, used after deleting nodes from a red-black tree.

[ttv]

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.

[raashid_]

My college professors should take tuition from you. Thankyou so much for these easy and short explanation videos

[Ari-pqdb]

This is by far the best video on the internet to explain this in such a short amount of time THANK YOU MUCHHHH SIR ❤❤❤

[flower]

Those tutorials are top notch. Thanks for uploading!

[thecoconutkid]

A multilevel-feedback-Queue rundown would be much appreciated!

[ramiltaghiyev]

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

[Souravjaiswal-jw]

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.

[ShubhamShrikantBawner]

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

[stephenhowe]

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.

[michealnestor]

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.

[dinesh.p]

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.

[TorpedOvrn]

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.