RB 树上的复杂性分析练习

Question

BLACK_PATH(T,x)
if x==NIL 
then return TRUE
if COLOR(x)==BLACK
then return BLACK_PATH(T,left(x)) || BLACK_PATH(T,right(x))
return FALSE

这些练习要求分析该程序的复杂性。我认为复发如下

T(n)<=2T(2n/3)+O(1)

使用递归树，我得到 T(n)=O(n)。这是对的吗？

Answer 1

这种方法的复杂度在树中元素数量最坏的情况下是线性的(O(n))。

在这里使用主定理来计算节点总数是困难的，因为它没有考虑红黑树的属性。虽然对于堆来说，具有n节点的树的每个子树都有最多2n/3个节点，但对于红色黑树，每个子树最多有n/2个黑色节点也是正确的。这是因为红色黑色树相对于黑色节点是平衡的(从任意节点向下到叶节点的每条路径都具有相同数量的黑色节点)。

最重要的是：因为总节点数不会渐近地高于黑色节点的数量，所以通过纯粹根据黑色节点总数来分析复杂性，隐式分析与节点总数相关的复杂性。

因此，与其使用T(n)<=2T(2n/3)+O(1)，不如使用T(m)<=T(m/2)+O(1)其中m是黑色节点的数量，这为您提供了O(m)，并且因为如前所述，O(m)==O(n)，我们有O(n)。

另一种思考方式：只要你能理解这个算法是O(n)树中的所有节点都是黑色的，你应该能够理解，如果树中的某些节点是红色的，它才可能需要更少的操作，因为无论红色节点在哪里，子树中根植于该红色节点的每个节点都将被忽略并且不会访问通过这种递归算法。因此，它只能是O(n)或更好，将O(n)确定为最坏的情况。