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

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

@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.
Hassam Sheikh
He Looks Like Sheldon Cooper
bachir masry
If we could listen to the students remarks and questions, that would make this video in my opinion mush more beneficial.
Wasif Altaf
At 46.00 is a left rotate, not a right rotate
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)
shrikant sarma
Damn good prof. ... Need more videos from him !
Thanks a lot! Way better then my prof in germany... Amazing how much better motivated ppl. can teach stuff! Keep up the good work!
Upvote if you have a mancrush on Demaine.
Shiva Kumar Reddy Suram
i'm very impressed by the way u taught :)
He gave the cushion because she was pretty . Otherwise the answer was Okay. An example of subconscious bias.
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.
Nikhil Kumar
Thanks a lot professor for solving my doubt of AVL Tree and also thanks to MIT
Ł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!
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.
@44:57 its called a left rotate of x. Not right rotate. He goofed up.
I love this guys, so enthusiastic about what he's teaching!
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.
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!
Jinal Thakkar
@27:33 he said N(h-2) = 2^(h/2). can someone please explain how ??
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.
Raghav Rao
@ 30:00
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
Adam Rosenberg
he also blows glass. like a badass
klingt net
Errata: 44:57 should be LR(x)
Scott Wells
@31:30 "now all the heights change... and it's annoying to draw what the heights are... but... I'll do it"
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.
cihangir '
nice one
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
are the hard seats made on purpouse? lol
здравствуйте, объясните пожалуйста, как этот бизнес растает.
Keshav Sharma
Beautifully explained
This teacher is awesome
avl insert 29:40
I'm a Maths student from Italy and my exam is tomorrow! thank you so much for sharing these!! they're so useful!!
Minks Q
Those tree nodes are so cute
Great lecture! Really helped to understand AVL trees for my exam
whats with the cushions
Anthony Nguyen
at 1:20 since when does a binary search tree alow a dublicates?
Great lecture, thank you very much!
Caio Novaes
Very good lecture, congratulations and thank you very much! =)
Charles Li
Tree rotation is magic.
Very strong lecture! Clearly understandable and Smooth
Ho Thai
thanks MIT & professor for this video
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.
Are you serious?
ze a
I love this prof
amr abdulaziz
thank you
Praveen Marandi
:-D really helpful !!!
thank you..
if node height = max height of the left + max height of the right + 1 shouldn't the root of the tree at 9:35 = 4 and not 3?
Thong Nguyen
BST has not a same Node...X-node can't equal X-Root in this case
He really loves that board
Heather Rojas
For god sakes man that is enough. Do you want my head to explode lmao.
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?
Christian Campos
good catch haha
rishi pariyani
At @46:00 How come the height of A is k-3 and not k-2??
Anmol Deep
40:23 - Watch from this part next time
he's very good!
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?
Robin Pankaj Gupta
Inspired me to write more programs on Trees. Visit robinfromsps.com for more ...
Anthony Penner
best part 32:50
Karan Kashyap
good Morning
no if you look at the maximum height of the children it is 2(maximum) since the last node has a height of 0. ok?
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
What is the lecturer throwing to the students?
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?
Gergely Bod
great teacher
Jeevan B Manoj
At 44:58 shouldn't it be left rotate of x insyead of right?
not a great lecture
saisowmya bavirisetty
i did't get any clarity from this lecture
AkShay Mahajan
Thanks a lot Sir.
arshdeep kapoor
If I want to insert a value of equal to node... will it be inserted on left leaf or right?
so comfy vidjeo
Will Sirius
Why u didn't talk about delete
jason dads
he goes through one large piece of chalk
jason dads
Wow MIT lecturers are good
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.
Windows Logo
33:00 mind blown inc
Himanshu Chowdhury
Worst video on rotations.
Drew Verlee
Thanks now i feel terrible.
Arlind Hajredinaj
Rudy Magasrevy
this guy is a magician with chalk
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!
Quang Tran
Why in the lecture note on page 6 the running time for findmin of AVL tree is constant?
Sourabh Goswami
man if you watch this video at speed 1.5 it seems like the instructor is dancing
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.
Arlind Hajredinaj
cushions, everytime they get a right answer they get a cushion because the seats they sit on are hard seats.
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?
Zhang He
It is a enjoyment to watch Erik's lecture! Greetings from Dalhousie!
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.
Saad Taame
@4:45 when writing the inset operation Erik got the direction wrong. It's a left rotation
hello anyone to sugegst me book with solved exercises in recutions??i be grateful for that help!!thanks
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 
Arlind Hajredinaj
lol i guess so
"Life is good."
I thought that was the actor from the facebook movie at first. His voice is identical.
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.