# Red-Black Tree Introduction

Difficulty Level Hard
Advanced Data Structure Binary Search Tree Binary Tree Data Structure Tree

Red Black Tree is a self-balancing binary tree. In this tree, every node is either a red node or a black node. In this Red-black Tree Introduction, we will try to cover all of its basic properties.

## Properties of Red-Black Tree

1. Every node is represented as either red or black.
2. The root node is always black.
3. A red node cannot have a red parent or a red child(i.e. no two red nodes are adjacent).
4. Every path from any node to its NIL descendant must contain an equal number of black nodes.

### Valid and Invalid examples of Red-Black Tree  ## Time Complexity Analysis

All the BST operations like searching, insertion, deletion, etc. can be performed in O(h) time, where h is the height of the red-black tree, and for a balanced BST the height is always of the order log(n) [n-> number of nodes].

Searching = O(log(n))
Insertion = O(log(n))
Deletion = O(log(n))

## Black Height in Red-Black Tree

Black Height in a red-black tree is defined as the number of black nodes on the simple path (you do not visit same node twice) from any node to a leaf(which is NIL). It is represented by bh(x).

## Height of Red-Black Tree

Unlike AVL tree, the height balance is not as strict, but in red-black trees, the number of rotations is less compared to that in AVL trees.
Height of a red-black tree h <= 2(log(n+1)) {Base of log is 2} Detailed proof of why the height of RB trees is <= 2 log (n+1).

Recursion

To maintain the balance in height a red-black tree uses recoloring and restructuring.

You can see how the RB trees recolor and restructure themselves here.

### Recoloring

It refers to changing the color of some red nodes to black and vice-versa, it is done whenever the sibling of a red node’s red parent is red. ### Restructuring

It refers to the rotation of the tree, it is done whenever a red child has a red parent and black or null uncle. There are four cases in restructuring,

• Right
• Left
• Right-Left
• Left-Right ### Applications

• Used in real-world libraries to implement self-balancing BSTs.
• Used as TreeSet and TreeMap in JAVA and Sets and Maps in C++.

### Searching

A red-black tree is a BST, so searching in an RBT is exactly the same as searching in BST, the color of the node does not matter.