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.
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 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.
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.
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 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 ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-5IBxA-bZZH8.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)
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.
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.
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: ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-A3JZinzkMpk.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!
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.
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.
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.
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.
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?????????????
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.
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
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 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)
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
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.
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).
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.
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.
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
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.
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
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 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.
