AVL Trees in Data Structures

• The lecture is about Data Structures and Algorithms specifically AVL Trees
• Homework PS4 will be released Feb 12 15:15, and due Feb 18 23:59
• Scapegoat Trees should be implemented, with caution

Todays Plan

• Cover height-balanced binary search trees, AVL trees, Rotations, Insertion and Deletion

Recap: Dictionary Interface

• A dictionary interface has key and value pairs
• insert(Key k, Value v) inserts the key and value into a table
• search(Key k) gets the value paired with the key
• successor(Key k) finds the next key which is greater than k
• predecessor(Key k) finds the next key which is less than k
• delete(Key k) removes the key and value
• contains(Key k) indicates there is a value for key k or not
• size() states the number of key and value pairs

Recap: Binary Search Trees

• Binary search trees have two children: v.left, and v.right
• The key is represented as v.key
• BST Property is such that all in left sub-tree < key < all in right sub-tree

Binary Search Tree

• Modifying operations such as insert and delete, take O(h) time
• Query operations such as search, predecessor, successor, findMax, and findMin take O(h) time
• Traversals take O(n) time

The Importance of Being Balanced

• Operations take O(h) time where log(n) −1 ≤ h ≤ n
• A BST is balanced if h = O(log n)
• All operations on a balanced BST run in O(log n) time

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.
• Invariant, after every insert/delete, the good property still holds, if not, fix it

AVL Trees

• AVL Trees were developed by Adelson-Velskii & Landis in 1962
• A node v is height-balanced if: |v.left.height – v.right.height| ≤ 1
• A height-balanced tree with n nodes has at most height h < 2log(n)
• A height-balanced tree is balanced

Inserting in an AVL Tree

• Starting initially balanced, after doing an insert the tree is no longer balanced
• Rotations are used to rebalance

Tree Rotations

• Rotation costs O(1)
• Rotations maintain the ordering of keys
• Rotations maintains the BST property

Tree Rotations (Left and Right Heavy)

• After inserting into the tree rotations are employed to restore balance
• The height is out-of-balance by 1 node
• Tree rotations should be used to restore balance
• After inserting, start at the bottom and work up the tree
• A is LEFT-heavy if the left sub-tree has larger height than the right sub-tree.
• A is RIGHT-heavy if the right sub-tree has larger height than the left sub-tree

A is the lowest node in the tree violating the balance property.

• Assume A is LEFT-heavy
• Case 1: B is equi-height: h(L) = h(M) where h(R) = h(M) – 1, and a right-rotate is needed
• Case 2: B is left-heavy : h(L) = h(M) + 1 where h(R) = h(M), and a right-rotate is needed
• Case 3: B is right-heavy : h(L) = h(M) - 1 where h(R) = h(L), and a right-rotate is needed

Rotations Summary

• v is out of balance and left heavy
• v.left is balanced: right-rotate(v)
• v.left is left-heavy: right-rotate(v)
• v.left is right-heavy: left-rotate(v.left) then right-rotate(v)
• If v is out of balance and right heavy, the case is symmetric

Multiple Rotations

• In the worst case, two rotations are needed after an insertion
• After insert, the insert increases heights by 1
• Rotation reduces root height by 1, everything higher in the tree is unchanged
• Rotation does not reduce the height for case 1: B is balanced
• Case 1 is needed for deletes

Insert in AVL Tree

• Insert the key in BST
• Walk up the tree, at every step, check for balance
• If out-of-balance, use rotations to rebalance and return
• Can only fix the the lowest out-of-balance node
• Only need at most two rotations to fix

Binary Search Tree Deletion

• Three Cases for removal:
• No children
• 1 child
• 2 children
• If v has two children, swap v with its successor
• Delete node v from binary tree and reconnect children
• For every ancestor of the deleted node:
• Check if it is height-balanced.
• If not, perform a rotation.
• Continue to the root.
• Deletion may take up to O(log(n)) rotations

Delete in AVL Tree

• Delete key from BST
• Walk up tree
• At every step, check for balance
• If out-of-balance, use rotations to rebalance
• Continue to root
• It is not sufficient to only fix the lowest out-of-balance node in tree
• Deletion reduces height
• Rotations to rebalance also reduce height
• Rebalancing does not "undo" the change in height caused by deletion

AVL Trees: Other potential modifications

• Mark a node "deleted" and leave it in the tree for logical deletes
• Performance degrades over time and cleanup is needed later for Amortized performance
• Only store the difference in height from parent, to avoid storing the height in every node

Next Week

• More Trees and Other Augmentations
• Examples of other forms of trees
• Introduction to hashing