6. AVL Trees, AVL Sort

Download videos:
hd720 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

@45:00- it should be LeftRotate(x), not Right
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.
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.
bachir masry
If we could listen to the students remarks and questions, that would make this video in my opinion mush more beneficial.
@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.
Santos Santander
This guy is a terrible teacher. I like the Indian teacher better... This guy gets too fanatical about the algebra!!
shrikant sarma
Damn good prof. ... Need more videos from him !
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)
Scott Wells
@31:30 "now all the heights change... and it's annoying to draw what the heights are... but... I'll do it"
Wasif Altaf
At 46.00 is a left rotate, not a right rotate
Upvote if you have a mancrush on Demaine.
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.
Gergely Bod
37:53 Zig-Zag path - Youtube share button's icon
Thanks a lot! Way better then my prof in germany... Amazing how much better motivated ppl. can teach stuff! Keep up the good work!
I love this guys, so enthusiastic about what he's teaching!
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!
c.daniel Premkumar
What does AVL stand for ?
Shiva Kumar Reddy Suram
i'm very impressed by the way u taught :)
klingt net
Errata: 44:57 should be LR(x)
Raghav Rao
@ 30:00
He gave the cushion because she was pretty . Otherwise the answer was Okay. An example of subconscious bias.
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.
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...
Manveer Singh
39:59 ahaan .. smart!
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!
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
Jinal Thakkar
@27:33 he said N(h-2) = 2^(h/2). can someone please explain how ??
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.
Arash Jamshidi
I love how the professor is kinda dancing while cleaning the board @ 26:05
Fredo Corleone
I get lost... This guy is too advance.
kalapala rahul
how to check if the node is even, left heavy or right heavy???????????????
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.
Rachit Mathur
Earlier i was sad :( now m happy :) thanks Erik
maru aq
this man ruleeess
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?
Suraj Shaw
How come N suffix (h-1) + N suffix (h-2) got converted into 2*N suffix (h-2) ? Timestamp : 28:31
anne sanila
and the ticked ?
He really loves that board
Christian Campos
good catch haha
Windows Logo
33:00 mind blown inc
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.
jason dads
Wow MIT lecturers are good
Jeevan B Manoj
At 44:58 shouldn't it be left rotate of x insyead of right?
Quang Tran
Why in the lecture note on page 6 the running time for findmin of AVL tree is constant?
Suraj Shaw
Erik's explanations are great! Thanks to MIT.
Anmol Deep
40:23 - Watch from this part next time
Yuyang Tu
I have a same t-shirt
jason dads
he goes through one large piece of chalk
Udit schoolboy
Does anybody know what text book is being talked about at @6:00?
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
whats with the cushions
Nesae Mouzehkesh
@37:35 why 65 is doubly left heavy? It is not...
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?
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!
thank you..
amr abdulaziz
thank you
Gergely Bod
great teacher
Praveen Marandi
:-D really helpful !!!
so comfy vidjeo
Great lecture! Really helped to understand AVL trees for my exam
Harrington Luke
I love this prof
здравствуйте, объясните пожалуйста, как этот бизнес растает.
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 
Ho Thai
thanks MIT & professor for this video
"Life is good."
Zhang He
It is a enjoyment to watch Erik's lecture! Greetings from Dalhousie!
Thong Nguyen
BST has not a same Node...X-node can't equal X-Root in this case
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.
cihangir mercan
nice one
hello anyone to sugegst me book with solved exercises in recutions??i be grateful for that help!!thanks
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?
at 1:20 since when does a binary search tree alow a dublicates?
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.
I'm a Maths student from Italy and my exam is tomorrow! thank you so much for sharing these!! they're so useful!!
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.
avl insert 29:40
Charles Li
Tree rotation is magic.
I thought that was the actor from the facebook movie at first. His voice is identical.
Minks Q
Those tree nodes are so cute
s S
Why u didn't talk about delete
Karan Kashyap
good Morning
Keshav Sharma
Beautifully explained
AkShay Mahajan
Thanks a lot Sir.
Sourabh Goswami
man if you watch this video at speed 1.5 it seems like the instructor is dancing
Ahmet Cevahir ÇINAR
rishi pariyani
At @46:00 How come the height of A is k-3 and not k-2??
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
Anand Iyer
Great tutorial. But whoever subtitled it must be a retard. Best case : business.....??
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
Are you serious?
Very strong lecture! Clearly understandable and Smooth