Introduction.

Start with this Video.

Red-Black Trees // Michael Sambol

Terminology

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.

• What is the difference between tree depth and height?

The Rules

The video discusses some points I mention blower:

• Every node is red or black.
• The root is always black.
• New insertions are always red.
• Every path from root-leaf has the same number of BLACK nodes.
• No path can have two consecutive RED nodes.
• Null is always black.