AVL Trees Data Structures PDF

CS2040S Data Structures and Algorithms AVL Trees Puzzle of the Week: 100 prisoners. Every so often, one is chosen at random to enter a room with a light bulb. You can turn the light bulb on or off. WIN if one prisoner announces correctly that all have visited the room. LOSE if announcemen...

CS2040S Data Structures and Algorithms AVL Trees Puzzle of the Week: 100 prisoners. Every so often, one is chosen at random to enter a room with a light bulb. You can turn the light bulb on or off. WIN if one prisoner announces correctly that all have visited the room. LOSE if announcement is incorrect. What if, initially, the state of the light is unknown, either on or off? Housekeeping PS4 Release 12 Feb 15:15 - Due: 18 Feb 23:59 Implement Scapegoat Trees! - Beware: “It’s easy to introduce bugs” - One of your TAs Take care to make sure you’re careful when implementing it. Todays Plan On the importance of being balanced – Height-balanced binary search trees – AVL trees – Rotations – Insertion Recap – Deletion Recap: Dictionary Interface A collection of (key, value) pairs: interface IDictionary void insert(Key k, Value v) insert (k,v) into table Value search(Key k) get value paired with k Key successor(Key k) find next key > k Key predecessor(Key k) find next key < k void delete(Key k) remove key k (and value) boolean contains(Key k) is there a value for k? int size() number of (k,v) pairs Recap: Binary Search Trees 41 20 65 11 29 50 91 – Two children: v.left, v.right – Key: v.key – BST Property: all in left sub-tree < key < all in right sub-tree Binary Search Tree Modifying Operations: O(h) – insert – delete Query Operations: O(h) – search – predecessor, successor – findMax, findMin Traversals: O(n) The Importance of Being Balanced Operations take O(h) time log(n) –1 ≤ h ≤ n A BST is balanced if h = O(log n) On a balanced BST: all operations run in O(log n) time. The Importance of Being Balanced How to get a balanced tree: – Define a good property of a tree. – Show that if the good property holds, then the tree is balanced. – After every insert/delete, make sure the good property still holds. If not, fix it. AVL Trees [Adelson-Velskii & Landis 1962] AVL Trees [Adelson-Velskii & Landis 1962] Step 1: Define Invariant – A node v is height-balanced if: |v.left.height – v.right.height| ≤ 1 v k k-1 Height-Balanced Trees Theorem: A height-balanced tree with n nodes has at most height h < 2log(n). 🡺🡺 A height-balanced tree is balanced. AVL Trees [Adelson-Velskii & Landis 1962] Step 2: Show how to maintain height-balance 41 k k-1 Inserting in an AVL Tree Initially balanced 41 insert(37) 20 65 11 29 50 91 No longer balanced after insertion! 32 72 99 Use rotations to rebalance! 37 Quick review: a rotation costs: 1. O(1) 2. O(log n) 3. O(n) 4. O(n2) 5. O(2n) Tree Rotations B D Right Rotation D B A C E A C E A