Lecture 10: Red-black Trees, Rotations, Insertions, Deletions

author: Erik Demaine, Center for Future Civic Media, Massachusetts Institute of Technology, MIT
recorded by: Massachusetts Institute of Technology, MIT
published: Feb. 10, 2009,   recorded: October 2005,   views: 151885
released under terms of: Creative Commons Attribution Non-Commercial Share Alike (CC-BY-NC-SA)


Related Open Educational Resources

Related content

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
Lecture popularity: You need to login to cast your vote.


"Good morning. It looks like 9:30 is getting earlier and earlier for everyone. Hello to all the people watching at home. I think there should be a requirement that if you're watching the video, you can only watch it 9:30-11:00 on Sunday, or at least start watching then just so you can all feel our mornings. Today, we're going to talk about balanced search trees. Now, we've hinted at this for a while. Our goal today is to get a search tree data structure, so we can insert, delete, and search all at log n time for operations. So, we want a tree that's guaranteed to be log n in height. So, that's a balanced search tree data structure..."

See Also:

Download slides icon Download slides: mit6046jf05_demaine_lec10_01.pdf (317.0 KB)

Download Video - generic video source Download mit6046jf05_demaine_lec10_01.m4v (Video - generic video source 174.7 MB)

Download Video - generic video source Download mit6046jf05_demaine_lec10_01.rm (Video - generic video source 134.1 MB)

Download Video Download mit6046jf05_demaine_lec10_01.flv (Video 232.3 MB)

Download Video Download mit6046jf05_demaine_lec10_01_320x240_h264.mp4 (Video 249.5 MB)

Download Video Download mit6046jf05_demaine_lec10_01.wmv (Video 741.7 MB)

Download audio transcript Download mit6046jf05_demaine_lec10_01.mp3 (Audio lecture 19.4 MB)

Help icon Streaming Video Help

Link this page

Would you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !

Reviews and comments:

Comment1 naman sood, December 5, 2010 at 12:43 p.m.:

i just love the way RB tree is taught.I m a student of computer science engg. and i would love to attend such lectures live.
this is the way learning can be made so easy and simple.
and i would love to be in contact for further problems and topics

Comment2 Student at Charles University in Prague, February 2, 2011 at 7:02 p.m.:

Hello everyone,

very, very interesting lecture. But above all, it is given in a such an understandable way that I just could not resist to say "Thank you, MIT!" :)

I wish our lecturers were teaching like this as well... We have some (like, two - three of them) who are capable of such a teaching, but the others seem to just "do the dirty job". They do not try at all to make it interesting, easy to understand... They completely disregard how intelligible it is to their audience.

Comment3 kiran kumar, March 20, 2011 at 9:25 p.m.:

This is very very effective way to learn data structures.I love the way it is taught.I wish even indian universities should adopt this.

Comment4 Ohad Perets, May 10, 2011 at 5:16 p.m.:

Hello I'm Ohad Perets software engineering student from Israel in Tel Aviv
I just want to say that the lecture really clear and excellent.
Well done Keep it up.
I was helped a lot in my writing seminar.

Comment5 Ozgur, June 13, 2011 at 1:18 p.m.:

ProgrammingPages.net - http://www.programmingpages.net
Best Programming Resources and Source Code Examples for Java, Php, Visual Basic, C++ ,Asp, Python, Javascript, Ada, Cobol ,C, C#, Delphi, Fortran, Logo, Ruby, Xml.
Programming E-Book, Video Tutorials, History, Algorithms and Faqs.

Comment6 pranav choudhary, July 31, 2011 at 9:31 p.m.:

I think the guy made a mistake while describing the general algorithm for RB-INSERT. For CASE 1, he does not consider the color of the parent of x (the node to be inserted); and blindly recolors x's uncle/aunt if it is RED. This should have been done only if x' parent was RED as well. And the Trick here is, if X' parent ain't RED, we don't need to do anything to maintain the RED-BLACK property.
The CLRS book gives the correct algorithm, where the while loop runs over the color (RED) of the parent of X, rather than on X itself.

Comment7 ishita jain, November 21, 2011 at 6:54 a.m.:

he seems to be a great teacher..totally cleared my head..but i waslooking for deletion in RBtress..anyone has an idea where i'll get an equally good video to understand how deletion works?!!

Comment8 Anthony Muthu, December 22, 2011 at 3:32 p.m.:

hi it is very useful for us...............

Comment9 Anthony Muthu, December 22, 2011 at 3:32 p.m.:

hi it is very useful for us...............

Comment10 islam, March 25, 2012 at 9:07 p.m.:

Great !

Comment11 RATAN KUMAR, April 12, 2012 at 6:27 p.m.:

i got this lectures very useful !! got wat exactly a RBT is , thanks to MIT

Comment12 at 10:30, June 11, 2012 at 7:57 p.m.:

@10:30 - he draws node X which descends in 4 paths to bottom but a node points to only two sub-nodes (left, right). That can't be right. It should look like a tree imho:
/ \
y z
/ \ / \
a o e u
^ ^ ^ ^

Comment13 Nimmy K, October 29, 2012 at 11:19 a.m.:

Thank you! This indeed a big help!

Comment14 neel, January 1, 2013 at 8:12 a.m.:


Comment15 nath nathaniel, November 13, 2013 at 8:01 p.m.:

I enjoy your lectures alot, especially the Manner of presentation. I sincerely learn a lot from them. more grease to your elbows.

Comment16 mahesh, April 14, 2014 at 11:38 a.m.:


RBT Node Inserting - doc let link is shared here.


Comment17 Ashish, August 18, 2014 at 8:07 p.m.:

AS I understand, RB tree is balanced. When I say, I understand it to be height balanced. The tree example that is being worked out is not balanced.

Comment18 Pardeep, January 16, 2015 at 10:24 p.m.:

just Awesome! Today I understand the RB trees

Write your own review or comment:

make sure you have javascript enabled or clear this field: