What are red-black trees and their properties?

A Binary Search Tree (BST) is a tree in which every node has two children (left & right), and every node’s left child is smaller than the node while every node’s right child is larger than the node. Let’s take a look at the following example of a BST.

Red-black trees

A red-black tree is a kind of self-balancing binary search tree (BST)a tree in which each node’s left child is smaller in value and each node’s right child is greater in value, where each node is either red or black. Therefore, red-black trees store an extra item for each node to specify their color. It tries to balance itself in case of arbitrary insertions and deletions, while keeping the rules of BST in mind.

There are some distinctive properties of a red-black tree:

• The root node is always black.
• Every node is either red or black.
• Every NULL pointer (missing child) is considered black.
• If a node is red, both children should be black. (We cannot have two consecutive reds nodes in a path.)
• Every path from the root to the leaf contains the same number of black nodes.

Below is a red-black tree.