How Red Black Trees (RBT) Work

What is an RBT?

An RBT is a self-balancing implementation of a Binary Search Tree where every node is either red or black.

Lists, images, and links related to RBTs:

Properties of an RBT:

• The root is always black
• Red nodes cannot have red children
• The path to every non-null node must contain the same quantity of black nodes from the root

Example of a simple RBT from Geeks for Geeks:

For more information on RBTs, vist: UW Madison's page on RBTs