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

一、红黑树性质

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)