AVL 1 Introduction

[@fredericoamigo]

Best explanation i've come across so far. Brilliant and simple. Wonderful vid! Thank you so much for this!

[@oliverdo2163]

This is the best explaination of avl trees, I have ever heard. Thank you for being so clear and concise.

[@jakethewoz]

5:36 - What he means is he has a height of 3 children on the right of the four. This is why AVL trees call them 'heights' and not 'children', because it can be very confusing otherwise. Here, the four seems to have 4 children, but what the teacher means is that the height of its children is 3.

[@kirillholt2329]

thank you, that had me very confused

[@fredonianewmancenter3124]

As someone mentioned below, the last example is incorrect. But when we think about why, or how it should be done, we shouldn't start at the top and go down. We should think recursively, based on how node insertion works. Node insertion starts at the top of the tree and recursively descends until it finds the place to add the new node. Then, after adding the node, we unwind the recursion, returning back up the tree, updating the height as we go, checking each time whether the tree is unbalanced. In the example the tree is not unbalanced until we get back up to the root node, 4. That's why the (double) rotation should be centered on 4 (right on 10 and then left on 4, as mentioned below).

[@glowstonedust680]

this guy is insane the way it was explained it made so much sense

[@BloodHaZaRd666]

I wish I had Teatchers like him in my university.

[@fatihsonmez]

"so my tree is happy"

[@slitynskyy]

@RobEdwardsSDSU , there are several mistakes 1. Minor, there are number 8 written as 6. 2. Major - you are rotating wrong numbers near 6:00. You should rotate right and get 8 parent of 10 and 10 parent of 9 and 12 ( 9/10\12 ) and then rotate left and make 8 root.

[@shanjiang2078]

Agree, around 6:00, the violation node is 4, we should do a right left rotate on the subtree of 4 - 10 - 8, www.cs.usfca.edu/~galles/visualization/AVLtree.html this helps me

[@freshbreeze6180]

Thanks a bunch. The best explanation ever.

[@sikhokhelekhohliso4162]

Breaks down the problem properly. Love it

[@returnMarcco]

Thanks very much Dr. Rob, extremely well articulated information! Love the analogies. Home-wrecking single parents lol

[@TheElof]

This was exactly the instruction that I needed to understand height better, and to understand rotations. Thank you.

[@jalajkhanna6796]

how come first time 9 is considered to be the violating node and not 8. And later after left right, 10 is considered the violating node and not 12. How do we select the violating node ?

[@cpez47]

This last example is incorrect. Even though inserting 9 caused the violation, you only go down the tree 2 nodes from where the violation of rules occurs towards the violating node and choose that node's parent and grandparent for the rotations. In this case, the violation of rules occurs at node 4, so we go down the tree two nodes towards 9 and end up at 8. Then we perform a right rotation on 10 (the parent of 8) and a left rotation on 4 (the grandparent). This balances the tree in one set of rotations.

[@ParidTvShow1]

diese ubung ist nicht richtig

[@heikeneubau7064]

Thank you so much! Your videos on avl trees are great!

[@KansasFashion]

You are doing awesome lectures! Thanks so much!

[@sujaysshenoy247]

awesome explaination. ..but how is he writing those letters on glass.

[@natecolbert959]

My mind is fucked rn. Is he writing backwards?? Is the footage mirrored? I must know

[@MeinLink]

@@natecolbert959 Yeah, he's writing with the left hand and since most write with the right hand, I'd guess it's mirrored :D

[@ginicholas4322]

He's wearing a nike shirt, so yeah it's mirrored

[@DasBeatz]

@@ginicholas4322 I like how we are all watching CS videos and you're the only person who used logic to determine the video is mirrored. -_- our future is doomed.

[@iamhaileyrene]

Are you writing in mirror image? If so, that is impressive.

[@lordshardik]

I’ve been trying to figure that out, too. But I have a theory: Most people are right-handed. But he appears to be left-handed. So maybe he records them and flips the video afterwords. Or maybe he’s just left-handed and this is a live recording of a lecture. I couldn’t say for sure.

[@惜小夜]

Excellent video, helped me so much. Thanks!

[@mezzamate3252]

Great videos. Balancing makes a lot more sense, now.

[@diegocruzalves]

Excellent explanation!

[@danielstevens3020]

Great explanation, thank you Rob

[@definty]

2:40 you write 6 instead of 8

[@JournalistiekOnderzoek_4e]

Should be an 8

[@EricSmith-ts2pj]

at 5:53 ... why isn't the root the violation? can't you just do one rotation of the root to its left child from the start to fix it?

[@asahutchinsoniv9563]

great job explaining this! thank you

[@matejbeno569]

Nice explanation, thank you!

[@awienc]

I love your EKIN t-shirt

[@joelab.c]

Ok the video might be flipped....but what about him looking around like there are students in front of him?

[@icosmini]

Not sure why he is talking about the number of children. What is important is the height of the nodes, not the number of children.

[@jozicar]

this, confused me so much

[@hamzaelasri9051]

the height of the node is the number of children of the node

[@chanpreetsingh5054]

thats the same thing

[@andydaniel2]

