Algorithm Science (Summer 2025) - 19 - Red-Black Trees

This video was made as part of a second-year undergraduate algorithms course sequence (Algorithms and Data Structures I and II). Despite all of the pontificating about the need to make this topic accessible, I did a bad job of proofreading some technical points in the slides for this lecture, so there are a few errors: - The definition of the degree constraint (around 38:15) is incorrect, since it does not consider the case where a black node has a single red child (which is allowed, as is evident in the subsequent examples). A better phrasing of the degree constraint is "Except for black nodes with a single red child, all nodes must have either zero or two children." - The summary of removal cases (starting at 1:46:53) is oversimplified. Cases 4 and 7 should be split into two subcases, one where the root of T1 is red and one where the root of T1 is black. The version shown on the slides only covers the case where the root of T1 is black. The two subcases for Case 4 correspond to the case where a 3-node has a 1-node child with a 2-node sibling (which is shown in the slides and video) and the case where a 3-node has a 1-node child with a 3-node sibling (which is not shown). The two subcases for Case 7 correspond to the case where a 2-node has a 1-node child with a 2-node sibling (which is shown in the slides and video) and the case where a 2-node has a 1-node child with a 3-node sibling (which is not shown). The correct red-black behavior for each subcase can be derived from the corresponding 2-3 tree removal cases, though. 0:00 Introduction/Complaining 7:35 Dictionaries 13:47 Deconstructing a 2-3 Tree 32:09 Red-Black Trees 47:17 Red-Black Tree Operations 55:42 Rotations and Flips 1:04:15 Insertion into Red-Black Trees 1:20:32 Insertion Cases 1:27:49 Removal of a Red Leaf 1:29:05 Removal of a Black Leaf - Level I 1:32:37 Removal of a Black Leaf - Level II 1:35:42 Removal of a Black Leaf - Level III 1:43:24 Removal of Internal Nodes 1:46:53 Removal Cases 2:02:23 Summary The "left-leaning" variant of red-black trees described in this lecture was first described by R. Sedgewick in 2008, but the main source consulted for these slides was the book Algorithms by R. Sedgewick and K. Wayne (4th edition, 2011). However, some of the modification logic in these slides (particularly for removal) was based directly on 2-3 tree operations (see previous lecture), not the procedures given in Sedgewick and Wayne’s book (which are significantly different, but achieve the same effect). All slides and diagrams are original content (developed in early 2025). The materials used in this video, and the video itself, were prepared without any assistance from generative AI. As any viewer will quickly realize, these videos were made just like in-person lectures: in one sitting, with no breaks, editing or script. If you find any of this helpful or interesting, please let me know (I really appreciate any other feedback as well).