6. AVL Trees, AVL Sort


Download videos:
medium

MIT 6.006 Introduction to Algorithms, Fall 2011 View the complete course: />Instructor: Erik Demaine License: Creative Commons BY-NC-SA More information at />More courses at



Tags:
AVL tree rotation insert abstract data type data structure balanced binary search tree balanced BST



DaxXx988
@45:00- it should be LeftRotate(x), not Right
Kaze No Hito
Oh my god I wish my instructor was like this. I swear my csc instructor just pulled rotations out of his mitochondria and did not explain a lick of how they work.
Akarsh Rastogi
Somewhere in India, I mention to my mom, do you know who this guy is? He's a prodigy, now he teaches at MIT and I can't wait to watch each of his lectures, here on my laptop. Thank you MIT, Eric, the Internet and Computer Science in general for existing and making all of this possible.
bachir masry
If we could listen to the students remarks and questions, that would make this video in my opinion mush more beneficial.
CEngineer2010
@44:57 its called a left rotate of x. Not right rotate. He goofed up.
Jason Heo
Is Erik out there? or could someone help me? I have a question. At 45:20, RR(x) should be changed to LR(x) or RR(y)? it violates 35:21 Thanks.
Scott Wells
@31:30 "now all the heights change... and it's annoying to draw what the heights are... but... I'll do it"
shrikant sarma
Damn good prof. ... Need more videos from him !
Wasif Altaf
At 46.00 is a left rotate, not a right rotate
gosumadman
Can someone explain 26:09?I don't get why he changed N(h-1) to N(h-2) and removed the 1. Also I don't get how 2N(h-2) = (2^(h/2)
rsjrx
Upvote if you have a mancrush on Demaine.
codewing
Thanks a lot! Way better then my prof in germany... Amazing how much better motivated ppl. can teach stuff! Keep up the good work!
Eric Belrose
Why didn't he start with a balanced tree.  Is it not true that before he inserted the 23 the tree was already off balance.  The tree was left heavy. I am still just starting the study of this structure, but it would seem that the tree would have to left rotate at 20 so 29 becomes it's parent and 26 joins it.  Then the left subchild of the left subtree is heavy so it would right rotate so 29 becomes the head.  Maybe it is because he knew he was going to add the 55 and didn't care that he didn't start balanced. If he did that rotation first the tree would be a perfect tree after adding the 55. Perhaps I'm confused.  It would seem that you could improve the algorithm simply by looking beyond the max{HR,HL}.  Could you not calculate optimal tree height for N and if max height after walking down to insert in the BST fashion is worse, then start rotations on the max height side. First step towards that side being heaviest in that side (left heavy where left is the issue/right heavy where right is the issue), then balance the head node by rotating away from the heaviness. Is there another name for that tree balancing algorithm.
Richie Rich
Has Red Black Trees been removed from the course syllabus. In the Fall 2005 course there is a video on RBT but in this course there is one on AVL.
klingt net
Errata: 44:57 should be LR(x)
Shiva Kumar Reddy Suram
i'm very impressed by the way u taught :)
AJ
It blows my mind that people can essentially get a free MIT education from these lectures. Thanks for all the CS lectures & the rest of the online courses! I look forward to absorbing as much knowledge as I can from them!
TheEvil
He gave the cushion because she was pretty . Otherwise the answer was Okay. An example of subconscious bias.
Nikhil Kumar
Thanks a lot professor for solving my doubt of AVL Tree and also thanks to MIT
Hassam Sheikh
He Looks Like Sheldon Cooper
Łukasz Piątkowski
At 45:00 isn't it LEFT ROTATION of X instead of RIGHT ROTATION of X? UPDATE: Already pointed out by DaxXx988 in the comments below. Thanks!
shady1080
I love this guys, so enthusiastic about what he's teaching!
Raghav Rao
@ 30:00
nbafanboi23
I can tell that the students are pretty smart, just comparing it to my class at University of Waterloo. Although I can't tell if its the same students answering the question. I know that I would be clueless for half these questions.
Manveer Singh
39:59 ahaan .. smart!
Jinal Thakkar
@27:33 he said N(h-2) = 2^(h/2). can someone please explain how ??
SeiNj
40:47 - not sure it's correct that "we might have to do more than 2 rotations" after a violation fix, the tree should become re-balanced again
Modern Gandhi
How come N suffix (h-1) + N suffix (h-2) got converted into 2*N suffix (h-2) ? Timestamp : 28:31
Modern Gandhi
Erik's explanations are great! Thanks to MIT.
maru aq
this man ruleeess
Wei Shi
At 46:55, and was noted at another point earlier that there may be an imbalance in the higher levels of a tree if an imbalanced node is balanced at a lower level of the tree. Is that really true in a properly coded AVL tree? A properly coded AVL tree is balanced at the moment of insertion. After insertion, node X is imbalanced because of, let's say, right-heavy right subtree Y. After rotation(s), Y is now at the previous location of X, and Y has the same height as X before the insertion. This is because Y's height increased by 1 as a result of insertion, and now has the same height as X before insertion. Moving Y to replace X in the rotation means the height at the NODE OF ROTATION does not change. Therefore, the only way that there could be further imbalance up the tree is if the tree was already imbalanced before insertion.
Overwhelming Sarcasm
He sometimes switches between 'depth' and 'height', but the depth or level of a node is it's distance going down from the root, right? Also I've seen different ideas about whether the root of a tree is at level/depth 0 or - 1. Is there a widely accepted consensus on which should be used or is it just a matter of consistency with the formula/algorithm in the same way that null nodes were defined to have height - 1 here? The notation and terminology around this topic is a tad confusing...
Hieu Luong
The more important thing should be mentioned here is how AVL applied in the real problems, and why we choose AVL to solve? The implementation is just after that. I never learn a thing that I don't know how important it is.
Quang Tran
Why in the lecture note on page 6 the running time for findmin of AVL tree is constant?
Jeevan B Manoj
At 44:58 shouldn't it be left rotate of x insyead of right?
Bakyt Niyazbekov
Can anybody give an example when you need more than two rotations? After one or two rotations height of an unbalanced subtree remains the same it was before insertion, doesn't it? So I don't understand why we might need more than two rotations.
Anant Garg
@34:55, I don't understand how he checked formally. "B contains all the nodes between x and y" -what does this mean? Could someone please help me?
Yuyang Tu
I have a same t-shirt
Nesae Mouzehkesh
@37:35 why 65 is doubly left heavy? It is not...
jason dads
he goes through one large piece of chalk
Christian Campos
good catch haha
jason dads
Wow MIT lecturers are good
Anmol Deep
40:23 - Watch from this part next time
rosasmellshaha
He really loves that board
Jazzvids
at 42:50 didn't he mean that the left sub tree is -1 and the right one is -1 and that's why it comes out -2? If it was 0 like he says then the node would be balanced
Robin Pankaj Gupta
Inspired me to write more programs on Trees. Visit robinfromsps.com for more ...
Puneet Jain
The lecture is AWESOME. but yeah, the LR thing and the heights of that tree in the question.. that isn't (h-3)... else the right child would be left heavy.. (lesser the height, lower it is..).... just my point of view.... I love these lectures :D 
Windows Logo
33:00 mind blown inc
stanleyqqq7
hello anyone to sugegst me book with solved exercises in recutions??i be grateful for that help!!thanks
Thong Nguyen
BST has not a same Node...X-node can't equal X-Root in this case
candh
whats with the cushions
Zhang He
It is a enjoyment to watch Erik's lecture! Greetings from Dalhousie!
Ho Thai
thanks MIT & professor for this video
Anna Z
@46:08, why is it k-3? The triangle is connected to the X? similarly, the B triangle is connected to Y which is k-1 and C is k-2, but B is k-3?
Snake
Great lecture! Really helped to understand AVL trees for my exam
Na P
Hey, how do we do to define which node is ''x'' oder ''y'' And in double rotation who is ''x'', ''y'' or ''z'' please? thanks!
ze a
I love this prof
Mark Walle
Dr. Demaine Seems like a great professor, and brilliant mind from what I see at erikdemaine.org. Why is he calling the internal nodes in the trees leaves @7:51? Leaves should be a term reserved for the valueless nodes of height 0 that are children of internal nodes. This way you can talk about internal nodes as all those having value, and leaves as those that are at the very bottom of a tree and don't have a value, and you can also say that you insert at leaves, instead of saying you insert at the children of leaves. Perhaps it's just semantics, but it just seems that calling the lowest internal nodes leaves is confusing.
Minks Q
Those tree nodes are so cute
BEPIK МЛМ
здравствуйте, объясните пожалуйста, как этот бизнес растает.
Akweda
at 1:20 since when does a binary search tree alow a dublicates?
Gergely Bod
great teacher
egal
I thought that was the actor from the facebook movie at first. His voice is identical.
Sourabh Goswami
man if you watch this video at speed 1.5 it seems like the instructor is dancing
ZphykTESHD
so comfy vidjeo
Praveen Marandi
:-D really helpful !!!
realeques
ive never seen someone writing like that on a chalkboard , looks funny ....and it looks like the students have no table. Is that a college ? Im from germany.
Hang Chen
@49:16, the instructor mentions the insertion time for AVL try is nlg(n), is it because we have to talk about the worst case when we are talking about insertion time? Since it seems it assumes all the insertions are going to the leaf node?
Ignisardor
I'm a Maths student from Italy and my exam is tomorrow! thank you so much for sharing these!! they're so useful!!
amr abdulaziz
thank you
Kevin Beteta
Another reason to give NULLPTR a value of negative one is that you have to move upward once to get to a genuine leaf.
nilyo
"Life is good."
Charles Li
Tree rotation is magic.
XeriToN0
thank you..
rishi pariyani
At @46:00 How come the height of A is k-3 and not k-2??
Will Sirius
Why u didn't talk about delete
Karan Kashyap
good Morning
Ashwani
avl insert 29:40
Keshav Sharma
Beautifully explained
AkShay Mahajan
Thanks a lot Sir.
cihangir mercan
nice one
Ahmet Cevahir ÇINAR
Teşekkürler.
1cy3
not a great lecture
arshdeep kapoor
If I want to insert a value of equal to node... will it be inserted on left leaf or right?
saisowmya bavirisetty
i did't get any clarity from this lecture
Himanshu Chowdhury
Worst video on rotations.
Aaron Zhao
Have a doubt about BST in this lecture, where professor writes >=x and < =x that shows nodes in left subtree are equal or less than its parent...same on another side. Isn't BST supposes to have no duplicate nodes, which means nodes in left subtree must be less than its parent not equal or less, and nodes in right subtree must be greater than its parent not equal or greater?
Saad Taame
@4:45 when writing the inset operation Erik got the direction wrong. It's a left rotation
Heather Rojas
For god sakes man that is enough. Do you want my head to explode lmao.
Arlind Hajredinaj
lol i guess so
Arlind Hajredinaj
yep
Th4w
Are you serious?
Dsl
Very strong lecture! Clearly understandable and Smooth
sachoslks
are the hard seats made on purpouse? lol
Caio Novaes
Very good lecture, congratulations and thank you very much! =)
Arlind Hajredinaj
cushions, everytime they get a right answer they get a cushion because the seats they sit on are hard seats.
Miguel Rivera
I think he may have made a mistake. He defines N(h) as the minimum number of nodes in an AVL tree of height h. In my opinion N(h) = 2^(h - 1) + 1 (I think a student suggested that but he never really elaborated on why that was wrong). As I see it, you take the perfectly balanced tree of height h - 1, and you add only 1 node to increase the height by 1.
Cnidaria
i think that 45:13 it is a left rotate not a right rotation. can someone help me pls? since he's moving the x to the left thus it is a left rotation
Jorgetime
This teacher is awesome
Anthony Nguyen
cushion