Editing Red–black tree (section)

== Proof of bounds ==
[[File:5 minimal red-black trees nN.svg|thumb|right|320px|Figure 2: Red–black trees RB<sub>''h''</sub> of heights ''h''=1,2,3,4,5,<br/>each with minimal number 1,2,4,6 resp. 10 of nodes.]]
For <math>h\in\N</math> there is a red–black tree of height <math>h</math> with
:{|
|-
|<math>m_h</math> ||colspan=2| <math>= 2^{\lfloor(h+1)/2\rfloor} + 2^{\lfloor h/2 \rfloor} - 2</math>
|-
|rowspan=2| ||rowspan=2;style="vertical-align:bot"| <math>= \Biggl\{</math> ||style="vertical-align:top"| <math>2 \cdot 2^{\tfrac{h}2}-2 = 2^{\tfrac{h}2+1}-2</math> || &nbsp; &nbsp; &nbsp; ||style="vertical-align:bot"| if <math>h</math> even
|-
|style="vertical-align:top"| <math>3 \cdot 2^{\tfrac{h-1}2}-2</math> || ||style="vertical-align:bot"| if <math>h</math> odd
|}
nodes (<math>\lfloor \, \rfloor</math> is the [[Floor and ceiling functions|floor function]]) and there is no red–black tree of this tree height with fewer nodes—therefore it is '''minimal'''.<br/>Its black height is &thinsp; <math>\lceil h/2\rceil</math> &thinsp; (with black root) or for odd <math>h</math> (then with a red root) also &thinsp; <math>(h-1)/2~.</math>

;Proof
For a red–black tree of a certain height to have minimal number of nodes, it must have exactly one longest path with maximal number of red nodes, to achieve a maximal tree height with a minimal black height. Besides this path all other nodes have to be black.<ref name="Algs4"/>{{rp|444 Proof sketch}} If a node is taken off this tree it either loses height or some RB property.

The RB tree of height <math>h=1</math> with red root is minimal. This is in agreement with
: <math>m_1 = 2^{\lfloor (1+1)/2\rfloor} \!+\!2^{\lfloor 1/2 \rfloor} \!\!-\!\!2 = 2^1\!+\!2^0\!\!-\!\!2 = 1~.</math>

A minimal RB tree (RB<sub>''h''</sub> in figure 2) of height <math>h>1</math> has a root whose two child subtrees are of different height. The higher child subtree is also a minimal RB tree, {{nowrap|RB<sub>''h''–1</sub>,}} containing also a longest path that defines its height {{nowrap|<math>h\!\!-\!\!1 </math>;}} it has <math>m_{h-1}</math> nodes and the black height <math>\lfloor(h\!\!-\!\!1)/2\rfloor =: s .</math> The other subtree is a [[Binary tree#Types of binary trees|perfect binary tree]] of (black) height <math>s</math> having <math>2^s\!\!-\!\!1=2^{\lfloor(h-1)/2\rfloor}\!\!-\!\!1</math> black nodes—and no red node. Then the number of nodes is by [[Mathematical induction|induction]]
{|
|-
|style="width:1.0em;"| || <math>m_h</math> || <math>=</math> || <math>(m_{h-1})</math> ||style="width:4em;text-align:center;"| <math>+</math> || <math>(1)</math> ||style="width:4em;text-align:center;"| <math>+</math> || <math>(2^{\lfloor(h-1)/2\rfloor}-1)</math>
|-
| || || || (higher subtree) || || (root) || || (second subtree)
|-
|colspan="8"| resulting in
|-
| || <math>m_h</math> || <math>=</math> || <math>(2^{\lfloor h/2 \rfloor} + 2^{\lfloor(h-1)/2\rfloor} - 2)</math> ||style="text-align:center;"| <math>+</math> ||colspan="2" style="text-align:right;"| <math>2^{\lfloor(h-1)/2\rfloor}</math>
|-
| || || <math>=</math> ||colspan="8"| <math>2^{\lfloor h/2 \rfloor} + 2^{\lfloor(h+1)/2\rfloor} - 2</math>&nbsp;&nbsp;■
|}

The [[Graph of a function|graph]] of the function <math>m_h</math> is [[Convex function|convex]] and [[Piecewise linear function|piecewise linear]] with breakpoints at <math>(h=2k\;|\;m_{2k}=2 \cdot 2^k\!-\!2)</math> where <math>k \in \N .</math> The function has been tabulated as <math>m_h=</math> A027383(''h''–1) for <math>h\geq 1</math> {{nowrap|{{OEIS|A027383}}.}}

;Solving the function for <math>h</math>
The inequality <math>9>8=2^3</math> leads to <math>3 > 2^{3/2}</math>, which for odd <math>h</math> leads to
: <math>m_h = 3 \cdot 2^{(h-1)/2}-2 = \bigl(3\cdot 2^{-3/2}\bigr) \cdot 2^{(h+2)/2}-2 > 2 \cdot 2^{h/2}-2</math>.
So in both, the even and the odd case, <math>h</math> is in the interval
{|
|-
|style="width:1.0em;"| ||style="text-align:right;"| <math>\log_2(n+1) </math> ||style="width:8em;text-align:center"| <math>\leq h \leq </math> || <math>2 \log_2(n+2)-2 = 2 \log_2 (n/2 +1) </math> ||style="width:12em;text-align:right"| <math>\bigl[ < 2 \log_2(n+1) \; \bigr]</math>
|-
| || (perfect binary tree) || ||style="text-align:left;"| (minimal red–black tree)
|}
with <math>n </math> being the number of nodes.<ref>Equality at the upper bound holds for the minimal RB trees RB<sub>2''k''</sub> of even height <math>2 \cdot k </math> with <math>n = 2 \cdot 2^k-2 </math> nodes and only for those. So the inequality is marginally more precise than the widespread <math>h < 2 \log_2(n+1) ,</math> e.g. in [[#Cormen|Cormen]] p. 264.<br/>Moreover, these trees are binary trees that admit one and only one coloring conforming to the RB requirements 1 to 4. But there are further such trees, e.g. appending a child node to a black leaf always forces it to red. (A minimal RB tree of odd height allows to flip the root’s color from red to black.)</ref>

;Conclusion
A red–black tree with <math>n</math> nodes (keys) has tree height <math>h \in O(\log n) .</math>