Even though I dont understand some of the terms you use (its me on since Im not that good in DSA) but as a whole I like the way you explain things. Im currently studying DSA.
Thanks! This video is part of a series, and it is probably a good idea to first watch the video that introduces binary search trees (ua-cam.com/video/qIJCoaTrHVI/v-deo.htmlsi=N-9x-yNDKw8VcHmi) Success with studying Data Structures and Algorithms!
Nice and enlightening video, thanks! If I'd dare some criticism, It could be more clear the reason for the rotation in case2. It seems almost like the criterium is whether it's the right or left child of the parent, but that depends again on which child the parent is of the grandparent. Anyway, it's the most informative video I found on the topic, so good job!
Thanks, good point. From the perspective of the algorithm it makes sense to order the cases as they are (i.e. discuss the corresponding slide from left to right). But for explaining why we have the cases, it might be better to go from right to left (i.e. what do we want to achieve, how we get if from case 3, and then how we get case 3, in case we have case 2). Anyway, you figured it out, so I achieved my goal!
Red-black trees are balanced. Maybe there is a small misunderstanding what balanced means? "Balanced" means that the height is in O(log n) (see 00:20-00:35). Note that this is O(log n) and not log n. The smallest height that a binary tree can have is log n, but updates (insert/delete) would take long, if we would always want to have height log n. Asking for height = O(log n) instead, gives us enough flexibility to get efficient updates (i.e. O(log n)), while still getting operations like search (which are in O(height) in O(log n) time. Specifically, the height of a red-black tree is guaranteed to be at most 2*log (n+1) =O(log n), see 04:53. To get a feeling for how unbalanced a red-black tree can get, it can be helpful to use a visualizer like www.cs.usfca.edu/~galles/visualization/RedBlack.html . If you for instance insert 1,2,3,4,5,6,... you will see how the rotations remove the imbalance. In particular, the height is never more than 2 times what the most balanced tree would have. Does this answer your question?
I wonder whether a all-black linear list could be seen as RBT.I understand that the corresponding operations guarantee that such trees can not be built.But, it's the definition that comes first. According to my search, as long as a BST that satisfies those 5 requirements should be called RBT. Like 1->2->3->4->NULL with all black color, the case at least to me does not violate any of those properties or I just missed something.
Great question. The trick here is that we always include the NIL-Nodes and give them a black color. Note that this is a bit different from how we normally look at the nodes of a binary tree: If a child is NIL (or None in Python), then we would normally just see it as not being there. But to make red-black trees here, we need these NIL nodes to be black. So this already prevents the example of a linear list. In your example the nodes 1,2,3, and 4 would all have an extra NULL (or NIL) attached to them. Therefore starting at 1 there are many paths to leaves 1 -> NULL or 1-> 2 -> NULL etc. They have different lengths, which contradicts property 5. We prove that a red-black tree with n nodes has a height bounded by 2 log(n+1). This follows from the properties, so if a black list would satisfy the properties (which has height n), then something with the properties would have been wrong. I hope this clarifies the role of the NIL-nodes, and thanks for watching!
@@algorithmslab Yes, the concept is now much clear to me. Many proofs for the upper bound of the height are using induction, which seems less intuitive to me. Your proof is concise and easy to follow for me. Thanks for the detailed and patient reply.
But wait, how did you fix the RB properties at 17:56, if #5 is violated? "For each node, all paths from the node to descendant leaves contain the same number of black nodes".
The important observation here, is that #5 is actually never violated (i.e. assuming it holds at the beginning, all operations that we do don't break it). When inserting a new node, we make it red. So assuming that I had a correct tree before, the only violation that I now might have is one red child-parent pair. This is fixed in "Step 3". For all operations in Step 3 it is quite clear that they don't introduce a violation of #5. Only for the last rotation (the right rotation on the slide) we have to be careful. There we recolor z and b. But I explain, starting at 17:18, why property #5 still holds, assuming it was true before. So in short, the recoloring of z and b is what we do to make sure that #5 is not violated. I hope this answers the question.
Thanks for the compliment and thanks for the suggestion. Since publishing the videos and replying to questions/discussions here is something I have to fit in on the side, for now, I prefer to focus my attention on the youtube channel.
This is the only tutorial that explained when to do recoloring or rotation in a clear and simple way.
I wish I could give 10x likes.
Thank You!
Many thanks for all the very informative videos. Your explanations are great, and have helped me learn a great deal. Thanks for your hard work!
Very concise and clear, thank you very much Professor!
Excellent explanation. And thank you for assuming knowledge of BSTs and such.
you deserve more subscribers
Thanks! I am already amazed by how many views some of my videos got in the last couple of months.
@@algorithmslab You shall get more. I am a teacher myself and I can see the potential that your quality of explanation has.
Agreed. Subscribed.
Agree
Even though I dont understand some of the terms you use (its me on since Im not that good in DSA) but as a whole I like the way you explain things. Im currently studying DSA.
Thanks! This video is part of a series, and it is probably a good idea to first watch the video that introduces binary search trees (ua-cam.com/video/qIJCoaTrHVI/v-deo.htmlsi=N-9x-yNDKw8VcHmi) Success with studying Data Structures and Algorithms!
Nice and enlightening video, thanks! If I'd dare some criticism, It could be more clear the reason for the rotation in case2. It seems almost like the criterium is whether it's the right or left child of the parent, but that depends again on which child the parent is of the grandparent. Anyway, it's the most informative video I found on the topic, so good job!
Thanks, good point. From the perspective of the algorithm it makes sense to order the cases as they are (i.e. discuss the corresponding slide from left to right). But for explaining why we have the cases, it might be better to go from right to left (i.e. what do we want to achieve, how we get if from case 3, and then how we get case 3, in case we have case 2). Anyway, you figured it out, so I achieved my goal!
nice video and simple explanation sir
thanks!
But the resulting tree is not balanced, or is there something I might have missed?
Red-black trees are balanced. Maybe there is a small misunderstanding what balanced means? "Balanced" means that the height is in O(log n) (see 00:20-00:35). Note that this is O(log n) and not log n. The smallest height that a binary tree can have is log n, but updates (insert/delete) would take long, if we would always want to have height log n. Asking for height = O(log n) instead, gives us enough flexibility to get efficient updates (i.e. O(log n)), while still getting operations like search (which are in O(height) in O(log n) time. Specifically, the height of a red-black tree is guaranteed to be at most 2*log (n+1) =O(log n), see 04:53.
To get a feeling for how unbalanced a red-black tree can get, it can be helpful to use a visualizer like www.cs.usfca.edu/~galles/visualization/RedBlack.html . If you for instance insert 1,2,3,4,5,6,... you will see how the rotations remove the imbalance. In particular, the height is never more than 2 times what the most balanced tree would have.
Does this answer your question?
@@algorithmslab Thanks so much. This was very helpful. Thanks for the visualizer link as well.
I wonder whether a all-black linear list could be seen as RBT.I understand that the corresponding operations guarantee that such trees can not be built.But, it's the definition that comes first. According to my search, as long as a BST that satisfies those 5 requirements should be called RBT. Like 1->2->3->4->NULL with all black color, the case at least to me does not violate any of those properties or I just missed something.
Great question. The trick here is that we always include the NIL-Nodes and give them a black color. Note that this is a bit different from how we normally look at the nodes of a binary tree: If a child is NIL (or None in Python), then we would normally just see it as not being there. But to make red-black trees here, we need these NIL nodes to be black.
So this already prevents the example of a linear list. In your example the nodes 1,2,3, and 4 would all have an extra NULL (or NIL) attached to them. Therefore starting at 1 there are many paths to leaves 1 -> NULL or 1-> 2 -> NULL etc. They have different lengths, which contradicts property 5.
We prove that a red-black tree with n nodes has a height bounded by 2 log(n+1). This follows from the properties, so if a black list would satisfy the properties (which has height n), then something with the properties would have been wrong.
I hope this clarifies the role of the NIL-nodes, and thanks for watching!
@@algorithmslab Yes, the concept is now much clear to me. Many proofs for the upper bound of the height are using induction, which seems less intuitive to me. Your proof is concise and easy to follow for me. Thanks for the detailed and patient reply.
awesome vid :)
But wait, how did you fix the RB properties at 17:56, if #5 is violated? "For each node, all paths from the node to descendant leaves contain the same number of black nodes".
The important observation here, is that #5 is actually never violated (i.e. assuming it holds at the beginning, all operations that we do don't break it). When inserting a new node, we make it red. So assuming that I had a correct tree before, the only violation that I now might have is one red child-parent pair. This is fixed in "Step 3". For all operations in Step 3 it is quite clear that they don't introduce a violation of #5. Only for the last rotation (the right rotation on the slide) we have to be careful. There we recolor z and b. But I explain, starting at 17:18, why property #5 still holds, assuming it was true before. So in short, the recoloring of z and b is what we do to make sure that #5 is not violated. I hope this answers the question.
Could you put this video on Odysee, please? It is excellent! Thanks you!
Thanks for the compliment and thanks for the suggestion. Since publishing the videos and replying to questions/discussions here is something I have to fit in on the side, for now, I prefer to focus my attention on the youtube channel.
@@algorithmslab You did make a nicely complete video about red/black. Gets the abstraction out of the window. Thanks again!