# 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.

![](https://1133441777-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MP3gpNOfmHBf90k26iY%2Fuploads%2Fgit-blob-e8a8faaaeae608320123c420036a864025f77c06%2Fimage%20\(48\).png?alt=media)

![](https://1133441777-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MP3gpNOfmHBf90k26iY%2Fuploads%2Fgit-blob-dff6f541277e15964c9d30af531c0fe5d14e6f1d%2Fimage%20\(66\).png?alt=media)

{% 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**

![](https://1133441777-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MP3gpNOfmHBf90k26iY%2Fuploads%2Fgit-blob-80981197f2beda9edfed4f8f4ba445a5102dfec2%2Fimage%20\(60\).png?alt=media)

## **Balancing Red Black Tree**

![](https://1133441777-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MP3gpNOfmHBf90k26iY%2Fuploads%2Fgit-blob-3c3c947094663a60237aeb9411703ee4d4acd328%2Fimage%20\(76\).png?alt=media)

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

![](https://1133441777-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MP3gpNOfmHBf90k26iY%2Fuploads%2Fgit-blob-2b58c73b8074dddb1ae7eb27b19eb639df9b1e5c%2Fimage%20\(34\).png?alt=media)