ummm, you should have said whether right rotation is just mirror of left rotation? seems like answer is yes? maybe add annotations after the fact? that would be beautiful. Also, I don't know when to call leftRotate(x) or rightRotate(y), what is the context? appropriate conditon for which to make those calls?
Yeah, it's just a mirror. Check out the other videos in the playlist on when you use rotations (i.e., when you insert and delete so the tree keeps RB properties). Also the code in my GitHub shows them in action.
I love the conciseness of these videos, Michael! Keep up the great work! One recommendation I have is to make the pseudocode you provide more approachable by re-labeling the variables to match your diagrams.
Michael, this is a great playlist on Red-black trees. However, for the rotation video, I'd give an example that accomplishes the goal of decreasing the height of the tree. Your example was fine in demonstrating rotation, but did not help with balancing. Please keep up the high quality teaching. You are a great help to many people.
ok, i can understand why you rotated the 10, 5, 2 and the 12 since they're all connected. But why did you flip 8 to the other side of the tree?? No explanation. Just confused. Even if you keep the 8 on the same side in either rotation instead of changing it to the other side, it would still be balanced.
4 years ago but incase anyone reading now wonder the same: the 8 starts off as the left-child of 10, but after the rotation the left-child of 10 is now 5 instead a node cannot have 2 left children, so we must now store 8 somewhere else. luckily, since 10 was originally 5's right-child, it means that that 5's right-child spot is now free, since 10 is 5's parent now instead. therefore we can store 8 as 5's right-child it still conforms to the structure of binary tree structure since 8 was originally on the right sub-tree of 5, and we know all elements of that right-subtree must be greater than 5, so it therefore applies that 8 can go to the right of 5. ALSO, since 8 was originally the left -child of 10 (to the left of 10), we know it must go somewhere on the left subtree of 10, which ends up as the subtree with 5 as the top node.
The other important fixup for Red-black trees is recolouring. A combination of recolouring and rotation is done on inserts & deletes to fixup red-black tree violations. Fixups go in the direction of the root node. For Insert, a maximum of 2 rotations are required. For Delete, a maximum of 3 rotations are required.
I've read elsewhere that the maximum height of a red-black tree is 2 * log(n + 1). This is not to say that this isn't a fantastic series of videos, because it is and they've helped me substantially! Thank you for that!
To be exact(if anyone is confused), in CS when we count the big O(worst case), we only care about the most influential term and take away its coefficient. Therefore the 2 & 1 in 2 * log(n + 1) should both be omitted, and you get O(log n).
@@KennyChowPD I might be wrong but it's for space or time complexity I think whereas we study the relation between the height of a tree and element count here.
To be honest you explain next to nothing, you just move the nodes around and read what a simple textbook says. Liked your other videos, you failed here.
