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\)
Let’s implement a \(set\) with a Red-Black tree. At minimum we’ll need a
member function and an
A tree can be empty, or it can be a node with two subtrees, a color, and an element.
member function searches for an element. It’s a binary search.
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).
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.