CSC263H1 Lecture Notes - Lecture 3: Binary Search Tree, Avl Tree, Binary Tree
18 Oct 2017
School
Department
Course
Professor
Document Summary
Csc 263 lecture summary for week 3 winter 2017. Readings: part iii (introduction), sections 12. 1, 12. 2, 12. 3. Sets s where each element x has field x. key -- some totally ordered value. Assumption: keys are distinct -- no two keys the same. Search(s,k): return x in s s. t. x. key = k, or nil if no such x. Insert(s,x): insert x in s; if some y in s has y. key = x. key, replace y by x. Delete(s,x): remove x from s (given _element_ x in s, not just x. key) A: achieved with delete(s,search(s,k)); separates searching phase from. deletion phase, making it possible to analyse each one separately. Q: think of possibilities, from simple to complex. A: note: all complexity measures are worst-case tight bounds. Insert and delete expressed as time required *in addition to* search time. Note: complexity for unsorted data structures applies only when there are no duplicate keys (otherwise, checks must be performed).
