tl;dr: Complete implementation is at the bottom.

Red-Black trees are notorious for being nightmares of pointer manipulation. Instructors will show the theory, but won’t torture their students to implement one. Interviewers will avoid asking about it. They probably couldn’t do it themselves.

You should be vaguely familiar with how you might balance a tree. The details, however, are probably unnecessary for the purposes of an interview. – Gayle McDowell, Cracking the coding interview

If you’re proficient in a functional language, you owe it to yourself to implement a Red-Black tree. You’ll be one of the few people that can code a Red-Black tree on a whiteboard.

It will make you realize why people are so excited about the whole *functional programming* thing.

### What is a Red-Black Tree?

A Red-Black tree is a balanced binary search tree. Every node is colored red or black. Three rules hold:

- No red node has a red child.
- Every path from the root to an empty node contains the same number of black nodes.
- An empty node is always black.

Draw a tree with these rules. Notice it’s always relatively-balanced. Try to draw one as unbalanced as possible. You won’t get far.

You can prove the maximum depth of a node is at most \(2\lfloor log(n+1) \rfloor\)

### Implementation

Let’s implement a \(set\) with a Red-Black tree. At minimum we’ll need a `member`

function and an `insert`

function.

#### Data

A tree can be empty, or it can be a node with two subtrees, a color, and an element.

#### Member

The `member`

function searches for an element. It’s a binary search.

#### Insert

The `insert`

function uses the function `build`

, which is a constructor that makes sure the node is balanced.

There are four cases when `build`

needs to adjust a node. It detects the case when a black parent has a red child with a red child. It shifts the nodes around to fix it. The solution is the same in every case. (Notice the right hand sides of `build`

are the same).

### Afterwards

That’s it. You have a Red-Black tree.

If you want to learn more, read *Purely Functional Data Structures* by Chris Okasaki. I stole most of my implementation from this book. The `build`

diagram is also from the book.