CSC301.01 2015F, Class 11: Binary Search Trees ============================================== _Overview_ * Preliminaries. * Admin. * Upcoming Work. * Extra Credit. * Questions. * Trees, Formalized. * Terminology. * Binary Trees. * Traversing Trees. * Binary Search Trees. * Balancing Binary Search Trees. Preliminaries ------------- ### Admin ### Upcoming Work * For Wednesday: HW 3a Implement chained/bucketed hash tables * In Scheme * With strings as keys * An arbitrary values as values * That grow when more than 50% full * And support `add`, `remove`, and `find`. * And use the Skiena "sum of powers" for the hash function * Ideally, parameterize the "constructor" to allow changing some of these policies. * Ideally, with unit tests. * For Wednesday: HW 3b Design `SetOfStrings` Implementations * A `SetOfStrings` ADT provides * `add(set,val)`, `remove(set,val)`, `contains(set,val)` * `union(set,set)`, `subtract(set,set)` * Describe three different reasonable implementations of `SetofStrings`. (You need not write code; just describe memory arrangement and related issues.) * For each, indicate the asymptotic cost of each method. In writing this, reflect on both the size of the set (*n*,*m*) and the size of the string (*s*). * This is an informal analysis question; no proofs necessary ### Extra Credit #### Academic * John Gerrard talk, "Corn Bomb", Monday at 8pm in the Gallery. * No CS Table next week - It's advising week! * Wednesday CS Extra, 4:15 in 3821: Ursula Wolz on Building Coding Communities * Thursday CS Extra, 4:15 in 3821: SamR on The Architecture of Mediascript #### Peer * Monday 7-10 Sound Art Projects in JRC * EE Show in Smith started! * Soccer matches Saturday, women at 11, men at 1:30 * Orchestra concert Saturday, 2:00 in S-L. * Jazz concert Saturday, 7:30 in S-L. ### Questions _How do I change the size of my vector?_ > I'd recommend that you build your hash tables as four element vectors (size, capacity, alpha, vector of lists). That way, when you expand them, you're just setting one element of the enclosing vector. _Do values have to move when we expand the hash table?_ > Almost certainly. _What will our code look like?_ > `(vector-set hash-table 3 (expand-vector (vector-ref hash-table 3))` > `(vector-set hash-table 0 (vector-length (vector-ref hash-table 3))` > `(define expand-vector ...)` _Do we have to write code to implement `SetOfStrings`?_ > No. Your goal is to consider various options for implementing them and assess their relative efficacy. Trees, Formalized ----------------- Small group task: Describe trees formally. * A graph with no cycles is a forrrrest * A connected graph with no cycles is a tree * A recursive/structural definition * null is a tree * If T1 and T2 are trees, node(val,T1,T2) is a tree * A tree is a three-tuple * V, a finite set of values * r, a designated element of V * child, a binary relation between elements of V (a binary relation is a set of ordered pairs of the form ) * With some restrictions * For any v in V not equal to r, exists exactly one p s.t. is in child * Exists a c s.t. is in child. This somewhat mathematical representation serves multiple purposes * It reminds us that children are not always ordered. * Ordered trees are a separate an important data type * It reminds us that trees are not always binary * It reminds us that there are multiple ways to implement trees. For ordered trees, we add an i (in the natural numbers) to the child relationship, form , for "c is the ith child of p" * We may also add a restriction that if we have an ith child, with i>0, then we also have an i-1st child. Terminology ----------- Small group task: Think about what each of these terms means. Be prepared with a definition. (Your definitions can be formal or informal.) * *Root*: * *Leaf*: * *Parent*: * *Child*: * *Path*: * *Depth*: Length of shortest path from root to that node * *Height*: Length of shortest path to furthest descendent * height(leaf) = 0 * height(nonleaf) 1 + max(depth(children)) * *Level*: Another name for depth * *Descendent*: * *Forest*: * *Ancestor*: Binary Trees ------------ Binary trees are ordered trees in which no parent has more than two children (only valid indices are 0 and 1) without the requirement that having child 1 requires you to have child 0. Traversing Trees ---------------- When talking about traversal, we focus on when we *process* a value in the tree. We may visit the values in a slightly different order. * Breadth-first vs. depth first. * DF: Process one subtree (all the descendeants) before processing the other subtrees * Recursion! visit(node) process(node) for each child, c, of node visit(c) * Iteration! Stack * BF: Process all of the values on one level before visiting the next level * Iteration! Use a queue * Preorder vs. postorder vs. inorder. * Left-to-right vs. right-to-left. Binary Search Trees ------------------- Binary trees in which all the values in the left subtree are less than (or equal to) the node, which is less than (or equal to0 all the values in the right subtree In general, searcing in a binary search tree is O(height) A binary tree with N nodes can have height O(logn), so this can be fast. Can we balance our trees? Let's go for "almost balanced" - the height of subtrees shall not differ by more than 1. Balancing Binary Search Trees ----------------------------- See white board. (They are probably in my outline, too.)