# Red Black Tree

Written by

What is Red Black Tree ?

Insertion in Red Black Tree

Deletion in Red Black Tree

**What is Red Black Tree?**

A red-black tree is a binary tree where each node has a color attribute, the value is either Red or black.** It is a self-balancing Binary Search tree.**

A red-black tree follows all requirements that are imposed on a Binary Search Tree, however, there are some additional requirements of any valid red-black tree.

- A node is either
**Red**or**Black**. - The root is always Black.
- All the roots can be changed from red to black.
- All leaves (Null Child nodes) are black.
- Both children of every red node are black.
- Every simple path from the node to a descendant leaf contains the same number of black nodes.

**A red-Black tree** has the worst-case guarantees for insertion time, deletion time and search time. This makes it valuable in time-sensitive applications, also in other building blocks in other data structures with worst-case guarantees.

It allows guarantee searching in ** O (Log n)** times, where

**is the total number of elements in the tree. The rearrangement and recoloring of the tree after an insertion or deletion is also performed in**

*n***time.**

*O (Log n)*This type of data structures are used in computational geometry. They are also quite valuable in functional programming. It is also used in **CPU Scheduling Linux**,** Completely Fair Scheduler** uses it. If we compare the red-black tree to AVL tree, AVL seems to be a little more balanced than the Red-Black Tree.