Red-Black Tree

Description

A red-black tree is a binary search tree where each node is associated with a color (red or black) and has the following properties:

  1. Root property: The root is always black.
  2. Red property: The children of a red node are black.
  3. Black property: For each node with at least one non-null child, paths from this node to all null children have the same number of black nodes.
Here is an example of a red-black tree:
RBT example

Insertion and Deletion

The algorithm for inserting into and removing from a red-black tree is complex. Details on this can be found in this article.