AVL Trees Simply Explained

[@maanethdesilva]

At 2:21, I have bf=br-bl but I meant to say bl-br. Even though I wrote the formula wrong, you can see that all my calculations are bl-br. Sorry for the confusion!!

[@AnnisaSofea]

great video, ur a great teacher, thanks alot for your time and effort in making this

[@codiaji]

I guess u meant: bf=hl-hr

[@ireneloli4075]

almost half of videos for avl trees, are like "RL LRrrlrllrllr right left bla bla"... This one is the best. It is simple and straightforward. Thank you.

[@maanethdesilva]

Glad you liked it!

[@smartiee]

Bro is the definition of a Chill Guy

[@Shadow-cf7qd]

Your poised and calm explanation style really helps a lot while learning!! Great video!

[@maanethdesilva]

Thank you! I'm glad it helped!

[@user-cx5wq9rn6e]

bro is chill af

[@Penguinus-cv6mz]

At first I had no idea what i was looking at in class. But now i fully grasp the concept awesome job i appreciate the knowledge share!!!

[@jalenmcdonald758]

This is probably one of the most helpful videos I have ever watched. I struggled with diagramming these rotations for hours. I have a final on Friday and you just saved me!

[@ewazmi9114]

how did the final go then?

[@yusuftarik]

I have data structures makeup exam tomorrow and I believe that I can easily solve any AVL questions after this video, thanks to you :')

[@maanethdesilva]

Best of luck!

[@yusuftarik]

@@maanethdesilva I PASSED THE EXAM!!! THANK YOU SO MUCH!

[@maanethdesilva8035]

@@yusuftarikThat's awesome congrats!! 🎉

[@bobow4075]

Crazy how good you were at explaining this concept

[@socksforfrogs]

You explained this so much better than both my instructor and my textbook. Really good video and super helpful!!!!

[@maanethdesilva]

Thank you!! Glad it was helpful!

[@eliaaqu9375]

This is great, I love the soft music in the background!! It really helps with exam’s stress & great and straight forward explanation!

[@maanethdesilva]

Thanks so much! Good luck on your exam!

[@mridulbhattacharjee1866]

Bro, thank you so much! This video needs much more appreciation! This is the best AVL video so far I watched in 10 minutes

[@notnominal7013]

Excellent video for explaining AVL trees in a quick and straightforward way! Only thing I would change in an updated version would be some more streamlined graphics/animations, and a new voiceover for the bf=h_L -h_R so as to not get anyone confused. Also, a quick explanation of why "Left-Right" and "Right-Left" rotations are called what they are would be nice. When we perform a "Left-Right" rotation on a node, it seems we are actually doing a right rotation on it's child, THEN a left rotation. Seems to be a bit of a misnomer in that way.

[@fr18zq]

im pretty sure he just mixed the names up entirely

[@Onestepclosertodeen]

The best and simplest video on avl

[@mokshgujar375]

Explained Really Well Bro, my University Teacher Didn't Explained AVL Tree This Well!!!,I'm Having Exam Tommorow of Data Structures, Thanks Man!!!

[@maanethdesilva]

Thank you so much man! Good luck on your exam tomorrow!

[@mmaruft]

thank you very much, I was struggling for the type of tree at 9:58, I understood very well when you explained with negative/positive signs of the balance factor!

[@grizzthekid]

got a test in like 30 min, I know it sounds impossible. But this was fully explained. Will let you know how it goes🔥

[@grizzthekid]

Update, wrote the test. With theory I aced it won’t lie. But never got to have time for practicals. But in all great video. Fully explains the concept. Thank you

[@maanethdesilva]

Glad to hear you aced the theory! Let me know if there are any topics you'd like me to cover. Hopefully you'll have more time to learn it haha!

[@adityasamal3720]

@@maanethdesilva dude you're a god

[@princess_kedi]

I've been trying to udnerstand this for hours. you explained so well and I instantly grasped it and I love the style of the video. the music is helpful for me :D thanks so much. very helpful for my incoming exams please film more CS videos

[@princess_kedi]

please make videos about writing pseudocodes of inverting/deleting numbers into trees.

[@InsaneFire10YT]

taught so much better than my CS1 professor, well done sir!

[@fleontrotsky]

I must admit. I leatned thid in University. But never went on to work in Comp Sci. 28 years later ive been looking for a video to simply remind me the logic of rotations. Only 6 mins in an its all come flooded back. Now. I have to just go and implement it in C and i will be a hapoy man.

[@zenmikey]

Great conceptual explanation. One thing, at around 2:47 the formula is right height minus left height, but the rest of the video seems to flip that order. Am I being dyslexic?

[@WrongNicholas]

best video I have seen on avl rotations! you're helping me ace my quiz thanks man

[@maanethdesilva]

Glad it helped!

[@lincolnbethinkin5331]

super high quality video! helped so much for my data structures final I am studying for

[@rodriguez.anteTee]

I really enjoyed this video, easy to follow and shows the basic well.

[@FaizKhan-ft8lu]

