# 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.