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.

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

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

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

[@fatihsonmez]

"so my tree is happy"

[@sikhokhelekhohliso4162]

Breaks down the problem properly. Love it

[@freshbreeze6180]

Thanks a bunch. The best explanation ever.

[@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 ?

[@CharlesPieczonka]

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

[@TheElof]

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

[@returnMarcco]

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

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

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

[@diegocruzalves]

Excellent explanation!

[@heikeneubau7064]

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

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

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

[@mezzamate3252]

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

[@惜小夜]

Excellent video, helped me so much. Thanks!

[@joelab.c]

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

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

[@Psztyk236]

I love your EKIN t-shirt

[@danielstevens3020]

Great explanation, thank you Rob

[@asahutchinsoniv9563]

great job explaining this! thank you

[@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)

[@matejbeno569]

Nice explanation, thank you!

[@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 ?

[@arnavsaini3410]

Awesome explanation

[@ronzano774]

Thanks. Great explantaion!

[@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?

[@matt-ex5ub]

very useful video now i understood thanks

[@definty]

2:40 you write 6 instead of 8

[@JournalistiekOnderzoek_4e]

Should be an 8

[@rjfloat767]

Well explained!!

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

[@norueljayvillas5780]

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

[@mojtabaheidari3170]

perfect Explanation

[@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?

[@TheGugustar]

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

[@miladgholamhosseini3982]

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

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

[@feliperuiz1624]

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

[@ljkazuasd8605]

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

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

[@xPatata]

wait, are you writing backwards?

[@icosmini]

Does he have an audience?

[@underratedsupremehuman6311]

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

[@paulvaldivia8995]

r you writing backwards?

[@comcfi]

Why does his Nike shirt backward

[@tohoangkhoi2491]

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

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

[@winstonacousticstudio445]

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

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

[@nazimelhadi4700]

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

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

[@haiphan9181]

This dude looks like how the villain from Riddick moves

[@curias7]

thanos: perfectly balanced :D

[@curias7]

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

[@user-fy4iq6if4z]

writing backwards??? yo...

[@xushenxin]

you write 8 like a 6