> For the complete documentation index, see [llms.txt](https://cs-notes.gitbook.io/algorithm-notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://cs-notes.gitbook.io/algorithm-notes/outline/overview-4/balanced-search-tree/red-black-tree.md).

# Red-Black Tree

[Red Black Tree](/algorithm-notes/outline/overview-4/balanced-search-tree/red-black-tree.md#red-black-tree) is a type of [balanced binary search tree](/algorithm-notes/outline/overview-5/binary-search.md). It adds a bit to stand for the *color*: RED or BLACK, of each node.

*Formal Def*:

A [Red Black Tree](/algorithm-notes/outline/overview-4/balanced-search-tree/red-black-tree.md#red-black-tree) is a type of [binary search tree](/algorithm-notes/outline/overview-5/binary-search.md) that follows the properties below:

1. Each node is either RED or BLACK
2. The *root* is BLACK
3. All leaf nodes (NIL) are BLACK
4. If a node is RED, both of its children are BLACK
5. Every path from a node to its leaves contains the same number of BLACK nodes (*Def: the number of black nodes from a chosen node 𝓍 to a NIL leaf (node 𝓍 is not included) is called the **black-height*** (bh(𝓍)) of such node, the number of black nodes from **root** to any NIL leaves is the **black-height** of the total red-black tree)

## Height Guarantee

*Formal Claim*:

For every [red-black tree](/algorithm-notes/outline/overview-4/balanced-search-tree/red-black-tree.md#red-black-tree) with 𝓃 nodes, its height 𝒽 ⩽ 2 ⋅ log2 (n + 1).

***Proof***:

First, there are at least 2bh(x) - 1 number of internal nodes rooted from node x.

By simple induction, the base case: if height of tree x is 0, then there is 20 - 1 = 0; for tree with height more than 0 with both child nodes, there are at least 2bh(x) - 1 - 1 internal nodes for each child node. Therefore, a rooted tree from x has at least 2 \* (2bh(x) - 1 - 1) + 1 = 2bh(x) - 1.

Presumably, for a given tree with height 𝒽, any paths leading from root to leaves have at least half of the nodes are black, in other words, the bh(*root*) ⩾ 𝒽/2; then

*n* ⩾ 2𝒽/2 - 1, 𝒽 ⩽ 2 log(n+1)

guarantee holds, proof ends.