CS 3345: Data Structures and Algorithms - Homework 5 1. Show the red-black trees after successively inserting the keys 43, 39, 32, 13, 19,9,20 into and initially empty red-black tree. Show all steps. 2. Show the red-black trees that result from the successive deletion of the keys in the order 25, 50, 75, 99. Show all steps. 3. Fil in the blanks: Amortized Analysis is used for algorithms where an occasional operation is very slow, but most of the other operations are faster In Amortized Analysis, we analyze a sequence of operations and guarantee a worst case average time which is lower than the worst case time of a particular expensive operation. In computer science, amortized analysis is a method for analyzing a given algorithm's time complexity, or how much of a memory, it takes to execute 50 100 25 75 resource, time or Asymptotic analysis is input bound i.e., if there's no input to the algorithm, it is concluded to work in a constant time. Other than the "input" all other factors are considered constant. Asymptotic analysis refers to computing the running time of any operation in mathematical units of computation. In the worst case, a red-black tree insertion requires In the worst case a red-black tree deletion requires Walking a red-black tree with n nodes in pre-order takes Given a red-black tree with n elements, how fast can you sort them using the tree? a. rotations? b. node re-colorings? c. time? d. e. How fast can we build a red-black tree with n elements? f. Ifa data structure supports an operation X such that a sequence of n X's operations take: O (n log n) time in the worst case, then the amortized time of an X operation is 6( ) while the actual time of a single X operation could be as low as 6( ) and as high ais ( )