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. cs.stackexchange.com/question...)
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): • Binary Search Trees: S...
Python code for a minimalist implementation of Red-Black Trees can be found here: github.com/albanie/algorithms...
Slides (pdf): samuelalbanie.com/files/diges...
References for papers mentioned in the video can be found at
samuelalbanie.com/digests/2022...
Recommended further reading on this topic:
- L. Arge and M. Lagoudakis, CPS 230 lecture notes, courses.cs.duke.edu/cps130/fa...
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to algorithms. MIT press. mitpress.mit.edu/978026204630...
For related content:
- UA-cam: / @samuelalbanie1
- Twitter: / samuelalbanie