Red Black Trees

A red-black tree is a BST with one extra bit of storage per node: its color. which can be either red or black.

Red-black trees that no such path is no more than twice as long as any other, so that the tree is approximately balanced. The height of a red-black tree with n keys is at most $2\lg (n+1)\to O(\lg n)$

Attrobites of red-black tree node: Color, key, left, right, parent Properties of red-black tree

1. Every node is either red or black
2. Root is black
3. Every leaf is black
4. If a node is red, then both its children are black
5. For each node, all simple paths from the node to descendant leaves contain the same number of black nodes

RB-INSERT

RB-INSERT-FIXUP

RB-DELETE