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