Red Black Trees

Red black trees are a binary search tree where every node is either colored red or black. In order to be considered one, it must abide to the following rules:


There are two important factors when inserting a node into a red black tree: Recoloring and Rotating. The new node must be added as a leaf in its corresponding position and assigned the color red. Then, the tree is adjusted to follow the rules of a valid red black tree, depending on the cases that may appear.

Image of a valid Red Black Tree

For a more in-depth read on this topic: Introduction to Red Black Trees