Red-Black Trees (Mar 13)
Resources
Lecture Notes
- Read this first, so you know the basics of red-black trees (RBTs).
- Make note of the 5 properties which define a red-black tree (slide 4)
- Make note of the 3 cases during RBT insertion (slide 32)
- Get an idea of the properties of RBTs, and some of the related proofs.
Textbook
- Pages 315-321
- Code for RBT insertion
- Code for RBT fix (fixing the RBT after insertion)
- Good figures and explanations for how the code works, what the cases are (also described in lecture notes)
- Shows a proof for why the code works
Tool to visualize RBT insertions (link)
- VERY helpful to understand the cases mentioned above
- If you didn't attend tutorial, follow the video link on the left side
- Try to solve all five cases (turn each one into a valid RBT tree, if it isn't already)
- Cases 1 and 2 are special base cases. Cases 3-5 match Cases 1-3 from the lecture/textbook
- Examples values for each case:
- Case 1: add 22
- Case 2: add 22
- Case 3: add 22
- Case 3 mirror: add 99
- Case 4: add 49
- Case 4 mirror: add 22, add 10
- Case 5: add 46
- Case 5 mirror: add 22, add 24
- hint: instead of trying to memorize the left/right of each case, look at two things:
- Is the uncle (sibling of parent) red or black?
- If the uncle is a black node, are both the uncle and the new node (recently inserted) both left/right children? Or is one of them left, while the other is right (and vice versa)?
- So then, why do we have 6 cases instead of the 3 here? Well, when you write code, you will need to write 6 cases, because the computer will not group the mirrored cases together. Conceptually, however, the mirrored cases are identical.
Tool to visualize RBT (link)
- More of a sandbox, can do both insertions and deletions
- Gives you step by step rationale for how each node is inserted or deleted
- To use:
- pause when you want to read the rationale (small text in the left-top corner)
- insert/delete a node
- use step forward/backward buttons