CSC148H5 Lecture Notes - Lecture 21: Init, If And Only If, Binary Search Tree
28 Feb 2017
School
Department
Course
Professor
Document Summary
Csc148h5s - introduction to computer science (winter 2017) If your utorid starts with a to s, go to ib110. If your utorid starts with t to z, go to ib245. Question 1: consider each of the following orders of insertion into an empty bst. Which one results in the tree where searches are fastest: 1, 2, 3, 4, 5, 6, 7, 7, 6, 5, 4, 3, 2, 1, 3, 2, 1, 7, 6, 5, 4. Claim 1: time taken to search depends on the height of the bst. Claim 2: when you insert some value v, it becomes a leaf of the bst. True: insertion only happens when you fall off the tree. Claim 3: different insertion orders determine the shape and height of the tree. Suppose that we insert in this order: 1, 2, 3, 4, 5, 6, 7, . Here"s a better insertion order: 3, 6, 2, 5, 4, If not, explain why not and fix the algorithm.
