CSE332: Data AbstractionsLecture 6: Dictionaries; Binary Search TreesDan GrossmanSpring 2010Where we areStudying the absolutely essential ADTs of computer science and classic data structures for implementing themADTs so far:1. Stack: push, pop, isEmpty, …2. Queue: enqueue, dequeue, isEmpty, …3. Priority queue: insert, deleteMin, …Next:4. Dictionary (a.k.a. Map): associate keys with values– probably the most common, way more than priority queueSpring 2010 2CSE332: Data AbstractionsThe Dictionary (a.k.a. Map) ADT• Data:– set of (key, value) pairs–keys must be comparable• Operations:– insert(key,value)– find(key)– delete(key)– …• djgDanGrossman…• trobisonTylerRobison…• sandona1BrentSandona…insert(djg, ….)find(trobison)Tyler, Robison, …Will tend to emphasize the keys, don’t forget about the stored valuesSpring 2010 3CSE332: Data AbstractionsComparison: The Set ADTThe Set ADT is like a Dictionary without any values–A key is present or not (no repeats)For find, insert, delete, there is little difference– In dictionary, values are “just along for the ride”–So same data-structure ideas work for dictionaries and setsBut if your Set ADT has other important operations this may not hold– union, intersection, is_subset– notice these are binary operators on setsSpring 2010 4CSE332: Data AbstractionsDictionary data structuresWill spend the next 1.5-2 weeks implementing dictionaries with three different data structures1. AVL trees– Binary search trees with guaranteed balancing2. B-Trees– Also always balanced, but different and shallower3. Hashtables– Not tree-like at allSkipping: Other balanced trees (red-black, splay)But first some applications and less efficient implementations…Spring 2010 5CSE332: Data AbstractionsA Modest Few UsesAny time you want to store information according to some key andbe able to retrieve it efficiently– Lots of programs do that!• Networks: router tables• Operating systems: page tables• Compilers: symbol tables• Databases: dictionaries with other nice properties• Search: inverted indexes, phone directories, …• Biology: genome maps•…Spring 2010 6CSE332: Data AbstractionsSimple implementationsFor dictionary with n key/value pairsinsert find delete• Unsorted linked-list• Unsorted array • Sorted linked list• Sorted arrayWe’ll see a Binary Search Tree (BST) probably does better, but not in the worst case unless we keep it balancedSpring 2010 7CSE332: Data AbstractionsSimple implementationsFor dictionary with n key/value pairsinsert find delete• Unsorted linked-list O(1) O(n) O(n)• Unsorted array O(1) O(n) O(n)• Sorted linked list O(n) O(n) O(n)• Sorted array O(n) O(log n) O(n)We’ll see a Binary Search Tree (BST) probably does better, but not in the worst case unless we keep it balancedSpring 2010 8CSE332: Data AbstractionsLazy DeletionA general technique for making delete as fast as find:– Instead of actually removing the item just mark it deletedPlusses:– Simpler– Can do removals later in batches– If re-added soon thereafter, just unmark the deletionMinuses:– Extra space for the “is-it-deleted” flag– Data structure full of deleted nodes wastes space– find O(log m) time where m is data-structure size (okay)– May complicate other operationsSpring 2010 9CSE332: Data Abstractions10 12 24 30 41 42 44 45 509 8 99998 99Some tree terms (mostly review)• There are many kinds of trees– Every binary tree is a tree– Every list is kind of a tree (think of “next” as the one child)• There are many kinds of binary trees– Every binary min heap is a binary tree– Every binary search tree is a binary tree• A tree can be balanced or not– A balanced tree with n nodes has a height of O(log n) – Different tree data structures have different “balance conditions” to achieve thisSpring 2010 10CSE332: Data AbstractionsBinary Trees• Binary tree is empty or–a root (with data)– a left subtree (maybe empty) – a right subtree (maybe empty) • Representation:ABD ECFHGJIDataright pointerleftpointer• For a dictionary, data will include a key and a valueSpring 2010 11CSE332: Data Abstractions 12Binary Tree: Some NumbersRecall: height of a tree = longest path from root to leaf (count edges)For binary tree of height h:– max # of leaves: – max # of nodes:– min # of leaves:– min # of nodes:Spring 2010 CSE332: Data AbstractionsBinary Trees: Some NumbersRecall: height of a tree = longest path from root to leaf (count edges)For binary tree of height h:– max # of leaves: – max # of nodes:– min # of leaves:– min # of nodes:2h2(h + 1)-11h + 1For n nodes, we cannot do better than O(log n) height, and we want to avoid O(n) heightSpring 2010 13CSE332: Data AbstractionsCalculating heightWhat is the height of a tree with root r?Spring 2010 14CSE332: Data Abstractionsint treeHeight(Node root) {???}Calculating heightWhat is the height of a tree with root r?Spring 2010 15CSE332: Data Abstractionsint treeHeight(Node root) {if(root == null)return -1;return 1 + max(treeHeight(root.left),treeHeight(root.right));}Running time for tree with n nodes: O(n) – single pass over treeNote: non-recursive is painful – need your own stack of pending nodes; much easier to use recursion’s call stackTree TraversalsA traversal is an order for visiting all the nodes of a tree• Pre-order: root, left subtree, right subtree• In-order: left subtree, root, right subtree• Post-order: left subtree, right subtree, root+*2 45(an expression tree)Spring 2010 16CSE332: Data AbstractionsMore on traversalsvoid inOrdertraversal(Node t){if(t != null) {traverse(t.left);process(t.element);traverse(t.right);}}Sometimes order doesn’t matter• Example: sum all elementsSometimes order matters• Example: print tree with parent above indented children (pre-order)• Example: evaluate an expression tree (post-order)ABDECFGABD ECF GSpring 2010 17CSE332: Data AbstractionsBinary Search Tree4121062115814137 9• Structural property (“binary”)– each node has ≤ 2 children– result: keeps operations simple• Order property– all keys in left subtree smallerthan node’s key– all keys in right subtree largerthan node’s key– result: easy to find any given keySpring 2010 18CSE332: Data AbstractionsAre these