bro you make it so much easier to understand

[@teha1306]

i understand this topic much better now. thank you!!

[@timbansemer7272]

Question: at 6:55 you wrote LR rotation on the arrow. Isn’t that wrong? You explained it to be a RL rotation before.

[@maanethdesilva]

A LR rotation happens when you first do a left rotation then a right one. At first, we rotate it left on the pivot 9 and bring 9 left and down and 19 left and up. Then we do a right rotation on the pivot 19 and make 63 a right subtree of 19. That's why it is a LR (Left right) rotation. Hope this helps!

[@ThaboJaphta]

thanks a lot man you just made this crystal clear

[@winter_moon_11]

11:00 fir the balance factor of node 2; how is it -2? it has children on left side bf = hl - hr ; bf = 2-0 = +2 not -2 i think

[@maanethdesilva]

Yes you're right! Sorry for the mistake and thank you for pointing it out!

[@panchalrushang5869]

Really appreciate your efforts man!! Very well explained 👍

[@skullz9366]

10:27 how come the '4' has a sign of -1 shouldn't it be 0 ? as the left height is 2 and right height is also 2 so therefore '4' is zero?

[@ayushrane5606]

Very helpful, loved it bro

[@nickwerner436]

Perfect explanation!

[@jacobreil9661]

Amazing vid man. Got Data Structures II tomorrow and this really helped

[@maanethdesilva]

Thank you! Good luck on your exam!!

[@mikealTuan]

1:36 Are you saying the external nodes have rank 0?

[@skyblock127]

Didn't get why did u not change the value for the element "2" at 9:17. I mean height of right branch and left branch for 2 is 3 and 1 respectively, so why did u not change its value to -2?? Is it because we traverse bottom to up?? So first the 3-4-5 values will be optimised, then we move above??

[@welovemusic6844]

Literally The best❤ tysm

[@moppnitz]

@7:58 why was the root 19 still -1 .. should it have been -2?

[@maanethdesilva]

It would still be -1 because the right subtree increased height by 1, the left tree height is 2 and the right tree height is 3, so that's how we get -1

[@winter_moon_11]

7:56 how 19 balance factor is -1 after inserting 99? there are 2 left children of 19 (9 and 18) and on the right it has 4 (63, 27, 108, 99) so it is 2 - 4 = -2? how did it become -1?

[@maanethdesilva]

hl and hr are both calculated by the heights of the subtrees not how many nodes there are. On the left there are 2 children and the height is also 2. On the right, there are 4 children but the height is 3 because 2 of the nodes belong to the same parent. So hl=2 and hr=3, hl-hr = 2-3 = -1. Hope this helps!

[@thephelps]

great video, easy to follow!

[@azkanisar8274]

Thank you for making this video !!!

[@shivampandyajani]

Amazing man! can't thank you enough!

[@ojassingh4795]

Amazing explanation!!

[@bluetiger1372]

Great video, thank you!

[@alexander123987]

I notice some people saying the balancing factor is (h_L - h_R). Is this an error?

[@YousefAl_shikhAli]

you are GREAT bro , I really Hope You are Happy 🤝

[@ltsCoo]

How would I balance this avl tree? You dont give an equivalent example, if I followed steps at 10:07 it would still be unbalanced 30 / \ 25 40 / \ 35 45 / 34

[@ZettaiKatsu2013]

you need to do a trinode restructure in that case. A regular rotation will not fix the unbalance here. The relation between 30, 40 and 35 is your trinode. 35 needs to be at the top of the 30,40. 30 on left. 35 on right.

[@maanethdesilva]

You can test out your understanding with this visualizer www.cs.usfca.edu/~galles/visualization/AVLtree.html

[@matyaskrejci1259]

9:20 is that really right rotation?

[@AbhijithPai]

4:36 should be right left rotation, and not left right rotation, can someone confirm?

[@sahar.2316]

yes

[@lailajewett5327]

in the deletion portion, why is the 2nd to last unbalanced tree, why does 2 have a balance factor of -2 instead of a positive 2 since it's on the left side?

[@ribbitorbit]

Thanks for the video! Really helps me understand AVL Rotations! (I was struggling TT) Can you cover Red Black Trees next?

[@maanethdesilva]

For sure! I'll make a video on that as soon as I can!

[@BussLxn]

hey, im new here but i saw the first double rotation I think it should be "right-left rotation" and not "left-right rotation" IDK. if someone knows pls lmk ty!

[@minaungmyat1624]

2:07 Why you write height in red first then when you try to determine BF, you wrote the height in blue and automatically minus 1 and said not to be confusing.

[@deadvision22]

you are the god of avl tree

[@brightonsikarskie8372]

goated vid, thanks bro

[@andrewmcburney4425]

Great explanation!! Thank you

[@yerbolatuzakbay6895]

9:22 isn't it a left rotation?

[@maanethdesilva]

Yes! Sorry for the confusion

[@Berkmnn]

Wow this video just saved me

[@aihsdiaushfiuhidnva]

