Red Black Trees

There are lots of different trees for the same set of keys. The height of the tree could range anywhere between log₂n and n. Most of the operations on the search tree are governed by the height, we want to minimum the height. This is where balanced binary trees come in.

We want to ensure that the height is always O(logn) even after insertion and deletion. Some examples are red-black trees, AVL trees, and splay trees. There are also B trees that has multiple keys per node.

A red-black tree is the same as a binary search tree but it has a few invariants.

1. Each node is either red or black.
2. The root is black.
3. No 2 reds in a row - if you have a red node, its children must be black. This implies if a child is red, its parent must be black.
4. Every root-null path has the same number

Every red-black tree with n nodes has a height less than or equal to 2log₂(n+1).