Start with this Video.

Red-Black Trees // Michael Sambol


Let's familiarize ourselves with some terms we'll commonly come across in our upcoming discussion. Here is a helpful diagram showing the terms:


A tree node's height is defined as the number of edges on the longest path to a leaf. A leaf node's height is 0. For example, in the preceding diagram, the height of the node h is 0.

The total number of children of a node is collectively referred to as the node's degree. A leaf node's degree is 0. In the preceding diagram, the degree of node a is 2.

A non-leaf node is also called an internal node. For example, in the preceding diagram, node c is an internal node, so are a, b, d, e, f, and g.

Every internal node in the preceding tree has the same degree: 2. This makes this tree a complete binary tree.

The Rules

The video discusses some points I mention blower: