Post-class 05/27

2 files changed, 243 insertions, 0 deletions

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