From 45e20a69b88259371e5f0b0a9faf81f910078dca Mon Sep 17 00:00:00 2001 From: lshprung Date: Wed, 27 May 2020 11:11:12 -0700 Subject: Post-class 05/27 --- 05-22.md | 4 ++ 05-27.md | 239 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 243 insertions(+) create mode 100644 05-27.md diff --git a/05-22.md b/05-22.md index 7976495..18695f0 100644 --- a/05-22.md +++ b/05-22.md @@ -136,3 +136,7 @@ |**Add** |O(n) |O(n) |O(n) |O(n) |O(n) |O(h) (log(n) <= h <= n)|O(log(n))| |**Remove** |O(n) |O(n) |O(n) |O(n) |O(n) |O(h) (log(n) <= h <= n)|O(log(n))| |**Min/Max** |O(n) |O(1) |O(m) |O(n) |O(1) (assuming fast access to tail)|O(h) (log(n) <= h <= n)|O(log(n))| + +--- + +[05/27 ->](05-27.md) diff --git a/05-27.md b/05-27.md new file mode 100644 index 0000000..38a2dba --- /dev/null +++ b/05-27.md @@ -0,0 +1,239 @@ +[\<- 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 -- cgit