Introduction to Algorithms 6.046J/18.401J/SMA5503 Lecture 9 Prof charles e. leiserson
Introduction to Algorithms 6.046J/18.401J/SMA5503 Lecture 9 Prof. Charles E. Leiserson
Binary-search-tree sort T< b Create an empty bst for i=l to n do TREe-INSERT(T, AiD Perform an inorder tree walk of t Example A=[3182675] 8 ree-walk time =O(n but how long does it take to build the bst c 2001 by Charles E Leiserson Introduction to Agorithms Day 17 L9.2
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 17 L9.2 33 Binary-search-tree sort T ← ∅ ⊳ Create an empty BST for i = 1 to n do TREE-INSERT(T, A[i]) Perform an inorder tree walk of T. Example: A = [3 1 8 2 6 7 5] 11 88 22 66 55 77 Tree-walk time = O(n), but how long does it take to build the BST?
Analysis of bst sort BST sort performs the same comparisons as quicksort, but in a different order 3182675 8)675 675 The expected time to build the tree is asymptot ically the same as the running time of quicksort c 2001 by Charles E Leiserson Introduction to Agorithms Day 17 L9.3
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 17 L9.3 Analysis of BST sort BST sort performs the same comparisons as quicksort, but in a different order! 3 1 8 2 6 7 5 1 2 8 6 7 5 2 6 7 5 5 7 The expected time to build the tree is asymptotically the same as the running time of quicksort
Node depth The depth of a node the number of comparisons made during TREE-INSERT. Assuming all input permutations are equally likely, we have Average node depth E∑( comparisons to insert no lO(nlgn) (quicksort analysis O(gn) c 2001 by Charles E Leiserson Introduction to Agorithms Day 17 L9.4
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 17 L9.4 Node depth The depth of a node = the number of comparisons made during TREE-INSERT. Assuming all input permutations are equally likely, we have ( ) (lg ) ( lg ) 1 #comparisons to insert node 1 1 O n O n n n E i n n i = = = ∑= Average node depth . (quicksort analysis)
Expected tree height But, average node depth of a randomly built BST=O(g n) does not necessarily mean that its expected height is also O(g n)(although it is) Example ≤1gn Ave.deph≤1nlgn+nn O(gn) c 2001 by Charles E Leiserson Introduction to Agorithms Day 17 L9.5
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 17 L9.5 Expected tree height But, average node depth of a randomly built BST = O(lg n) does not necessarily mean that its expected height is also O(lg n) (although it is). Example. ≤ lg n h = n (lg ) 2 lg 1 O n n n n n n = ⋅ Ave. depth ≤ ⋅ +