Red-black trees in 5 minutes — Insertions (strategy)

Great explanation ..Thank you so much ..

😉🙏

Great explanation! Help me much.

why do you perform any of these operations when the tree remains balanced.

Holy shit i'm so dumb

Best video series to understand red black tree

I don't like how you left out the subtrees, which you could have included a small triangle in the illustration so that the audience knows that something's there; that way we know that a red node is not a leaf node.

In case 1 the structure is a triangle, does that characteristic matter? Because in case 2 it mattered.

But why at the end of case 2 are there two red nodes aside ?

The doctor at the university explained it in an hour and I did not understand it. you are here. you explained it in a few minutes and I understood everything from you. Thank you very much.

Thank you for the video! Could you consider posting AVL tree when you have time? thank you!

I feel how you present case 2 and 3 is confusing. It sounds like they are independent, i.e. if (case 2), else (case 3). However, after handling case 2, case 3 definitely will occur. So it's more like you should handle case 2 if it applies, but case 3 is required anyway if uncle is red.

thank you Michael~

If this would have explained with numbers it would be more clear.

Another banger, awesome job man😊

Thank you for the video, you were really clear and pointed out solid points when rotating a node!
Sad to see you stopped uploading videos!

For those who are struggling with the pseudocode:--
0.The RBFixup algorithm only starts when z's parent is red, then case 1,2,3 follows. KEEP TRACKING THE VALUE OF Z.
1. The value of z changes whenever case 1 and case 2 occurs.
2. Recoloring process takes place only when case 1 and case 3 occurs.

Can make video on rb tree deletion in 4 minutes please

Thanks a lot bro for charming explanation 😊😊😊

Uncle 😂

crisp and clear explanation. super . Great effort. thanks

Plz make vedio on deletion sir

Awesomee Explaination! Thankssss Alottt brother

"As you can see C is Z's uncle" great video but you might have chosen better names for the nodes

For python students, what property would "T.nil" be in the pseudo?

I thought red node cannot have a red node as a parent or a child?

You should Red-Black Tree Delete
That is more complex. Inserts always occur at leaf nodes but Deletes can occur at any part of the tree.
Also Inserts have a maximum of 2 rotations, Deletes have a maximum of 3 rotations but both may recolour to the root in repairing.
Having found the node in the tree => count the children: 0, 1 or 2
Deal with the simple cases first.
If the number of children is 0 and the node is red => delete the node, black path count still constant, you are done.
If the number of children is 1 => then node must be black and child red, no other combinations are valid => delete the node and replace it with the child, the child becomes black. Black path count still constant, you are done.
If the number of children is 2 => you need to find the immediate successor or immediate predecessor node.
Immediate successor => look at right child and now follow its children leftwards as far down as you can go.
Immediate predecessor => look at left child and now follow its children rightwards as far down as you can go.
I would recommend finding the Immediate successor and then seeing if it is cheap to delete (above two cases)
If not find the Immediate predecessor and then seeing if it is cheap to delete (above two cases)
And if not pick one of them.
Swap the node you really want to delete with immediate predecessor or immediate successor, BUT DO NOT swap the colours. Now you have reduce the problem to deleting a node with 0 or 1 children and when deleted, the tree will still be ordered correctly. If it is an easy case => delete it.
So what is left to do?
The hard case: Deleting a leaf node, no children and it is black.
You delete it but now the black path tree is in violation.
And basically you work your way towards to root, 1-level at a time.
Intuitively speaking, restoring the delete situation is a 2-prong stategy:
(i) You look at a nodes siblings and your parent. You are looking for red-nodes that that can be rotated or recoloured in such a way that the black path count is restored on your side of the tree while maintaining the black path count on the siblings side of the tree. If you can do that => it is over.
(ii) at the same time, you might find that parent, sibling and siblings children are all black => so what do you do?
You recolour the sibling as red and retry repairing the tree at parent level, the problem has moved up 1-level
So what happens if you encounter the root, no red nodes encountered (which is possible, it is a Red-Black tree)?
Then it is a red black tree. You have introduced a red node in every path by (ii). At the same time, you have reduced the black path count by 1 in every path.

I think you are missing 2 things
1. Any insertion will always occur at leaf nodes. Apart from the first node where it will become the root, this new node will have a parent whose left or right child where inserting is a nil pointer.
2. If the node you just inserted (which is red) has a black parent => no further repair is necessary, it is still a red-black tree.
Otherwise we move onto the cases you discuss.

for case 2, I don't quite understand the solution. After the rotation, Z and A are still red. Does that not violate the red-black-tree property?

that relatable moment when your parent is white but your uncle is black

I feel like all of the trees violated the black property

crazy explaination

hope thae same vedio to understand deletions in red Black tree.

Please make more videos

why A can be in the right subtree when the root is B?

the best explanation i ever seen, thanx

I am black and i do not like the tone in which he is addressing my uncle

In Case 2 you already violate the child relationship as you still have a red child as a child for a red parent after rotation

I need the Red-Black trees deletion video

thank you

It would be nice to emphasize which rules each case violates...

wow, great video!