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.
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.
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.
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.
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.
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.
It is very sad that you stopped making those amazing videos...
he's back :)
@@SkywarsLobby :(
You didn't get enough credit for these, they are appreciated it.
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.
Very good suggestion, thank you!
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.
'cz balancing aspect of rotation in R-B Tree becomes apparent only with insertion deletion etc.
u dont just rotate on whim in rb-tree to balance.
Please post the video of Red-Black Tree Deletion as well
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!
The height of a Red-Black tree is always O(Logn) where n is the number of nodes in the tree. 2* log(n+1) is still O(Logn)
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.
You make great videos about algorithms. Please keep it up and produce more videos like that! Short, easy and very helpful.
One of the best Videos yet, understood everything perfectly😊
superb explanation within 3.04 mins.. wow... good luck...
Your videos are awesome! Straight to the point and short compared to the others on youtube.
Thank you for you picture illustration. It's super clear!!!!
Congrats Michael and thanks, your videos are amazing. I wish my college professor were as good as you.
Hah, its almost like they're getting paid by your university which you pay tuition to go to...
Exams in next 10 min .... Huh.
same lol
not 10 min, but yeah, you got me.
In the middle of my exam 💀
@@Esteria bro I-
Not really, but homework due in 1 hour lol
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.
Very clear, methodical and intuitive
in few years if you will hold this level of video's you;ll be number one youtuber of informatics xD
yeah he stopped immediatelly...
Dear Michael, Thank you very much for this video. You are my saviour :)
Bro thank you the explanation was so good you saved me👍👍
Crisp, concise and clear.
By doing a rotation we are simulating the right order of inserting node
Useful, thanks so much, I was confused on rotating but it's actually simple
your videos are very helpful, keep up the good work!!
Amazing explanations. Thanks
I wish it was explained like that in data structure lectures. :D
awesome video, thanks man
Very Helpful and quick !
best guide ever
just a question ...the concept of rotations is the same also for an avl right ? the left and right rotations.
2:23 i knew right away on seeing this that it is Cormen Intro to DAA
Really helpfull ....please make more videos on algorithms and analysis
Hi Michael..can you do a video on Big O notation? I like your explanations on these CS topics!
thank you so much, this was extremely helpful for my first implementation, the psuedocode helped my understanding greatly!
so if I understand and did it correctly, is the solution to the the tree shown at 0:22 this?
12
/ \
8 15
/\ / \
5 9 13 23
/-(red)
19
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.
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.
Please make videos on design and and analysis of algorithms
i like it so much。 thank you
This is Fireship if he taught Data Structures !
Hello sir, is there a video for red black deletion?
and the videos are amazing. tysm :)
where. is video for deletion
it was deleted
@@dennistu hhahaha
Too short, should have explained node by node or at least stated general rules first.
nice name
Deletion!! Lol
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.
please skip this video.