# RED-BLACK TREES

A Red black tree is a type of tree data structure. It is basically a Binary Search tree
that has both red and black colored nodes that follow a
certain set of properties. Below is an image that shows how a Red-black tree looks like:

To better understand the existence of such a tree, let us dive into the properties of
a red-black tree.

## Properties of a Red-black tree:

- It follows all properties of a Binary Search tree.
- Every node is either red-colored or black-colored
- The root node is always a black node.
- A red node cannot have a red
child.
- Every possible path from the root node to any leaf node in the tree consists of
the same number of black nodes.

This is an example of a valid RBT (short for red-black tree):

## Red-black tree operations:

You can perform three simple operations on a red-black tree:

In all of these operations, the insert and delete operations modify the tree,
which may cause changes in the properties of the red-black tree too. Thus, we should
also take care of fixing the tree and restoring all its properties so that it remains
as a red-black tree. For that, there is a fix algorithm in place that
traverses through the entire modified tree and changes position and color of the nodes
so that it follows the properties of a red-black tree as indicated in the previous section
above.

### Worst-case Complexities:

- Insert: O(log(N))
- Search: O(log(N))
- Delete: O(log(N))

where N is the number of nodes in the red-black tree.