That's my fault. Case 2 is essentially a partial fix that Case 3 ultimately fixes. In other words, Case 2 gets you closer to the solution, and Case 3 finishes the job by correcting the remaining violations. I should have been more clear. If you watch my example video, I hope it makes sense.
Case 2 needs a double rotation. First right rotation between(A,Z) and then left rotation between(B,Z). Triangl is always a double rotation. Line just one rotation. After all Z is root and black, B and Z are childs of Z and red. C is black and a leaf.
Cannot thank you enough for these four simple scenarios. Just implemented it listening to your video a few times and it magically works (tested all cases). Now on to node removal.
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.
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.
I think it's not missed, at th-cam.com/video/5IBxA-bZZH8/w-d-xo.htmlsi=yeiuXO7fadUYHvb1&t=90 it's pointed that we're applying fixes *only* if there's a violation, and the only possible violations are: (1) if we're inserting red root (2) if we're inserting into red parent Conclusion: if inserting into black parent - there's no violation, so no need to do anything. Also in attached algorithm, in fixup function we follow with fixup only if we find the parent to be red (or being at root)
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.
It does. But case 2 transforms the problem into case 3. Afterwards you apply case 3 which also involves recolourations and it is this final step that sorts out the tree. Case 2 make sure that the node that requires repairing is no longer on the inside but on the outside. You cannot repair the tree if the node is on the inside. Note, the parent of Z is now regarded as the new Z, then case 3 applies.
Thank you for your video! Correct me if I wrong, but at 3:30 you violated property 4: "for each node, all simple paths from the node to descendant leaves contain the same number of black nodes". Same violation at 4:25.
You are absolutely correct. These are mostly subtrees (trimmed so there was less clutter on screen); I should have been more clear. Can you look at this video for full examples: th-cam.com/video/A3JZinzkMpk/w-d-xo.html For instance, at 4:25 Z can and should have children under it. Z and B would have to have the same "black height" for this to be a valid red-black tree. Hopefully my other video clears that up. Thanks for pointing it out!
I might just be stupid but in the tree at 4:25, how can we say it's a black-red tree ? if we add the nil nodes to C, D and Z, the black height for the nodes to the right of A will be 1 and for the nodes to the left of A it will be 2. Or am I wrong ?
@@MichaelSambol I was talking about case 3 not case 2, i'm wondering about the way we're counting the number of black nodes encountered, and not two consecutive red nodes.
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.
Another way to think about it is that when you get to the end of his explanation of case 2, you are immediately in case 3. If you then execute that logic, your tree will be fixed.
2:35 => B is red because it means the black tree height of nodes from root through C to its leafs has not changed. The swapping of colours of parent and uncle with grandparent preserves black tree height. But what you have not said is that the grandparent needs to be considered as z and the fixups applied again (in fact it could repeat right to the root), because the grandparent might have a parent which is also red and in which case you now have another double red violation. The whole thing stops when the parent of any z is black or the uncle is black (rotations now kick in) or you reach the root node (and if this has been recoloured red, it needs to be recoloured black).
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.
at 3:30 after rotation rule 3 is being violated shouldn't we recolor after rotation? and in case 1 at 2:20 what id Z's parent is black then after recoloring it will violate rule 3 again
How does case 1 violate any rules since A isn't guaranteed to be red by any property of RB Trees? I mean Z's uncle being red doesn't necessarily imply that A is red too, to create any violation.
in case 3, you violate the rules for every path from a node to an abitary leave, number of nodes remains the same, which is 2 if we start from A to C (C and his null), and 1 from A to Z (his null only)
Insertion is slightly confusing for RB trees... A full walkthrough on inserting a list of values into a RB tree would've helped understand it a bit better. You should do AVL trees next.
In the pseudocode at the end of the video the last line of Insert-Fixup is make root black. So my guess is simply color the root black if it ends up being red
I know this old, but if anyone else is curious: The pseudo-code in this book (Introduction to Algorithms) is confusing around if-else statements. Notice they have both elseif and else if, the difference being a space between the words. The elseif is what you would expect. The else if is more like ...} else { if{...} }. It's a subtle difference but matters in this case.
See the conversation in the pinned chat. I wish I did a better job with the coloring on this video. I was trying to demonstrate the actions and didn't pay enough attention to coloring. In the next example, all the coloring is correct. Apologies for any confusion.
You might already figured it out but just put here if someone has the same question. In RB tree, we need nil node when reviewing color in balancing process. Just leaving it as None could make your code more complex. So when defining "Tree.__init__", declare "self.NIL" and assign a tree node which children are None to it. Its parent can be None as well and its value is not important, just give it any number you can identify when debugging. Don't forget to paint it to black.
I suppose you're interested in the fixup code and not the insertion. Step 8 changes z to its grandparent, to check for new violations that might have appeared when recoloring. Then the formating is, i believe, a bit messed up. I think it should be an else, in which there is an if. If y is red, do the recoloring (steps 5 to 8) If not, then y is black, and we need to check if it's case 2, that's what the if does (it check if it's a "line" or "triangle"). If it's a case 2, we apply the first rotation, then in any case where y is black we apply another rotation. if y is red { recolor parent, grand parent and uncle } else (y is black) { if z is its parent's right (case 2, triangle) { rotate left } recolor and rotate right }
I think both case 2 and case 3 are impossible to appear because they both violate rule 4 even before z is inserted, I am confused why there are these 4 cases.
Case 2 and 3 are result of manipulation of case 1, u are correct they don't exist at insertion level, we loop our way towards the root node till we find parent and child of different colors
No one seems to explain that case for some reason. Everyone just leaves the root black in all times I've seen. Weird no explanation. Edit: I'm guessing it has something to do with the black height being the same if you just leave the root black, but still weird no one touches that idea.
It's the combination of two cases : First, you do the basic recoloring of the parent, grand parent and uncle. That's case 1. Now you move to the grandparent to check for new violations, so your new Z is your old Z's grandparent. Which, in your case, is the tree's root. So, Z is root and red : you simply recolor to fix violation. That's case 0. It's okay to simply recolor Z : It's going to be black, as it should. Since it's black, you don't care about its child's color, they can be either red or black. And since it's the root, if you change it to black, you're going to increase the black height of every branch equally : Every violation is fixed.
this video has made me more confused at 3:30........ Z and A are RED AND ADJACENT!!!!!!!!!!!!!!!!! So why in hell would it not violate the rbtree properties?????????????
It can't. But what Michael is describing is the fixups necessary to make that so. So Insert introduces a red node as a leaf node. Afterwards if the tree breaks the 4 rules (only 2 rules could be broken - root is red or 2 red nodes in succession), this procedure is the fixups necessary to repair the tree. And in mathematical notation, fixups go in the direction of the root, a maximum of O(log N) fixups are required. Delete also may require fixups. After some tree manipulation, you can arrange it so you are deleting a node with 0 or 1 children. 1-child is an easy case. Also 0-child (so it is a leaf node) where the node is Red is an easy case as well. The hard case is 0-child and the node is Black. Because if you delete that, you violate the property that the Black tree path count is the same for every path. You now have to do fixups towards the root, looking to restore the Black tree path count for this branch of the tree. This can always be done.
The author mentioned in a reply to another similar comment that case 2 in the video is only a partial fix. After case 2, case 3 is applied to completely fix the violation
Nope. The history of it, is that at the time it was devised, the programmers only had red and black marker pens on white computer paper, so that is why those colours were chosen. This is reading racism into what was never there in the first place.
I'm confused. In case 2, you have a red child with a red parent.
That's my fault. Case 2 is essentially a partial fix that Case 3 ultimately fixes. In other words, Case 2 gets you closer to the solution, and Case 3 finishes the job by correcting the remaining violations. I should have been more clear. If you watch my example video, I hope it makes sense.
Case 2 needs a double rotation. First right rotation between(A,Z) and then left rotation between(B,Z). Triangl is always a double rotation. Line just one rotation. After all Z is root and black, B and Z are childs of Z and red. C is black and a leaf.
I think that before insert 'z',it is NIL node,we have to insert 'z' which must be red ,so a red child with a red parent
@@marieh7957 Can't you just color Z black after performing the one rotation in the video?
@@marieh7957 B and A are childs of Z and red.
Cannot thank you enough for these four simple scenarios. Just implemented it listening to your video a few times and it magically works (tested all cases).
Now on to node removal.
Super awesome to hear this! Thanks for watching the videos.
these are probably the best tutorials on youtube. They are so short, but they dont leave out any of the complexity! Thanks!
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.
me too,and I am from China
@@MichaelChiang-i2d welcome, I'm from Jordan
@@MichaelChiang-i2d Are you teochew, also your surname name is not pinyin
1:46 bro was smiling when he said that 😂
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.
thank you.
I think it's not missed, at th-cam.com/video/5IBxA-bZZH8/w-d-xo.htmlsi=yeiuXO7fadUYHvb1&t=90 it's pointed that we're applying fixes *only* if there's a violation, and the only possible violations are: (1) if we're inserting red root (2) if we're inserting into red parent
Conclusion: if inserting into black parent - there's no violation, so no need to do anything.
Also in attached algorithm, in fixup function we follow with fixup only if we find the parent to be red (or being at root)
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.
crisp and clear explanation. super . Great effort. thanks
Best video series to understand red black tree
Thanks! I spent hours to learn this things. But your video gives me the final knowledge, so I'm trusting myself I can do this
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?
It does. But case 2 transforms the problem into case 3. Afterwards you apply case 3 which also involves recolourations and it is this final step that sorts out the tree. Case 2 make sure that the node that requires repairing is no longer on the inside but on the outside. You cannot repair the tree if the node is on the inside. Note, the parent of Z is now regarded as the new Z, then case 3 applies.
@@stephenhowe4107 THANK YOU, mf excluded the critical "obvious" my ass context just like a university lecturer
Thank you for your video!
Correct me if I wrong, but at 3:30 you violated property 4: "for each node, all simple paths from the node to descendant leaves contain the same number of black nodes".
Same violation at 4:25.
You are absolutely correct. These are mostly subtrees (trimmed so there was less clutter on screen); I should have been more clear. Can you look at this video for full examples: th-cam.com/video/A3JZinzkMpk/w-d-xo.html
For instance, at 4:25 Z can and should have children under it. Z and B would have to have the same "black height" for this to be a valid red-black tree. Hopefully my other video clears that up. Thanks for pointing it out!
The tree at 4:25 can never get created if the tree was made from the first node as a Red-Black Tree
Although it's good to illustrate what would happen with a left son of A (which is NULL in this case)
@@wesley_khan This really explains well. Good one, thanks！
I might just be stupid but in the tree at 4:25, how can we say it's a black-red tree ? if we add the nil nodes to C, D and Z, the black height for the nodes to the right of A will be 1 and for the nodes to the left of A it will be 2. Or am I wrong ?
See the pinned comment. Hope that helps
@@MichaelSambol I was talking about case 3 not case 2, i'm wondering about the way we're counting the number of black nodes encountered, and not two consecutive red nodes.
Thanks for this vidoe It is helpful for me and saved me a lot of time and effort.
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.
Great explanation! Help me much.
In case 2 at 3:29, after rotation, Z and A are red, is that ok?
I think that's an error. Red nodes would need to have black children so I think we have to recolor A
Another way to think about it is that when you get to the end of his explanation of case 2, you are immediately in case 3. If you then execute that logic, your tree will be fixed.
2:35 => B is red because it means the black tree height of nodes from root through C to its leafs has not changed. The swapping of colours of parent and uncle with grandparent preserves black tree height. But what you have not said is that the grandparent needs to be considered as z and the fixups applied again (in fact it could repeat right to the root), because the grandparent might have a parent which is also red and in which case you now have another double red violation. The whole thing stops when the parent of any z is black or the uncle is black (rotations now kick in) or you reach the root node (and if this has been recoloured red, it needs to be recoloured black).
2:20 I have to assume that in the case of this being actually just a 4-node tree, the top 3 nodes would be black and the bottom red.
Another banger, awesome job man😊
this is great but id really appreciate if you added comments to the code to show which cases each block was handling - thanks
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.
at 3:30 after rotation rule 3 is being violated shouldn't we recolor after rotation?
and in case 1 at 2:20 what id Z's parent is black then after recoloring it will violate rule 3 again
Correct.. see the pinned comment. Apologies!
How does case 1 violate any rules since A isn't guaranteed to be red by any property of RB Trees? I mean Z's uncle being red doesn't necessarily imply that A is red too, to create any violation.
Great explanation ..Thank you so much ..
You are welcome!
hope thae same vedio to understand deletions in red Black tree.
Awesomee Explaination! Thankssss Alottt brother
in case 3, you violate the rules for every path from a node to an abitary leave, number of nodes remains the same, which is 2 if we start from A to C (C and his null), and 1 from A to Z (his null only)
See the pinned comment. These are partial fixes (I should have said that in the video). The example video shows full fixes. Sorry for any confusion!
Insertion is slightly confusing for RB trees... A full walkthrough on inserting a list of values into a RB tree would've helped understand it a bit better. You should do AVL trees next.
Ankur Sundara Give me a few days and I'll have another video!
Excellent work!
Thanks a lot bro for charming explanation 😊😊😊
Good lecture and awesome strategy, but is the leave nil? Should them be paint as black? Why your leaves nodes have red color?
Clean and simple :) Thank you
thank you Michael~
In case 1 the structure is a triangle, does that characteristic matter? Because in case 2 it mattered.
At 3:30, the red node is having red child, which violates the RBT property.
When you rotate case 2 you create case 3 (line)
for 3:30 isnt it violating the rule because of two consecutive roots?
Sir in case 3 black height of tree is not balanced
crazy explaination
Didnt realize, 5 min was so Long
"As you can see C is Z's uncle" great video but you might have chosen better names for the nodes
wow, great video!
Is possible to have a similar video for deletion?
Thanks for the video. For Case-1, the solution is recolor, but after recolor you have a red root, which is a violation. how do we fix that? Rotation?
In the pseudocode at the end of the video the last line of Insert-Fixup is make root black. So my guess is simply color the root black if it ends up being red
I am black and i do not like the tone in which he is addressing my uncle
Getting z on rhs of tree is ok but b c and d to the lhs of a ??? Aren't they suppose to be bigger than A
the best explanation i ever seen, thanx
Thank you for the video! Could you consider posting AVL tree when you have time? thank you!
Yes!
Do you have a video for deletion in Red Black tree? please reply
dude just collect all the values of the tree except the one you want to delete, make root null and add all them back lol
Thats a fucking terrible solution
I said lol dude :(
hahahhaha
@@beko_61 hahah i love brute force
At 5:23, is there a "else" missing where it refers to case 3 (after LEFT-ROTATE(T, z))?
I know this old, but if anyone else is curious: The pseudo-code in this book (Introduction to Algorithms) is confusing around if-else statements. Notice they have both elseif and else if, the difference being a space between the words. The elseif is what you would expect. The else if is more like ...} else { if{...} }. It's a subtle difference but matters in this case.
@@evandoug90 Thank you, that was confusing me as well
Awesome!
perfect, thanks!
Plz make vedio on deletion sir
Anyone knows what "key" means in the pseudo code?
If this would have explained with numbers it would be more clear.
But why at the end of case 2 are there two red nodes aside ?
See the conversation in the pinned chat. I wish I did a better job with the coloring on this video. I was trying to demonstrate the actions and didn't pay enough attention to coloring. In the next example, all the coloring is correct. Apologies for any confusion.
Great videos, thank yoU!
Hey..will you please do an deletion video as well... please..I need it so bad..😭😭😭
yes i will do it for you
Can make video on rb tree deletion in 4 minutes please
why do you perform any of these operations when the tree remains balanced.
Check the conditions here for rebalancing: github.com/msambol/dsa/blob/master/trees/red_black_tree.py#L97
For python students, what property would "T.nil" be in the pseudo?
You might already figured it out but just put here if someone has the same question.
In RB tree, we need nil node when reviewing color in balancing process. Just leaving it as None could make your code more complex. So when defining "Tree.__init__", declare "self.NIL" and assign a tree node which children are None to it. Its parent can be None as well and its value is not important, just give it any number you can identify when debugging. Don't forget to paint it to black.
It would be nice to emphasize which rules each case violates...
Plz make video on red black tree deletion
I need the Red-Black trees deletion video
Can u explain step 8 and 10 of the pseudo code given at the end please
I suppose you're interested in the fixup code and not the insertion.
Step 8 changes z to its grandparent, to check for new violations that might have appeared when recoloring.
Then the formating is, i believe, a bit messed up. I think it should be an else, in which there is an if.
If y is red, do the recoloring (steps 5 to 8)
If not, then y is black, and we need to check if it's case 2, that's what the if does (it check if it's a "line" or "triangle").
If it's a case 2, we apply the first rotation, then in any case where y is black we apply another rotation.
if y is red
{
recolor parent, grand parent and uncle
}
else (y is black)
{
if z is its parent's right (case 2, triangle)
{
rotate left
}
recolor and rotate right
}
Please make more videos
5:12 i saw that pseodocode in "introduction to algorithms" but didn't quite understand that.
thank you
I think both case 2 and case 3 are impossible to appear because they both violate rule 4 even before z is inserted, I am confused why there are these 4 cases.
Case 2 and 3 are result of manipulation of case 1, u are correct they don't exist at insertion level, we loop our way towards the root node till we find parent and child of different colors
At 3:30, didn't you violate property 3 as well, "every red node has a black child"!?
Tomorrow is my exam but I can't understand deletions in red Black tree.
you passed in your xam ?
What if the uncle is red and the grandparent is actually the root?
No one seems to explain that case for some reason. Everyone just leaves the root black in all times I've seen. Weird no explanation.
Edit:
I'm guessing it has something to do with the black height being the same if you just leave the root black, but still weird no one touches that idea.
It's the combination of two cases :
First, you do the basic recoloring of the parent, grand parent and uncle. That's case 1.
Now you move to the grandparent to check for new violations, so your new Z is your old Z's grandparent.
Which, in your case, is the tree's root.
So, Z is root and red : you simply recolor to fix violation. That's case 0.
It's okay to simply recolor Z : It's going to be black, as it should. Since it's black, you don't care about its child's color, they can be either red or black. And since it's the root, if you change it to black, you're going to increase the black height of every branch equally : Every violation is fixed.
Uncle ?wtf !!
bohot hard
bro how does "A" become larger than "Z"
What about the cases where Z has no uncle?
If Z has no uncle, then it has no grandparent, and its parent must be black. So you can insert a red node without violating any of the properties.
that relatable moment when your parent is white but your uncle is black
I feel like all of the trees violated the black property
this video has made me more confused at 3:30........ Z and A are RED AND ADJACENT!!!!!!!!!!!!!!!!! So why in hell would it not violate the rbtree properties?????????????
I thought red node cannot have a red node as a parent or a child?
It can't. But what Michael is describing is the fixups necessary to make that so.
So Insert introduces a red node as a leaf node. Afterwards if the tree breaks the 4 rules (only 2 rules could be broken - root is red or 2 red nodes in succession), this procedure is the fixups necessary to repair the tree.
And in mathematical notation, fixups go in the direction of the root, a maximum of O(log N) fixups are required.
Delete also may require fixups. After some tree manipulation, you can arrange it so you are deleting a node with 0 or 1 children. 1-child is an easy case. Also 0-child (so it is a leaf node) where the node is Red is an easy case as well.
The hard case is 0-child and the node is Black. Because if you delete that, you violate the property that the Black tree path count is the same for every path. You now have to do fixups towards the root, looking to restore the Black tree path count for this branch of the tree. This can always be done.
@@stephenhowe4107 yes I understand now, I was a bit frustrated when I left the comment thanks
Why do you have to use the term "uncle"...it gets even more confusing!
guys i think z's uncle might be black
Is that Comic Sans?
why A can be in the right subtree when the root is B?
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
The author mentioned in a reply to another similar comment that case 2 in the video is only a partial fix. After case 2, case 3 is applied to completely fix the violation
Holy shit i'm so dumb
nahhh these take a bit to understand.
😉🙏
Thank you!
This data structure is so racist lol xD
Nope. The history of it, is that at the time it was devised, the programmers only had red and black marker pens on white computer paper, so that is why those colours were chosen. This is reading racism into what was never there in the first place.
@@stephenhowe4107 was literally a joke chill
Uncle 😂
A dump lecture
bite me
black man love red aunt
You are wrong Englishman
what in the racist....