this is amazing, very good sir.

[@sriramsujith4918]

Music is so soothing Can I get music link or name

[@sayandeepsoren361]

Amazing explanation

[@nifemiipaye7700]

loved it. Made me understand it better :)

[@maanethdesilva]

Glad you liked it!

[@LaraPierre-n8b]

you ate with this i fear thank you

[@dragoneye5385]

Why the bounce factor for 63 is +2 ?

[@maanethdesilva]

The left subtree has a height of 2 and there is no right subtree meaning that the height on the right is 0, so given that the balance factor is Height_l - Height_r, 2-0=0. Hope this helps!

[@yukon_2]

at 7:45 after adding 99, wouldn't the tree be more balanced if 27 was the root? then the left and right subtrees would each have three elements, and the max height of the tree would be 3, instead of 4.

[@maanethdesilva]

There's always only one spot you can insert a node in a tree and it's by looking at the nodes as you traverse down and going right if the new value is bigger or going left otherwise. Since 99 is greater than 63, it'll go to the right of that, so it can't go to 27 which is on the left of 63.

[@mateogerard146]

chillest mf on the internet, love your content boy!

[@jonathanlicurse6987]

I thought that the height of an AVL tree was the number of edges on the longest path from that node to a leaf node?

[@maanethdesilva]

That definition also works

[@kimmo2222]

You explained well but this video was full of mistakes. At 4:02 you have left child and you said left child is empty ! I am very confused! please make some effort to revisit and fix the mistakes. thanks

[@sg_umerrabbani6852]

really good vid keep it up bro

[@henryangeliiibacurnay2882]

What app and device you are using in this video to write?

[@maanethdesilva]

The app is called Goodnotes and I'm using an iPad Pro.

[@its_shmul]

I noticed that the height of a node can be different, counting bottom to top from the left and right sides, is it just me? What am I not seeing?

[@maanethdesilva]

The height in a tree is the longest path it takes to get to a child node, so even if the left and right sides have different values we take the maximum one. Hope this helps!

[@guesswhothis]

Saved me, tqsm

[@Hussein....]

Thanks a lot ❤

[@Daemont_JP]

I still don't get it

[@konstantinkozokar7587]

Great vid, one thing to improve - audio, it is echoish, next time process it with some filter. Anyway, thx, simple and str8 forward

[@JKRProductions2022]

My professor uses right - left for Bf, just as long as you keep track of which should be - and which + it doesn't matter.

[@jonathanh.5358]

What application is that?

[@hooohooo283]

Goodnotes

[@teckSik]

Amazing!

[@PulsingPiano]

ur the goat my g

[@rmrmrm258]

great video

[@syntrofosflash]

You're the best

[@aymenfadily1773]

Name of the application . I like it !

[@gabriel-oc4pt]

Thank you bro!!!

[@thanhnguyenchi2356]

thank you mister

[@kvelez]

Good one.

[@moredom]

thank you bro good video

[@chrisedgett6280]

Theres a ticking sound, like the hand of a clock, playing in the background of your video. Thought you should know.

[@bryanbeltran5983]

seems like it should be clear from the explanation... but the balance factor explanation feels rushed. how are you getting those numbers from Height of Left - Height of Right?

[@maanethdesilva]

If you think of nodes as parents and children, height is the number of generations. For example, one node has a height of 1, a child and parent node has a height of 2, and so on. Your height of a subtree would be: starting from the top of that subtree, how many generations are under you. Note, if a parent node has 2 children one left one right, the height is still 2 because there's 2 generations, until one of the children has another child then it'll be 3.

[@dolmondboi]

I think this video could do a better job explaining how assigning heights to the sub-trees works. I am having a lot of trouble doing that for some reason. Maybe it's just me.

[@dolmondboi]

Still miles better than my professor's explanation

[@maanethdesilva]

I have some resources in the description where they talk about assigning heights to the tree and the pseudocode. Hope that helps out!

[@AndrewAddae]

The course is interesting

[@Tofusky]

thank you for explaining about left-right and right-left rotation, my code doesn't work because of this.

[@samly3299]

I think you might have mixed up the LR and RL rotations.

[@kazianwar]

Splay trees next please!

[@isaacdeane799]

Nice video but you were constantly messing up the balance factors, doing LH - RH instead of RH - LH

[@maanethdesilva]

Sorry for the confusion, it should be LH-RH, check 2:30. Regardless, if you consistently do RH-LH it'll be fine too. The type of rotation depends on the parent and child node having the same sign or opposite sign. Hope this helps!

[@louishauger3057]

Thanks

[@parker7721]

pretty sure you explain right-left rotation on the left-right explanation

[@leduy5735]

cảm ơn kiến thức

[@ejsafara456]

very nice vid ^^ just the music is a lil too loud

[@maanethdesilva]

Thanks for the feedback! I'll reduce it a bit for my next videos.

[@Baannoanjum]

Excellent explanation of concept i understand very little from your voice because it too fast 😂

[@9s466]

So helpful and bro charging his shit