[\<- 05/22](05-22.md) --- ## Just One of Many - Today we will go over AVL tree insertion and deletion - The best way to learn AVL trees: practice, practice, practice! - AVL trees are just one type of balanced search tree: - Red-Black trees (not as strict as AVL); - Splay trees (change tree on search as well); - 2-3 trees (2 or 3 children per node); - B-trees (generalization of 2-3 trees); - B+ trees (a B-tree on disk in which full data is stored only in the leaves, which are linked together as a linked list) ## Coding - Coding a BST isn't that bad - Coding an AVL tree is much harder ## Not Just Numbers - Students always ask why are we inserting numbers into a BST? - In reality the number is just a key that identifies a much larger piece of data - The key might be your student ID number, which identifies your student record - We can use strings (just like in a hash table) on a search tree as easily as we can use numbers - We'll have fun with some strings today # Examples ## Example 1 Insert 8, 6, 7, 5, 3, 0, 9 - Insert 8 - 8 is the root - Insert 6 - 6 is less than 8, so it becomes the left child - 6 is even, 8 is left high - Insert 7 - 7 is less than 8, and higher than 6, so 7 becomes the right child of 6 - Now 8 is unbalanced - Rotate 6 left: now the tree is root 8, 7 is the left child, 6 is the left child of 7 - Rotate 8 right: now 7 is the root, 6 is the left child, 8 is the right child - Insert 5 - 5 is less than 7 and less than 6, so 5 becomes the left child of 6 - 6 and 7 are left high, the other nodes are even - Insert 3 - 3 is less than 7, less than 6, and less than 5, so it becomes the left child of 5 - 6 and 7 are unbalanced - Rotate 6 right: Now 7 is the root, 8 is the right child, 5 is the left child, 3 is the left child of 5, 6 is the right child of 5 - Insert 0 - 0 is less than 7, less than 5, less than 3, so it becomes the left child of 3 - Now the root is unbalanced - Rotate 7 (the root) right: Now, 5 is the root, 3 is the left child, 0 is the left child of 3, 7 is the right child of the root, 6 is the left child of 7, 8 is the left child of 7 - Insert 9 - 9 is greater than 5, greater than 7, greater than 8, so it becomes the right child of 8. - 5, 7, and 8 are right high - Resulting Tree Stats: - Height = 4 - Root = 5 - Leaves = {0, 6, 9} - Single Rotations = 2 - Double Rotations = 1 - Possible scenarios - Inserting 4 -> no rotation - Inserting 10 -> single rotation - Inserting 2 -> double rotation ## Example 2 - We have a tree: - 5 is the root - 3 is the left child - 0 is the left child - 7 is the right child - 6 is the left child - 8 is the right child - 9 is the right child - Delete 3: The resulting tree is: - 5 is the root - 0 is the left child - 7 is the right subchild - 6 is the left subchild - 8 is the right subchild - 9 is the right subchild - The tree is right of right: 5 needs to be rotated left - 7 is the root - 5 is the left child - 0 is the left child - 6 is the right child - 8 is the right child - 9 is the right child - Delete 9: The resulting tree is: - 7 is the root - 5 is the left child - 0 is the left child - 6 is the right child - 8 is the right child - The emphasis will be on insertion, but it is good to practice deletion regardless ## Example 3 - Insert: 10, 20, 30, 40, 50, 60, 70 - This is a worst case for a BST, but not for an AVL tree! - Insert 10: The resulting tree is: - 10 is the root - Insert 20: The resulting tree is: - 10 is the root - 20 is the right child - Insert 30: The resulting tree is: - 10 is the root - 20 is the right child - 30 is the right child - The tree is right of right: rotate 10 left: - 20 is the root - 10 is the left child - 30 is the right child - Insert 40: the resultign tree is: - 20 is the root - 10 is the left child - 30 is the right child - 40 is the right child - Insert 50: the resultign tree is: - 20 is the root - 10 is the left child - 30 is the right child - 40 is the right child - 50 is the right child - The tree is right of right: rotate 30 left: - 20 is the root - 10 is the left child - 40 is the right child - 30 is the left child - 50 is the right child - etc. ## Example 4: With Words! - Insert dog, cat, bat, fox, elk, gnu, ant - Insert dog: - "dog" is the root - Insert cat: - "dog" is the root - "cat" is the left child - Insert bat: - "dog" is the root - "cat" is the left child - "bat" is the left child - The root is left of left: rotate "dog" right: - "cat" is the root - "bat" is the left child - "dog" is the right child - Insert fox: - "cat" is the root - "bat" is the left child - "dog" is the right child - "fox" is the right child - Insert elk: - "cat" is the root - "bat" is the left child - "dog" is the right child - "fox" is the right child - "elk" is the left child - "dog" is left of right - first rotate "fox" right, then rotate "dog" left - "cat" is the root - "bat" is the left child - "elk" is the right child - "dog" is the left child - "fox" is the right child - Insert gnu: - "cat" is the root - "bat" is the left child - "elk" is the right child - "dog" is the left child - "fox" is the right child - "gnu" is the right child - the root is right of right: rotate "cat" left: - "elk" is the root - "cat" is the left child - "bat" is the left child - "dog" is the right child - "fox" is the right child - "gnu" is the right child - etc. ## Example 5: The Mammoth Example - Insert doe, emu, gar, fly, boa, cow, sow, jay, hog, yak, lar, nit, ass, owl, pug, rat, man - Try this on your own. I will only write out one guide to constructing the tree (as opposed to rewriting each time a new entry is added - "jay" is the root - emu" is the left child - "cow" is the left child - "boa" is the left child - "ass" is the left child - "doe" is the right child - "gar" is the right child - "fly" is the left child - "hog" is the right child - "sow" is the right child - "lar" is the left child - "nit" is the right child - "yak" is the right child - This is the AVL tree with most of the entries. Try adding the rest yourself --- [05/29 ->](05-29.md)