@@jozicar Me too. It seemed like he had 3 children on the left of the 10 and he was saying 2 children. Thanks @Cosmin for explaining this.

[@gurkengerd9981]

@@chanpreetsingh5054 it is not, at 5:42 he says that the 4 has 3 children, but it has 4. What he means is the height/depth of the node.

[@arnavsaini3410]

Awesome explanation

[@matt-ex5ub]

very useful video now i understood thanks

[@taruchumccullough9045]

Hi so those super-scripts next to the node represent the height of the sub tree right? When you say children on the left or right you mean “generations” right ?

[@georgevasiliadis4228]

who cares about the trees that dude is writing like backwards, teach me that instead

[@HappyLeoul]

lol, I was thinking the same, but he is probably writing normally, then the video is flipped :)

[@cy9987]

I think maybe there is a mirror somewhere lolz

[@YellerMetal]

Just look at the nike symbol on his shirt. It looks like he is writing with his left, but it's actually his right. The picture is simply flipped

[@definty]

No he is writting so he can see it. He then mirros the image in a video editing package.

[@jokkerBANG]

give ariel a job at google

[@rymertymer3766]

Would it be wrong if we balance the tree even if the height is less than or equal to 1. It might not be useful but would it be wrong?

[@ronzano774]

Thanks. Great explantaion!

[@blingbam404]

The second example is wrong unless there are multiple ways of balancing an AVL tree--it's suppose to be a right-left rotation (not a left right rotation)

[@feliperuiz1624]

exercise 3 can be resolved with right-rotation(10) and left-rotation(4) ?

[@norueljayvillas5780]

hello sir, does Red Black Trees and AVL Trees have different rotation method?

[@TheGugustar]

Wait! He doesn't write backwards, it's Nike logo is reversed. The video is mirrored!! A legend has fallen...

[@sabetaytoros4123]

Hi, I've a problem with creating a Balanced AVL tree . In the following there is a sequence to create. The issue is I can not create a Balanced tree with a difference of 1. If you try to rotate the nodes in my understanding I am entering to an endless loop. I'l appreciate very much if someone can explain me on how to create from this sequence a balance tree.

[@sabetaytoros4123]

Sorry here is the sequence. Thanks vector v = { 43, 18, 22, 21, 9, 6, 8, 27, 4, 2, 13, 7, 10, 16, 3, 15, 1, 11 };

[@楊宗儒-i7o]

it's cool. How to write on a blackboard like through a glass?

[@DevinSamarin]

Looks like he is writing on the glass and the video is flipped so that it doesn't appear backwards. Note the flipped image of the Nike logo on his shirt!

[@jiashuotong6922]

His left hand is actually his right hand.

[@vikrambhavsar3558]

@@DevinSamarin mate you smart, i didn't notice that. Anyways I wish you a good day sir.

[@rjfloat767]

Well explained!!

[@underratedsupremehuman6311]

What Hank would've looked like if he hadn't become a police officer and decided to be a college professor.

[@thrakiamaria]

there is a mistake in 3:09 the number is 8 not 6

[@zbynekjuros5139]

Look closer its 8

[@thrakiamaria]

@@zbynekjuros5139 the left child in the left rotation must be 8, not 6. But it doesn't change anything.

[@zbynekjuros5139]

​@@thrakiamaria so one more time? Its 8. Zoom in.

[@adityamehta2819]

Are you sure its definitely a 8? it looks like a 6

[@thrakiamaria]

@@adityamehta2819 it looks like 6, I zoomed in, except if you have 4k screen.

[@AmirHamedZakeri]

That is not called two children on the left and one on the right, each node has a maximum of 2 children! You should say the height of the left subtree is two and the height of the right subtree is one.

[@ljkazuasd8605]

do you mirrow writing? how is it possible that I can write the letters on the glass XD

[@miladgholamhosseini3982]

Does anyone have an idea where and how he is writing? It's definitely not glass! Is he using a software?!

[@mojtabaheidari3170]

perfect Explanation

[@xPatata]

wait, are you writing backwards?

[@icosmini]

Does he have an audience?

[@FrankieG_Youtube]

first example, from where did you get 6?

[@faizan1041]

That's 8, either it looks like 6 or he wrote it by mistake.

[@icosmini]

Yes, he made a mistake.

[@paulvaldivia8995]

r you writing backwards?

[@curias7]

@5:45 4 children at the right of 4? right?

[@tohoangkhoi2491]

At first, I thought that he used Bunshin no Jutsu.

[@travenishere6063]

Nice visuals, but you lost me when you did the left right rotation, that's why in the end the vid, as nice it may looks, doesn't really help me...

[@comcfi]

Why does his Nike shirt backward

[@winstonacousticstudio445]

he should have said 'max subtree height' instead of 'child'

[@nazimelhadi4700]

at first i was like whaaaat this guy write backward then i got it

[@haiphan9181]

This dude looks like how the villain from Riddick moves

[@vladimirarevshatyan4622]

horrible...not explained why the 10 is the one violatiing, how you decide the rotation? how you decide ll rotation vs l rotation? horrible.

[@user-fy4iq6if4z]

writing backwards??? yo...

[@curias7]

thanos: perfectly balanced :D

[@xushenxin]

you write 8 like a 6