CSE 214 Computer Science II (Spring 2015)

RECITATION 11 – Heap and Binary Search Tree

Objective:

  1. To study operations on AVL Tree

2.   To study Sorting Algorithms

 

  1. [15 min]  For the following list, insert the keys in the order shown below to build them into an AVL tree. Draw an AVL tree after each insertion step.

      

    Key ={65, 90, 66, 89, 67, 88, 68, 87, 69, 86, 70}

Show the deletion of keys: 70, 86, 69 and 87

 

  1. [10 min] Table of Time Complexities

Fill in the following table giving the best/worst case order of complexity for the following sorting algorithms. Briefly describe when these cases occur.

Sorting Algorithm Best Case Complexity Worst Case Complexity
Bubble    
Selection    
Merge    
Quick    
Radix    

                                                                                 

  1.  [20 minutes] Selection Sort, Insertion Sort, Quick Sort, Merge Sort

Simulate the four types of sorts using the following array:

                                               {3, 7, 1, 4, 2, 5, 8, 6}

 

  1. [5 min]  Comment on the running time nature of Quick Sork, given the list is already sorted and the selection of pivot index is (a) First position (b) Last position (c) Mid position of list.