Sing, Pray Announcements =============== * 3 extra points will be awarded for making your code Checkstyle compliant on the last two projects (AVL and Hashing). Full credit will be given otherwise. Furthermore, no more than 3 extra points will be awarded for any single project (e.g., you cannot get more than 103 points even if you turn in early). That being said, I encourage you to continue to follow the Checkstyle guidelines as they will help you to produce clean and manageable code, which becomes increasingly important as the size of your coding projects grow. Eclipse tips AVL Project Tips ---------------- * Adapt the code from the lecture notes (e.g., add, remove, rotations) - Tree operations are often recursive and can return a tree node * Go to a Help Session - Help session today at 2:00pm (John) - Help session on Monday at 11:00am on AVL Project (Kamis) Outline =========================== * Review * AVL Applet examples * Group-work: discuss AVL implementation notes together * Discuss AVL Implementation notes together Review =========================== Important Tree Properties BST Order Property: In a binary search tree, for every node X, all keys in X's left subtree have smaller values than the key in X, and all keys in X's right subtree have larger values tha the key X. AVL Balance Property: For any node in the tree, the height of the left and right subtrees can differ by at most 1. (As usual, the height of an empty subtree is -1.) Why do we wish to keep the tree balanced? How do we know if we need to re-balance the tree? If we fix the balance at the deepest unbalanced node, we rebalance the entire tree. There are four cases that we might have to fix; two are mirror images of the other two. How do we know if we should do a single or double rotation? Check to see which case it is: 1. left > right, left-left > left-right (Solution: Single Right Rotation) 2. left > right, left-left < left-right (Solution: Double Right Rotation) 3. right > left, right-right < right-left (Solution: Double Left Rotation) 4. right > left, right-right > right-left (Solution: Single Left Rotation) AVL (Adelson-Velskii and Landis) Trees ---------------------------------------- An AVL tree is a BST with the additional balance property (see above) Every node in an AVL tree has subtrees whose heights differ by at most 1. Any empty subtree has height -1. The AVL tree has height at most roughly 44 percent greater than the minimum The depth of a typical node in an AVL tree is close to the optimal log N. An update (e.g., add or remove) in an AVL tree could destroy the balance. It must then be rebalanced before the operation can be considered complete. Only nodes on the path from the root to the insertion point can have their balances altered. If we fix the balance at the deepest unbalanced node, we rebalance the entire tree. There are four cases that we might have to fix; two are mirror images of the other two. Balance is restored by tree rotations. A single rotation switches the roles of the parent and child while maintaining the search order.