From 5d742b7d953c5b9ac874e64c1a8836ced51d772f Mon Sep 17 00:00:00 2001 From: lshprung Date: Fri, 22 May 2020 10:59:41 -0700 Subject: Post-class 05/22 --- 05-22.md | 138 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 138 insertions(+) create mode 100644 05-22.md (limited to '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))| -- cgit