Lecture 10: Red-black Trees, Rotations, Insertions, Deletions
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)
Slides
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.
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..."
See Also:
Download slides:
mit6046jf05_demaine_lec10_01.pdf (317.0 KB)
Download mit6046jf05_demaine_lec10_01.m4v (Video - generic video source 174.7 MB)
Download mit6046jf05_demaine_lec10_01.rm (Video - generic video source 134.1 MB)
Download mit6046jf05_demaine_lec10_01.flv (Video 232.3 MB)
Download mit6046jf05_demaine_lec10_01_320x240_h264.mp4 (Video 249.5 MB)
Download mit6046jf05_demaine_lec10_01.wmv (Video 741.7 MB)
Download mit6046jf05_demaine_lec10_01.mp3 (Audio lecture 19.4 MB)
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:
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
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.
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.
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.
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.
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.
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?!!
hi it is very useful for us...............
hi it is very useful for us...............
Great !
i got this lectures very useful !! got wat exactly a RBT is , thanks to MIT
@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
^ ^ ^ ^
Thank you! This indeed a big help!
cool!!!!
I enjoy your lectures alot, especially the Manner of presentation. I sincerely learn a lot from them. more grease to your elbows.
Great!
RBT Node Inserting - doc let link is shared here.
https://drive.google.com/file/d/0B1pg...
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.
just Awesome! Today I understand the RB trees
Write your own review or comment: