Sort
S ? ort 9 5 12 6 1 5 6 7 8 7 8
Sort ①③⑦(
S ? ort 9 12 1 5 6 7 8 9
Sort 9 12 ①③⑦( 9
S ? ort 9 12 1 5 6 7 8 9
Sort ①③⑦( 9)(12
S ? ort 1 5 6 7 8 9 12
Analysis of inorder-walk Theorem. Ifx is the root of an n-node subtree then the call INORDER-TREE-WALK() takes O(n)times Substitution method T(n)=(c+ d)n+c Base case: n=0, T(0)=(c+d)0+C-C For n>o 7(n)=7(k)+7n-k-1)+d (c+ak+c)+((c+d)·(n-k-1)+c)+d (c+ an+c-(c+d)+c+d -(c+ d)n+c
Al f d na lysis o f inor der-walk Theorem. If x is the root of an n-node subtree, then the call INORDER-TREE-WALK (x ) takes Θ ( n ) times. Substitution method T( n) ( = ( c + d) n + c Base case: n = 0, T(0) = ( c + d) · 0 + c = c For n > 0, 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