> For the complete documentation index, see [llms.txt](https://blog.sunilgudivada.dev/notebook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://blog.sunilgudivada.dev/notebook/data-structures-and-algorithms/topics/binary-search-tree/red-black-tree.md).

# Left Leaning Red Black Tree

## Definition

A BST such that:

* No node has two red links connected to it.
* Every path from root to null link has the same number of black links.
* Red links lean left.

![](/files/jyzV0BE442PvisZ5k0MM)

![](/files/jGeyLUXa6cPHFoNuFuQM)

{% hint style="success" %}

#### Properties

* Height of tree is ≤ 2 lg N in the worst case.
* Every path from root to null link has same number of black links.
* Never two red links in-a-row.
  {% endhint %}

## **Sample Red Black Tree with 255 Random Nodes**

![](/files/FM2qWZVrekNDpdMadQTl)

## **Balancing Red Black Tree**

![](/files/N6aID2kVit4EN6JultvU)

## **Complexity Analysis with other Data Structures**

![](/files/7IIf2gSTVoPHqQSmXnUF)