红黑树的时间复杂度证明

参考这篇文章

首先我们知道,红黑树是一棵二叉查找树,其左子树都比根结点的值小,右子树都比根结点的值大。

因此,高度为h的红黑树,插入查询删除的时间复杂度也是$O(h)$。

证明

需证:结点个数为n的红黑树,高度为$O(logn)$。(log函数以2为底)

我们定义两个函数$h(v)$和$bh(v)$:

  • $h(v)$代表以任意结点$v$为根的子树的高度
  • $bh(v)$代表在$v$子树中,从$v$结点到任意黑色叶子结点的数目(如果$v$是黑色则不计数它,也叫做黑色高度)

引理:以结点$v$为根的子树有至少$2^{bh(v)} – 1$个结点。

要证明上述定理,需要用到数学归纳法。

我们依次证明$h(v)=0$、$h(v)=3$时满足上述定理,最后从$h(v)=k$引申到$h(v’)=k+1$都满足定理。

$h(v)=0$时,树高为0,$bh(v)=0$,此时$2^{bh(v)}-1=2^0-1=0$,满足定理。

$h(v)=3$时,观察下图:

$bh(v)=1$,此时$2^{bh(v)}-1=2^1-1=1$,即要求至少要有一个结点,而图中以$v$为根的子树有5个结点。

因此,存在一棵红黑树,当$h(v)=3$时,满足定理。

接下来,我们假设$h(v)=k$时,根据定理$v$子树中至少有$2^{bh(v)}-1$个结点。

那么当$h(v’)=k+1$时,黑色高度可能不变也可能加一,即:
$$
bh(v’)=
\begin{cases}
bh(v), \
bh(v)+1 \
\end{cases}
$$
对于$v’$的左右子树而言,$h(v’_左)=h(v’_右)=k$,因此左右子树结点+根结点就是$v’$的总结点树了,即:

从$h(v)=k \to h(v’)=k+1$,设$v’$子树的结点个数为$n’$:
$$
n’>=2^{bh(v_左)}-1 + 2^{bh(v_右)}-1 + 1 = 2^{bh(v)+1} -1>= 2^{bh(v’)}-1
$$
即证以结点$v$为根的子树有至少$2^{bh(v)} – 1$个结点

又由于红黑树的性质,红色父结点必定有两个黑色的子结点,而黑色父结点没有这个要求。因此在一条从根到叶的最长路径中,该路径长度等于树高,黑色结点数目必然大于等于红色结点数目,即:
$$
bh(root) >= \frac{h(root)}{2}
$$
所以:
$$
n >= 2^{bh(root)}-1>=2^{\frac{h(root)}{2}}-1
$$

那么:
$$
2^{\frac{h(root)}{2}}<= n + 1 \to h(root)<=2log(n+1)
$$

结论

$h(root)<=2log(n+1)$表明,红黑树的树高小于等于$2log(n+1)$。那么插入查询删除结点的时间复杂度自然也就是$log(n)$了。

暂无评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

浙ICP备19002997号