Red Black Trees

Image and Overview

a Red Black Tree is a self balancing binary search tree, and remains balanced through insertions/deletions.

Characteristics

• Every node needs to be red or black
• The root node must always be black
• There cannot be two consecutive red nodes
• The number of black nodes must be the same in each branch