Introduction

Binary search trees can degrade in performance Balanced binary trees require too much overhead during insertion and deletion to maintain search performance This is where red-black trees come in. Unlike balanced binary trees, red-black trees don’t require the height difference between two subtrees to be at most 1 at all times Reference: http://www.sohu.com/a/201923614_466939

Properties

• Nodes consist of red and black colors, with the root node being black
• Leaf nodes are made up of black NIL nodes
• A red node’s children must be black nodes, and must contain two leaf nodes. This means there cannot be two consecutive red nodes.
• Starting from any node, any path to any NIL node must pass through the same number of black nodes

This means that starting from the root node to any leaf node, the difference between the longest path and the shortest path is no more than half of the longest path. In this case, the longest and shortest paths have the same number of black nodes, and the longest path can have at most one additional red node for each black node.

Recoloring and Rotation

When a node is inserted (or deleted), the properties of the red-black tree may be violated. Recoloring and rotation are used to restore these properties.

Recoloring

If two consecutive nodes are red, recoloring is needed

Rotation

If a path has too many black nodes, rotation is needed

Conditions for Recoloring and Rotation

This will be summarized later