红黑树高度上限的证明（通俗易懂）

本文主要是介绍红黑树高度上限的证明（通俗易懂），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

先把结论放上，设红黑树的高度为h，总结点数为n，那么h与n的关系就是

$h\leq 2\log_{2}(n+1)$

下面开始证明过程

首先，从任意节点出发，到其子树的叶子节点的路径中黑色节点的数量称为该节点的黑高，即

我们设根节点为T,那么根节点的黑高就是

bh(T)

根据红黑树的性质，我们可知红色节点不可相邻（即红色节点的父节点和孩子节点均为黑色），但是性质中并没有对黑色节点进行要求

换句话说，所有的黑色节点可以挨在一起，一棵红黑树可以全部都是黑色节点。

那么我们就假设一棵只有黑色节点的红黑树(此假设仅作为一个思路提供，可能深究并不严谨)，那么它的黑高bh(T)就是它的树高，我们可得这样一棵树的结点数为（根据树的高度与节点数量的关系）

$n=2^{bh(T)}-1$

而对于红黑树而言，我们还要考虑红色节点，所以在此基础上加上红色节点的数量，那么不论加几个红色节点，只要增加，一定满足下式

$n\geq 2^{bh(T)}-1$ （1）

而根据红黑树的性质，我们可知根节点的黑高bh(T)至少为h/2 (h为树高)，也就是说

$bh(T)\geq \frac{h}{2}$ (2)

根据(1)式(2)式，我们可得

$n\geq 2^{bh(T)}-1\geq 2^{\frac{h}{2}}-1$

即

$n\geq 2^{\frac{h}{2}}-1$

然后稍微计算一下就得到了

$h\leq 2\log_{2}(n+1)$

这篇关于红黑树高度上限的证明（通俗易懂）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！