扫描？BST的代价是线性的 If x is the root of an n-node subtree,then the call INORDER-TREE-WALK(x) takes (n)time. 为什么你会 T(n)=T(k)+T(n-k-1)+d 猜出这么 个结论？ We use the substitution method to show that T(n)=O(n)by proving that T(n)<(c+d)n+c.For n =0,we have (c+d)0+c=c=T(0).For n >0, we have T(n)T(k)+T(n-k-1)+d =(c+d)k+c)+(c+d)n-k-1)+c)+d (c+d)n+c-(c+d)+c+d =(c+d)n+c, 其实我们还需要使用数学归纳 法来证明我们的猜测“扫描”BST的代价是线性的 其实我们还需要使用数学归纳 法来证明我们的猜测 为什么你会 猜出这么一 个结论？ T(n)=T(k)+T(n-k-1)+d