当前位置: 代码迷 >> 综合 >> 红黑树时间复杂度为什么是O(logn)?
  详细解决方案

红黑树时间复杂度为什么是O(logn)?

热度:79   发布时间:2023-12-25 08:22:46.0

一、红黑树性质

  1. 结点必须是红色或者黑色。
  2. 根节点必须是黑色。
  3. 叶节点(NIL)必须是黑色(NIL节点无数据,是空节点)。
  4. 如果一个节点是红色的,则它的子节点必须是黑色的。
  5. 从任一节点出发到其每个叶子节点的路径,黑色节点的数量必须相等。

二、时间复杂度证明

接下来我们将通过“数学归纳法”对红黑树的时间复杂度进行证明,保证让您看得明明白白!

首先我们要知道O(logn)中的n是指红黑树节点个数。

已知一条关于红黑树的定理:一棵有n个节点的红黑树高度h至多为2log(n+1)。(h <= 2log(n+1)

只要证明这条定理成立,时间复杂度也就成立的(因为红黑树查询的时间复杂度其实就是从根节点开始往下查询,最大查询时间也就是到叶节点终止,即为树的高度),接下来就来证明这条定理。

  1. h <= 2log(n+1)可推出n >= 2^(h/2)-1。得出定理的逆否命题是 "高度为h的红黑树,它包含的节点个数至少为 2^(h/2)-1个"。我们只需证明逆否命题为真,即证明了原命题为真。
  2. 从某个节点x出发(不包括该节点)到达一个叶节点的任意一条路径上,黑色节点的个数称为该节点的黑高度(x's black height),记为bh(x)
  3. 根据性质五可知,从节点x出发到达所有的叶节点都具有相同数目的黑节点。这也就意味着,bh(x)的值是唯一的
  4. 根据性质四可知,从节点x出发到达叶节点"所经历的黑节点数目">= "所经历的红节点的数目"(画个红黑树数数就理解了)。假设x是根节点,则可以得出结论"h/2 <= bh(x) < h" (h=黑高度+红高度)。
  5. 因此接下来只需证明"高度为h的红黑树,它包含的节点个数至少为 2^bh(x)-1个"。(n >= 2^bh(x)-1)

下面通过"数学归纳法"论证n >= 2^bh(x)-1:

  • 当bh(x)=0时,节点数n(b) = 2^(0)-1 = 0,原命题成立;
  • 当bh(x)=k时,假设该树至少有2^bh(x)-1 = 2^k-1个节点;
  • 当bh(x)=k+1时,根节点的两棵子树的黑高度肯定都为k(根据性质二和性质五),则两棵子树上的节点个数和至少为2*(2^bh(x)-1) = 2^(k+1)-2,那么该树共有2^(k+1)-2+1(加上根节点) = 2^(k+1)-1个节点,与右式相等,原命题成立。

因此,“一棵含有n个节点的红黑树的高度至多为2log(n+1)” => 红黑树时间复杂度为O(logn)