Post-class 05/22

7 files changed, 142 insertions, 0 deletions

diff --git a/05-18.md b/05-18.md
index d183631..b0f402c 100644
--- a/05-18.md
+++ b/05-18.md
@@ -137,3 +137,7 @@ NODE *mknode(int data, NODE *left, NODE *right){
 	- `addEntry(pq, np);`
 
 4. print 
+
+---
+
+[05/22 ->](05-22.md)
diff --git a/05-22.md b/05-22.md
new file mode 100644
index 0000000..7976495
--- /dev/null
+++ b/05-22.md
@@ -0,0 +1,138 @@
+[\<- 05/18](05-18.md)
+
+---
+
+## A Question
+
+![bad tree](05-22_img1.png)
+
+- How many tests do we need to do in order to locate node 52?
+- This tree was made with an array of values in sorted order and has a big-O of O(n) (bad!)
+- How can we make it easier to traverse?
+
+## AVL Tree Definition
+
+- An AVL tree is a binary search tree in which **the heights of the subtrees of any given node differ by no more than 1**
+- It is a **balanced binary search tree**
+- An AVL tree is a binary tree that either is empty or consists of two AVL subtrees, Tl and Tr, whose heights differ by no more than 1
+	- `|Hl - Hr| <= 1`
+
+- What are the possible values for balance factor of an AVL tree?
+	- 0, -1, 1
+
+## An Example
+
+1. Check the value - BST
+2. Check the shape - Balanced binary tree
+	- For each node, we use
+		- LH to indicate that the left subtree is higher than the right subtree
+		- RH to indicate that the left subtree is shorter than the right subtree
+		- EH to indicate that the subtrees are the same height
+
+![example tree](05-22_img2.png)
+
+- Is this an AVL tree?
+
+## AVL Tree - Operations
+
+- The **search** and **traversal** of AVL tree is the same as BST
+	- What is the worst-case big-O run time for AVL tree search? O(log(n))
+		- Remember worst-case big-O of BST was O(n)
+- How about **insertion** & **deletion**
+	- They are different
+	- Why?
+		- AVL tree is a balanced tree, while insertion/deletion may **make it unbalanced**
+
+## AVL Tree - Insertion/Deletion
+
+- We can consider insertion as two steps
+	- Insert the node at a leaf/leaflike node - (**the same as BST insertion**)
+	- **Back out** of the tree and balance each node
+- We consider deletion as two steps
+	- Delete the node - (**the same as BST deletion**)
+	- **Back out** of the tree and balance each node
+
+- Example:
+
+![example](05-22_img3.png)
+
+- After inserting 8, 12 is LH, but 18 is too uneven
+
+# How to do Balance?
+
+## Four Cases for Rebalancing
+
+1. Left of Left -> Rotate right
+2. Right of Right -> Rotate left
+3. Right of Left -> Rotate parent right, child left
+4. Left of Right -> Rotate parent left, child right
+
+- First two cases require one rotation, last two cases require two rotations
+
+## Meaning of Rotations
+
+- Rotate to the left
+	- Your **original right child** becomes your parent
+	- After rotation, you are the left child of your parent
+	- If your new parent originally had a **left child**, you need to take it as your child
+
+- Rotate to the right
+	- Your **original left child** becomes your parent
+	- After rotations, you are **the right child** of your parent
+	- If your new parent originally had a **right child**, you need to take it as your child
+
+## Summaries
+
+- Starting from the newly inserted/deleted node, go back to the root of the entire tree. Along the path, calculate balance factor for each node and rebalance the unbalanced nodes **one by one** through rotations. (**The order matters!**)
+
+- For each unbalanced node:
+	1. Identify it as one of the four cases (i.e. left-of-left, right-of-right, left-of-right, right-of-left) by checking itself and its higher subtree. For example, if an unbalanced node is LH, the case if left-of-left
+	2. Rotate nodes accordingly
+	3. Back out to handle another unbalanced node if there's any
+
+## Exercise I - Complex Rotation
+
+![example 1](05-22_img4.png)
+
+- Left of Left
+- We only need to look at the left side
+- We need to rotate to the right to reblanace
+
+## AVL Tree Insertion practice
+
+- Let's take some arbitrary numbers and let's insert them into an AVL tree
+
+![example](05-22_img5.png)
+
+- Don't be concerned about the costs of rotation: the only thing that's changing is pointers
+
+- Another example (recommended to draw the tree as we describe it):
+	- Let's insert 8, 6, 7, 5, 2
+	- Insert 8 as root
+	- Insert 6 as left child of 8
+	- insert 7 as right child of 6
+		- Now the tree is unbalanced (right-of-left)
+		- First, rotate 6 to get 8 -> 7 -> 6
+		- Now the tree is left-of-left, so we just rotate the root right
+		- Now 7 is the root, 6 is the left child, 8 is the right child
+	- insert 5 as the left child of 6
+	- insert 3 as the left child of 5
+		- Now the tree is unbalanced (left-of-left)
+		- Rotate the root (7) to the right
+		- Now 6 is the root, 5 is the left child, 3 is 5s left child, 7 is the right child, 8 is 7s right child
+
+## AVL Deletion
+
+- Delete the specified node, then rebalance the tree if necessary
+- Remember that deleting a parent involves a bit of cleaning (like with a BST)
+
+[website to visualize AVL Trees](https://www.cs.usfca.edu/~galles/visualization/AVLtree.html)
+
+---
+
+|SET            |Unsorted Array|Sorted Array|Hash Table|Unsorted Linked List|Sorted Linked List                 |BST                    |AVL Tree|
+|---------------|--------------|------------|----------|--------------------|-----------------------------------|-----------------------|--------|
+|**Search/Find**|O(n)          |O(log(n))   |O(n)      |O(n)                |O(n)                               |O(h) (log(n) <= h <= n)|O(log(n))|
+|**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))|
diff --git a/05-22_img1.png b/05-22_img1.png
new file mode 100644
index 0000000..151e995
--- /dev/null
+++ b/05-22_img1.png
diff --git a/05-22_img2.png b/05-22_img2.png
new file mode 100644
index 0000000..0c1833d
--- /dev/null
+++ b/05-22_img2.png
diff --git a/05-22_img3.png b/05-22_img3.png
new file mode 100644
index 0000000..9cddf7f
--- /dev/null
+++ b/05-22_img3.png
diff --git a/05-22_img4.png b/05-22_img4.png
new file mode 100644
index 0000000..a8ce310
--- /dev/null
+++ b/05-22_img4.png
diff --git a/05-22_img5.png b/05-22_img5.png
new file mode 100644
index 0000000..ff8ca83
--- /dev/null
+++ b/05-22_img5.png