Red-black trees in 3 minutes - Rotations

[@DVZM.]

It is very sad that you stopped making those amazing videos...

[@SkywarsLobby]

he's back :)

[@josephsnow3432]

@@SkywarsLobby :(

[@leo6d985]

You didn't get enough credit for these, they are appreciated it.

[@andrewmartin4045]

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.

[@MichaelSambol]

Very good suggestion, thank you!

[@piyushnariani09]

Please post the video of Red-Black Tree Deletion as well

[@kevingraham9831]

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.

[@yash1152]

'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.

[@NOLAMarathon2010]

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!

[@anuhyasai28]

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)

[@KennyChowPD]

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).

[@eminkilicaslan8945]

@@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.

[@AnonymousDeveloper1]

You make great videos about algorithms. Please keep it up and produce more videos like that! Short, easy and very helpful.

[@TheEpicBlend]

Your videos are awesome! Straight to the point and short compared to the others on youtube.

[@Randeesha]

superb explanation within 3.04 mins.. wow... good luck...

[@vhcsilvaa]

Congrats Michael and thanks, your videos are amazing. I wish my college professor were as good as you.

[@davidcain3752]

Hah, its almost like they're getting paid by your university which you pay tuition to go to...

[@vanshrana9508]

One of the best Videos yet, understood everything perfectly😊

[@賊貓]

Thank you for you picture illustration. It's super clear!!!!

[@StreamerSagaYT]

Exams in next 10 min .... Huh.

[@jeff2573]

same lol

[@manishmayank4199]

not 10 min, but yeah, you got me.

[@Esteria]

In the middle of my exam 💀

[@awesomemilkshake6612]

@@Esteria bro I-

[@awesomemilkshake6612]

Not really, but homework due in 1 hour lol

[@merinkjacob2443]

Dear Michael, Thank you very much for this video. You are my saviour :)

[@Gary-lh4fg]

Very clear, methodical and intuitive

[@terigopula]

Crisp, concise and clear.

[@DavidEspinosa21]

Useful, thanks so much, I was confused on rotating but it's actually simple

[@riccardofratuzztazz]

Bro thank you the explanation was so good you saved me👍👍

[@12husnainabbas]

your videos are very helpful, keep up the good work!!

[@PL_chochlikman]

in few years if you will hold this level of video's you;ll be number one youtuber of informatics xD

[@DVZM.]

yeah he stopped immediatelly...

[@stephenhowe4107]

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.

[@yash1152]

2:23 i knew right away on seeing this that it is Cormen Intro to DAA

[@bassilorabii7183]

Very Helpful and quick !

[@leenlovesdancing3561]

I wish it was explained like that in data structure lectures. :D

[@Ananasbleu]

Amazing explanations. Thanks

[@sdshsjg]

best guide ever

[@_mrix_534]

By doing a rotation we are simulating the right order of inserting node

[@king_esteban]

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

[@Nadzap]

awesome video, thanks man

[@akshatjain7797]

Really helpfull ....please make more videos on algorithms and analysis

[@claytonwasenius1304]

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.

[@ThomasEdits]

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.

[@jastejsingh5062]

just a question ...the concept of rotations is the same also for an avl right ? the left and right rotations.

[@jessadreamer]

Hi Michael..can you do a video on Big O notation? I like your explanations on these CS topics!

[@coreylallojr5392]

thank you so much, this was extremely helpful for my first implementation, the psuedocode helped my understanding greatly!

[@nyahhbinghi]

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?

[@MichaelSambol]

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.

[@ambatirakesh5597]

Please make videos on design and and analysis of algorithms

[@nxpy6684]

This is Fireship if he taught Data Structures !

[@任安明]

i like it so much。 thank you

[@greshmalizgeorge]

Hello sir, is there a video for red black deletion? and the videos are amazing. tysm :)

[@amanchhabra1161]

where. is video for deletion

[@dennistu]

it was deleted

[@DVZM.]

@@dennistu hhahaha

[@h3Xh3Xh3X]

Too short, should have explained node by node or at least stated general rules first.

[@rishimalishetti5094]

Exam in 2 minutes

[@lucutes2936]

nice name

[@academicconnorshorten6171]

Deletion!! Lol

[@asadullahrafiq-em1pz]

these sesseion are for indian not foreigeiner

[@FanaticBall]

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.

[@AryanSingh2512.]

please skip this video.