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.

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.

Sample Red Black Tree with 255 Random Nodes

Balancing Red Black Tree

Complexity Analysis with other Data Structures