---
tags: fall 2018 cs61b
---
# Red Black Trees
[TOC]

## Introduction
**Red-Black Trees** are binary trees with nodes that are colored red and black.

There may be some discreprencies with red-black trees on some exams because for some semesters, they taught with red or black *links* instead of *nodes*.

## Purpose
Red Black Trees are considered the best of both worlds. They are balanced trees that allow us to search for nodes in $θ(\textrm{ log } N)$ time. However, they are also in the shape of a binary search tree, allowing us to run some BST operations (not all of them!).

## Constraints
Referenced from [Hilfinger's slides](https://inst.eecs.berkeley.edu/~cs61b/fa18/materials/lectures/lect29.pdf):
> 1. Each node is colored red or black.
> 2. Root node is black.
> 3. Every leaf node contains no data (null) and is black. (These are the black nodes at the end of the Red Black Tree above!)
> 4. Every leaf has same number of black ancestors.
> 5. Every internal node has two children.
> 6. Every red node has two black children.

## Insertion Methods
You might have learned about color flips and rotation when it comes to insertion. The cases are quite complicated! If you're really interested in understanding how to insert numbers directly into a red black tree, I recommend reading these [slides](https://docs.google.com/presentation/d/1j7kiMfMzmhdi6AoKSuYdZr65iH7ckeWMKGQAyI4M61c/edit#slide=id.g1ee126c17d_0_0) (start at Slide 43) and watching this short [video](https://www.youtube.com/watch?v=A3JZinzkMpk).

According to this [lecture](https://docs.google.com/presentation/d/1J7fPC_BYohgDUUDxTk4PiE6XyBHDUAatvOqX_vOhIWw/edit#slide=id.g3d073bd9ed_7_248) (Slide 32), you don't need to always consider rotations and color flips for the insertion process. Instead, you can consider the **1-1 correspondance between 2-3 Trees and Red Black Trees**.

### Summary
There are two methods for inserting into a Red Black Tree:
1. Insert and perform a series of color flips and rotations (difficult, but if you're interested, watch this [video](https://www.youtube.com/watch?v=A3JZinzkMpk))
2. Convert to a 2-3 Tree. Insert everything one-by one (order matters!). Convert back to a Red Black Tree. (recommended!)

## Checking for a Valid Red-Black Tree
If you're ever unsure if the red-black tree you created is valid, try following this checklist:
- [ ] Maintains BST properties (left child smaller than root, right child greater than root)
- [ ] Every leaf has the same number of black ancestors (meaning every path from the root node to the leaf node should contain the same number of black links/nodes)
- [ ] The root node/link is black

**Let's try the checklist on the Red Black Tree pictured above.**
- [x] Maintains BST properties (e.g. 5 < 15 < 35)
- [x] Every leaf has the same number of black ancestors
- [x] The root node is black

**Conclusion:** The Red Black Tree above is valid!

## Resources
### Red-Black Tree Rotation and Color Flip Videos
* [Examples](https://www.youtube.com/watch?v=A3JZinzkMpk)
* [Strategies](https://www.youtube.com/watch?v=5IBxA-bZZH8)