红黑树时间复杂度

Question

如题所述

Answer 1

红黑树性质与时间复杂度证明扩展：

一、红黑树性质：

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'sblackhe为bh(x)。

3、根据性质五可知，从节点x出发到达所有的叶节点都具有相同数目的黑节点。这也就意味着，bh(x)的值是唯一的!