CS234 Lecture 20: Search Tress.docx

• School: University of Waterloo
• Department: Computer Science
• Course: CS234
• Professor: John- Paul Pretti

Document Summary

Analysis each node is a bstnode element everything in left subtree smaller than root, right subtree bigger than root: search, insert & delete each spend (1) time at each visited node, each visits (h) nodes. Deletions (deleting k: find k, if not in a leaf: swap with successor, next delete from leaf: if two keys in node, just do it if only one key in node: transfer from an immediate sibling (sibling next to each other) if possible, then delete from the node (with two keys) if not possible, then have at least one sibling with only 1 key => fuse with an immediate sibling fusions may lead to repeating this recursively, as you must have at least 2 children in the node you just deleted from. Analysis: wc (h) to search o: insert and delete involve a search, (h) splits/transfers/fusions and (1) time per split/transfer/fusion, thus all 3 operations are (h) .