Red-black trees: Samuel's tutorial

Samuel's tutorial on red-black trees covering search, insert and delete operations. Timestamps: 00:00 - Brief Guide to Red-Black Trees 02:45 - Red-Black Tree Properties 05:25 - Rotation Operations 07:52 - Why Are Rotations Useful? 09:44 - Red-Black Tree Insertion 14:48 - Red-Black Tree Deletion 19:26 - Fixing Red-Black Tree Violations from Deletion Corrections: 03:56 - Note: sometimes the term "perfect binary tree" is used rather than "complete binary tree" here. There isn't a settled community consensus (see e.g. https://cs.stackexchange.com/questions/32397/is-there-a-difference-between-perfect-full-and-complete-tree) 16:40 The variable x should be defined as u.right in the first condition, and u.left in the second condition. Detailed description: This video provides a short description of red-black trees. We first begin with their historical development and describe their key property: guaranteed O(log n) complexity for the operations of search, insert and delete. We then discuss the five properties that characterise red-black trees and describe how they combine to ensure that tree height is Theta(log n). Next, we discuss rotation operations. These enable us to restructure a tree locally without violating the binary search tree property. They are particularly useful for balancing trees because they can shift nodes from one path to another. We describe red-black tree insertion in detail, stepping through each of the cases that can arise and how we resolve red-black tree property violations. Last, we walk through the deletion operation in red-black trees, describing the "double black" trick, the various cases that must be handled, and how everything comes together to ensure O(log n) complexity. Topics: #datastructures #redblacktree #coding A brief guide to binary search trees (mentioned in the video as a building block for red-black tree insertion): https://www.youtube.com/watch?v=0woI8l0ZWmA Python code for a minimalist implementation of Red-Black Trees can be found here: https://github.com/albanie/algorithms-and-data-structures Slides (pdf): https://samuelalbanie.com/files/digest-slides/2022-12-brief-guide-to-red-black-trees.pdf References for papers mentioned in the video can be found at http://samuelalbanie.com/digests/2022-12-brief-guide-to-red-black-trees Recommended further reading on this topic: - L. Arge and M. Lagoudakis, CPS 230 lecture notes, https://courses.cs.duke.edu/cps130/fall02/fall02lectures/lecture18/long_redblack.pdf - Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to algorithms. MIT press. https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/ For related content: - YouTube: https://www.youtube.com/@SamuelAlbanie1 - Twitter: https://twitter.com/SamuelAlbanie