{
  "title": "6 February // Lecture 7",
  "cells": [
    {
      "type": "markdown",
      "data": "1. Assignment 2: BST due 17 Feb.\n2. PollEverywhere\n\n>Q: What is the height of the node \"beta\"? (need to see picture)\n>\n>A: 2. Remember, height is the length of longest path from node to a leaf (length is number of links)\n\n>Q: What is the depth of the node \"beta\"? (same image)\n>\n>A: 1. Remember, depth is length of path from root to node\n\n>Q: What is the height of the tree shown? (same image)\n>\n>A: 4. The height of a tree is equivalent to the height of its root node\n\n>Q: Which sequence is an In-Order traversal of the tree shown? (different image)\n>\n>A: delta beta epsilon alpha gamma theta (in order: left, middle, right)\n\n>Q: Which sequence is a Breadth-First traversal of the tree shown? (same as above)\n>\n>A: alpha beta gamma delta epsilon theta (breadth-first: each depth level one at a time)\n\n>Q: Here is a Binary Search Tree. Click on the circle where \"heels\" will go when inserted. (new image)\n>\n>A: Left of iota. Less than Kappa, greater then Gamma, less that iota.\n\n#Binary Search Trees\nSee extra conditions on general binary tree that gives BST from last lecture\nAlso see degenerate case (linked list) from last lecture, which will clearly yield the worst cases\n\nNumber guessing game: random guesses takes $O(n)$ average and worst case. Knowing to guess up or down can reduce to $O(\\log n)$, which for a number $i \\in [1,1000000]$ is $\\approx 20$ steps\n\nThis is a binary search tree. For full tree of height $h$, the number of $nodes = 2^{h+1} - 1$\n\nThe layout of a binary search tree is *also* determined by the order nodes are inserted: bad insert orders can result in less tree-like trees\n\n###ADT: $BST$ of $T$\n\n$new: \\to BST$\n$insert: BST \\times T \\to BST$\n$remove: BST \\times T \\to BST$\n$findMin: BST \\to T$\n$findMax: BST \\to T$\n$contains: BST \\times T \\to Boolean$\n$size: BST \\to Natural$\n$height: BST \\to Natural$\n\n####Contains\nLooking for value $i$ in a binary search tree $b$\n1. Start at the root node $r$ and compare to $i$\n2. Equal:\n  - return true\n3. Less than:\n  - set $r = r.left$ and return to step $1$\n4. Greater than:\n  - set $r = r.right$ and return to step $1$\n5. $r$ is null\n  - return false\n\n####Insert\n(we will exclude duplicates)\nInsert $i$ into $b$\n1. Perform a $contains(i)$ and check result\n2. True: finish\n3. False: Create a new node $n$ and make the end of the path traversed by contains point right or left to $n$\n\n####Remove\nRemove $i$ from $b$\n1. Perform a $contains(i)$ and check the result\n2. True:\n  1. Leaf: unlink it from parent\n  2. One child: parent points to child\n  3. Two children: \n    - findMin $m$ in right subtree $R$\n    - Replace the value of $i$ with the value of $m$\n    - Recursively delete $m$, which will become a one or zero child case (because, as the min, it has no left subtree $L$)\n3. False: finish\n\nBST get more linear as we do more deletes\nVery useful structure for largely static data sets (like lexicons: OED)\n\nBST Depth depends on order of inserts\nConsider inserting 1, then 2, then 3, then 4, then 5, etc. Each node has only one subtree (the right) and insert becomes $O(n)$\nConsider instead inserting 6,2,9,5,1,7,3. We have a relatively balanced tree, so insert is $O(\\log n)$\n\n###Analysis\ninsert: worst $O(n)$, avg: $O(\\log n)$\nremove: worst $O(n)$, avg: $O(\\log n)$\nfindMin: worst $O(n)$, avg: $O(\\log n)$\nfindMax: worst $O(n)$, avg: $O(\\log n)$\ncontains: worst $O(n)$, avg: $O(\\log n)$\nget: worst $O(n)$, avg: $O(\\log n)$\nempty: $O(1)$\nsize: $O(1)$\n\nWorst cases is nearly-ordered data\nAverage is random data"
    }
  ]
}