CS 1332 Lecture Notes - Lecture 9: Subset
19 Feb 2019
School
Department
Course
Professor
Document Summary
Is a proper subset of bsts but now a bit more robust. Left < parent < right order is still enforced. Balance factor = height lchild - height rchild. Bf can differ by at most 1 (so can be -1 or 1) Bf is positive left heavy right rotation. Bf is negative right heavy left rotation. Update methods: you have to update the height and balance factor once you rotate. Anything below the node doesn"t change, anything from the node and up changes. Stop updating when there is no change to balance factor or height. So it"s right heavy (negative bf) so we have to do a single left rotation a b x b y z a z x y. Everything to the left of b is smaller, everything to the right of b is larger. Redirect a"s right child to b"s left child. Redirect b so that b is the parent of a.
