时间戳

首页 > 解决方案 > RB-Trees 的复杂性分析练习

algorithm - RB-Trees 的复杂性分析练习

问题描述

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)。这个对吗？

标签： algorithmasymptotic-complexityrecurrencered-black-tree

解决方案

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

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

最重要的是：因为总节点的数量并不渐进地高于黑色节点的数量，所以通过纯粹根据黑色节点的数量分析复杂度，隐含地分析相对于节点总数的复杂度。

因此，与其使用T(n)<=2T(2n/3)+O(1)你，不如使用T(m)<=T(m/2)+O(1)wherem是给你的黑色节点的数量O(m)，因为如前所述O(m)==O(n)，我们有O(n)。

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

推荐阅读