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

author: Erik Demaine, Center for Future Civic Media
recorded by: Massachusetts Institute of Technology, MIT
published: Feb. 10, 2009,   recorded: October 2005,   views: 33780
released under terms of: CC BY-NC-SA
You might be experiencing some problems with Your Video player.

# Slides

0:00 Slides Introduction to Algorithms - Lecture 10 Balanced search trees Red-black trees Example of a red-black tree (1) Example of a red-black tree (2) Example of a red-black tree (3) Example of a red-black tree (4) Example of a red-black tree (5) Height of a red-black tree (1) Height of a red-black tree (2) Height of a red-black tree (3) Height of a red-black tree (4) Height of a red-black tree (5) Height of a red-black tree - Theorem Proof Query operations Modifying operations Rotations Insertion into a red-black tree (1) Insertion into a red-black tree (2) Insertion into a red-black tree (3) Insertion into a red-black tree (4) Insertion into a red-black tree (5) Pseudocode Graphical notation Case 1 Case 2 Case 3 Analysis

# 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.

# Description

"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..."

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

1 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

2 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.

3 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.

4 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.

5 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.

6 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.

7 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?!!

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

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

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

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

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

Great !

11 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

12 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:
x
/ \
y z
/ \ / \
a o e u
^ ^ ^ ^

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

Thank you! This indeed a big help!

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

cool!!!!