红黑树的时间复杂度分析

大家好，欢迎来到IT知识分享网。

一、红黑树的基本属性。

1. 红黑树的每个结点，要么是黑色，要么是红色。
2. 根结点(root)一定是黑色。
3. 所有红色结点不可以直接相连。 也即是，如果一个结点为红色，那么，它的爸爸或儿子，一定就是黑色，不可是红色。符合，绿帽定律。
4. 所有空结点，都是黑色。所谓的空结点，就是当红黑树的某一个叶子结点下，没有其它结点，那么这个结点，就是空结点，用NIL 或 NULL 表示。
5. 从任意结点出发，到其某个子结点的空结点，所经过的黑结点数量，总是相同的。(维基上的原文：Every path from a given node to any of its descendant NIL nodes contains the same number of black nodes.)

二、基础概念。

1、空结点，即值为NIL 或 NULL的结点，
2、亲子结点，跟某一根结点，直接相连接的两个结点，称作亲子结点。
3、h(x)，即树的高度
4、bh(x) , 全称是Black Height(x) ，是指结点x所在的位置的黑树的高度。听起来，有点抽象，让我们来看一张图片。以结点10为例， x = 10时， BH(x) = BH(10) = 2。这个2是怎么来的呢？从结点10开始数起（不包含起始结点），到空结点为止。5是黑色结点，NIL也是黑色结点。所以，BH(10) = 2。同理，我们再举一个例子，结点9，当 x = 9时，BH(x) = BH(9) = 1(不包含起始结点)，NIL是黑色结点，所以，BH(9) = 1。现在，你应该清楚的了解了什么是BH（即黑树的高度）。

三、通过归纳法论证红黑树的时间复杂度为Olog(n)。

通过对红黑树的大量研究，人们发现这么一个规律，以结点x为根结点的子树，至少包含，2^bh(x)-1个内结点。这个规律是通过，大量的研究，总结出来的。但规律，毕竟只是规律，必须通过证明，才能确定是正确的。Loosely Speaking，我们把这种归纳出来的，需要被证明的规律，称为引理。把经过证明的引理，称为定理。接下来，让我们来证明这个引理。在证明的过程，我们依据由简入繁的思路，步步为营。

引理：结点x的子树至少包含2^bh(x)-1个内结点。

证明过程：

1. 首先，我们来证明一种比较简单的情况，即h(x) = 0 。当结点x包含的子结点为0时，这个结点一定是空结点NIL。而且，空结点的黑树高度，也必然为0（结点本身不计数），即当h(x) =0时，bh(x) = 0也必然成立。因为上述的描述是必然正确的(不信者，可自代实数以验之)，所以，如果引理是正确的，引理一定会满足以上的条件，让我们将这种情况，代入到引理中：

   当h(x) = bh(x) = 0 时，2^bh(x) – 1 = 2^h(x) – 1 = 2⁰ – 1 = 1 – 1 = 0。综上所述，当h(x) = bh(x) = 0 时，引理是正确的。

2. 接下来，我们证明h(x) > 0的情况。当h(x) > 0时，意味着结点x一定是个叶子结点，每一个叶子结点，都拥有左右两棵子树（或空结点）。 那么，结点x的左右子树两边的黑高，要么是bh(x)，要么是bh(x)-1。这取决于，结点x的亲子结点的颜色。如果亲子结点是红色，就是bh(x)-1。如果是黑色，即是bh(x)。因为如果是亲子结点是红色的，不计入黑高。根据归纳法，每一个子树，至少包含(2^bh(x)-1 – 1) 个结点。所以，结点x至少包含，左树结点 + 右树结点 + x结点本身，个结点。

   综上所述，我们可以得到如下公式：(2^bh(x)-1 – 1) + (2^bh(x)-1 – 1) + 1 = 2^bh(x) – 1。其中，第一个括号代表左子树，第二个代表右子树，最后的+1代表结点x本身。

3. 根据1和2的论证，我们可以知道，某个结点x，至少会包含 2^bh(x) -1 个结点。我们设总结点数为N，则 N ≥ 2^bh(x)-1。 接下来就是变形的过程：

   已知，N ≥ 2^bh(x)-1
   所以， N + 1 ≥ 2^bh(x)
   所以，log₂(N +1) ≥ bh(x)

4. 根据红黑树的第三个属性，红色结点不可以直接相邻。所以，从某一个根结点到其任意一个空结点NIL的任意路径上(这句话的意思是指h(x)，即树的高度)，黑色结点的数量(这句指的是bh(x))，至少包含一半及以上。即，bh(x) ≥ h(x)/2。 让我们把这句，代入论述3里面的公式，可得：

   log₂(N +1) ≥ bh(x) ≥ h(x)/2，
   两边同时，乘以2，得 2log₂(N+1) ≥ h(x)。
   所以，h(x) ≤ 2log₂(N+1)。
   因为，当N+1趋于无限大时，2log₂(N+1)与lg(N)，只相差一个常数。
   所以，h(x) ≤ 2log₂(N+1)，等价于h(x) ≤ lg(N)，也等价于log(N)。
   也即是，Olog(N)或Olog(n)。

【看不懂为什么，log₂(N)==lg(N)==log(N)的，可以查看，博文最底部的注1】

四、总结。

学习红黑树的复杂度，需要了解算法、红黑树、对数函数、指数函数和数学归纳法的一些基本概念。其中任何知识点的不熟悉，都会对整个论证过程，造成障碍。最后，感谢各位的阅读，要是还有什么疑问，可以留言提出。

【注1】：

这里为什么要，强调或是O(lgn)呢？因为在算法领域，当log的底数固定，且n趋于无限大时，两者的结果都是一个常数，只是两者存在一个倍数差而已。所以，在研究算法时，这底数是可以忽略掉。打比方说：O(n+100000)，我们会简单的看成O(n)，一样的道理。这表达的是一种极限思维。不理解这点的，可以再私聊我详聊，这里不再赘述。

【参考资料】

1、维基百科-红黑树。
2、Red-Black Trees。