CSC263H1 Lecture 12: Lecture 12.docx
22 Apr 2014
School
Department
Course
Professor
Document Summary
Cost of find(z) = o(length of findpath z root) L: with wu(by size) any tree t of height h created during the execution of has at least 2^h nodes. Proof: by induction on h: h = 0. Any tree t of height h = 0 has at least 2^0 = 1 node (*: suppose (*) holds for h [i. h] We show (*) holds for h + 1. Consider the moment a tree t of height h + 1 is created during the execution of . T was created by attaching a tree a of height h. to tree b: by i. h. , |a| 2^h, by wu |b| |a| 2^h. |t| = |a| + |b} 2^h + 2^h = 2^(h+1) => wu rule: wc cost of is o(n(unions) + m*logn(finds))
