asymptotic bounds of red and black tree

January 3rd, 2009 | Categories: Programming | Tags:

Warning: fopen(/home/phill84/phill84//wp-content/cache/tex_134c0aba8f0f7b4c55a967c6db48ec89.png) [function.fopen]: failed to open stream: No such file or directory in /home/phill84/phill84/wp-content/plugins/latex/latex.php on line 100

Warning: fputs(): supplied argument is not a valid stream resource in /home/phill84/phill84/wp-content/plugins/latex/latex.php on line 101

Warning: fclose(): supplied argument is not a valid stream resource in /home/phill84/phill84/wp-content/plugins/latex/latex.php on line 102

Warning: fopen(/home/phill84/phill84//wp-content/cache/tex_79f39ca78d5736cdc58924054d3c7a55.png) [function.fopen]: failed to open stream: No such file or directory in /home/phill84/phill84/wp-content/plugins/latex/latex.php on line 100

Warning: fputs(): supplied argument is not a valid stream resource in /home/phill84/phill84/wp-content/plugins/latex/latex.php on line 101

Warning: fclose(): supplied argument is not a valid stream resource in /home/phill84/phill84/wp-content/plugins/latex/latex.php on line 102

Warning: fopen(/home/phill84/phill84//wp-content/cache/tex_5ccc41c66b450ede51bc85e9b519d34e.png) [function.fopen]: failed to open stream: No such file or directory in /home/phill84/phill84/wp-content/plugins/latex/latex.php on line 100

Warning: fputs(): supplied argument is not a valid stream resource in /home/phill84/phill84/wp-content/plugins/latex/latex.php on line 101

Warning: fclose(): supplied argument is not a valid stream resource in /home/phill84/phill84/wp-content/plugins/latex/latex.php on line 102

Warning: fopen(/home/phill84/phill84//wp-content/cache/tex_cfcddc7227a5e5d197d3937ee5288edb.png) [function.fopen]: failed to open stream: No such file or directory in /home/phill84/phill84/wp-content/plugins/latex/latex.php on line 100

Warning: fputs(): supplied argument is not a valid stream resource in /home/phill84/phill84/wp-content/plugins/latex/latex.php on line 101

Warning: fclose(): supplied argument is not a valid stream resource in /home/phill84/phill84/wp-content/plugins/latex/latex.php on line 102

Warning: fopen(/home/phill84/phill84//wp-content/cache/tex_da1031bef0ff32159a39e8a15ff76448.png) [function.fopen]: failed to open stream: No such file or directory in /home/phill84/phill84/wp-content/plugins/latex/latex.php on line 100

Warning: fputs(): supplied argument is not a valid stream resource in /home/phill84/phill84/wp-content/plugins/latex/latex.php on line 101

Warning: fclose(): supplied argument is not a valid stream resource in /home/phill84/phill84/wp-content/plugins/latex/latex.php on line 102

Warning: fopen(/home/phill84/phill84//wp-content/cache/tex_df56c2b3a3810f7cd09aaf3cb4982436.png) [function.fopen]: failed to open stream: No such file or directory in /home/phill84/phill84/wp-content/plugins/latex/latex.php on line 100

Warning: fputs(): supplied argument is not a valid stream resource in /home/phill84/phill84/wp-content/plugins/latex/latex.php on line 101

Warning: fclose(): supplied argument is not a valid stream resource in /home/phill84/phill84/wp-content/plugins/latex/latex.php on line 102

Warning: fopen(/home/phill84/phill84//wp-content/cache/tex_de5be40873295b3a694f6ff5f59d90ad.png) [function.fopen]: failed to open stream: No such file or directory in /home/phill84/phill84/wp-content/plugins/latex/latex.php on line 100

Warning: fputs(): supplied argument is not a valid stream resource in /home/phill84/phill84/wp-content/plugins/latex/latex.php on line 101

Warning: fclose(): supplied argument is not a valid stream resource in /home/phill84/phill84/wp-content/plugins/latex/latex.php on line 102

A red black tree which contains n internal nodes has a height of O(log(n)).

Definitions:

h(v) = height of subtree rooted at node v
bh(v) = the number of black nodes (not counting v if it is black) from v to any leaf in the subtree (called the black-height).

Lemma: A subtree rooted at node v has at least $2^{bh(v)}-1$ internal nodes.

Proof of Lemma (by induction height):

Basis: h(v) = 0

If v has a height of zero then it must be null, therefore bh(v) = 0. So:

2^{bh(v)}-1=2^0-1=1-1=0

Inductive Step: v such that h(v) = k, has at least $2^{bh(v)}-1$ internal nodes implies that $v ‘$ such that h( $v ‘$ ) = k+1 has at least $2^{bh(v')}-1$ internal nodes.

Since $v ‘$ has h( $v ‘$ ) > 0 it is an internal node. As such it has two children each of which has a black-height of either bh( $v ‘$ ) or bh( $v ‘$ )-1 (depending on whether the child is red or black). By the inductive hypothesis each child has at least $2^{bh(v')-1}-1$ internal nodes, so $v ‘$ has at least:

2^{bh(v')-1}-1+2^{bh(v')-1}-1+1=2^{bh(v')}-1

internal nodes.

Using this lemma we can now show that the height of the tree is logarithmic. Since at least half of the nodes on any path from the root to a leaf are black (property 4 of a red black tree), the black-height of the root is at least h(root)/2. By the lemma we get:

$n \geq 2^{{h(\text{root}) \over 2}} - 1 \leftrightarrow \; \log_2{(n+1)} \geq {h(\text{root}) \over 2} \leftrightarrow \; h(\text{root}) \leq 2\log_2{(n+1)}$