MATH 114 Final: MATH 114 UPenn 07cMath114FinalExam Exam
Document Summary
Recall the de nition of generic binary trees and the bst insert and lookup functions: type "a tree = let rec lookup (x: "a) (t: "a tree) : bool = | node of "a tree * "a * "a tree let rec insert (t:"a tree) (n:"a) : "a tree = begin match t with. | node(lt, x, rt) -> if x = n then t else if n < x then node (insert lt n, x, rt) else node(lt, x, insert rt n) end begin match t with. | hd::tl -> insert_list tl (insert hd t) end let big_tree : int tree = insert_list a_million_ints empty. Answer: a randomly-ordered list would perform better because a sorted list creates a skewed, list-like tree, so the bst search would not be able to prune the search space. Grading scheme: 2 points for correctly identifying random , 3 points for the explanation, 2 or 3 points for almost correct other explanations.
