Lecture 10: Red-black Trees, Rotations, Insertions, Deletions
recorded by: Massachusetts Institute of Technology, MIT
published: Feb. 10, 2009, recorded: October 2005, views: 151803
released under terms of: Creative Commons Attribution Non-Commercial Share Alike (CC-BY-NC-SA)
Report a problem or upload filesIf 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.
"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..."
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 pageWould you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !