CSC263H1- Final Exam Guide - Comprehensive Notes for the exam ( 28 pages long!)
Document Summary
Please follow the instructions provided on the course website to submit your assignment. We augment the nodes with two values: sum (the total sum of the keys in the subtree) and size (the number of items in the subtree). Average simply returns root. sum/root. size which takes o(1) time. (c) explain why search, i nsert, and delete can still be performed in o(lg n) time. Given t , x and y, write an algorithm to nd the set of elements in t with key values in [x, y] . The time complexity of your algorithm should be o(h + k) where h is the height of the tree and k is the number of elements within the range. The rst while loop walks down from the root to nd the smallest subtree that contains all the elements within the range. The loop invariant is that the subtree rooted at z contains all the elements within the range.
