Hash TablesPrefix TreesCS 311 Data Structures and AlgorithmsLecture SlidesMonday, November 30, 2009Glenn G. ChappellDepartment of Computer ScienceUniversity of Alaska [email protected]© 2005–2009 Glenn G. Chappellcontinued30 Nov 2009 CS 311 Fall 2009 2ReviewWhere Are We? — The Big ProblemOur problem for much of the rest of the semester: Store: a collection of data items, all of the same type. Operations: Access items [one item: retrieve/find, all items: traverse]. Add new item [insert]. Eliminate existing item [delete]. All this needs to be efficient in both time and space.A solution to this problem is a container.Generic containers: those in which client code can specify the type of data stored.30 Nov 2009 CS 311 Fall 2009 3Unit OverviewTables & Priority QueuesMajor Topics Introduction to Tables Priority Queues Binary Heap algorithms Heaps & Priority Queues in the C++ STL 2-3 Trees Other balanced search trees Hash Tables Prefix Trees Tables in various languagesIdea #1: Restricted TableIdea #2: Keep a Tree BalancedIdea #3: “Magic Functions”Lots of lousy implementations(part)30 Nov 2009 CS 311 Fall 2009 4ReviewIntroduction to TablesIdea #1: Restricted Table Perhaps we can do better if we do not implement a Table in its full generality.Idea #2: Keep a Tree Balanced Balanced Binary Search Trees look good, but how to keep them balanced efficiently?Idea #3: “Magic Functions” Use an unsorted array of key-data pairs. Allow array items to be marked as “empty”. Have a “magic function” that tells the index of an item. Retrieve/insert/delete in constant time? (Actually no, but this is still a worthwhile idea.)We will look at what results from these ideas: From idea #1: Priority Queues From idea #2: Balanced search trees (2-3 Trees, Red-Black Trees, B-Trees, etc.) From idea #3: Hash TablesLinearLinearLinearBinarySearch TreeLinearConstantLinearUnsortedLinked ListLinearLinearLinearSortedLinked ListLogarithmicLogarithmicLogarithmicBalanced (how?)BinarySearch TreeConstant???LinearInsertLinearLinearDeleteLinearLogarithmicRetrieveUnsortedArraySortedArray30 Nov 2009 CS 311 Fall 2009 5Overview of Advanced Table ImplementationsWe will cover the following advanced Table implementations. Balanced Search Trees Binary Search Trees are hard to keep balanced, so to make things easier we allow more than 2 children: 2-3 Tree Up to 3 children 2-3-4 Tree Up to 4 children Red-Black Tree Binary-tree representation of a 2-3-4 tree Or back up and try a balanced Binary Tree again: AVL Tree Alternatively, forget about trees entirely: Hash Tables Finally, “the Radix Sort of Table implementations”: Prefix Tree(part)30 Nov 2009 CS 311 Fall 2009 6Review2-3 Trees [1/4]A Binary-Search-Tree style node is a 2-node. This is a node with 2 subtrees and 1 data item. The item’s value lies between the values in the two subtrees.In a “2-3 Tree” we also allow a node to be a 3-node. This is a node with 3 subtrees and 2 data items. Each of the 2 data items has a value that lies betweenthe values in the corresponding pair of consecutive subtrees.Later, we will look at “2-3-4 trees”, which can also have 4-nodes.2-node10·≤10 10≤·3 93-node3≤·≤9 9≤··≤32 54-node5≤·≤7 7≤··≤272≤·≤52 subtrees1 itemordering3 subtrees2 itemsordering4 subtrees3 itemsorderingLike a Binary-Search-Tree node30 Nov 2009 CS 311 Fall 2009 7Review2-3 Trees [2/4]A 2-3 Search Tree (generally we just say 2-3 Tree) is a tree with the following properties. All nodes contain either1 or 2 data items. If 2 data items, then thefirst is ≤ the second. All leaves are at thesame level. All non-leaves are either 2-nodes or 3-nodes. They must have the associated order properties.To retrieve in a 2-3 Tree: Begin at the root, and go down, using the order properties, until the item is found, or clearly not in the tree.To traverse a 2-3 Tree: Use the appropriate generalization of inorder traversal. Items are visited in sorted order.9 182032352 47 1223 2830 Nov 2009 CS 311 Fall 2009 8Review2-3 Trees [3/4]To insert in a 2-3 Tree: Find the leaf that the new item should go in. If it fits, then simply put it in. Otherwise, there is an overfull node. Split it, and move the middle item up, either recursively inserting it in the parent, or else creating a new root.9182 47 12187 129 2 4 5 9 184 7 122 5 9 182 51247182 47 129187 12942530 Nov 2009 CS 311 Fall 2009 9Review2-3 Trees [4/4]To delete in a 2-3 Tree: Find the item. If it is not in a leaf, swap with its successor. Do the recursive delete-a-leaf procedure.To delete-a-leaf: Easy Case: If the item is in a node with another item, simply remove it. Semi-Easy Case: Otherwise, if the node has a consecutive sibling with two items, do a rotation with the parent. Hard Case: Otherwise, bring the parent down, combining it with a consecutive sibling. Use recursive delete-a-leaf on the parent.When doing a recursive “delete-a-leaf” on a non-leaf node, drag along subtrees.182 47 129 182 49 127182 47 129 187 1292182 47 129 184 1272182 47 129 2 479 1230 Nov 2009 CS 311 Fall 2009 10ReviewOther Balanced Search Trees [1/4]In a 2-3-4 Tree, we also allow 4-nodes.The insert and delete algorithms are not terribly different fromthose of a 2-3 Tree. They are a little more complex. And they tend to be a little faster.9 1820323523 284 7 122 530 Nov 2009 CS 311 Fall 2009 11ReviewOther Balanced Search Trees [2/3]A very efficient kind of balanced search tree is a Red-Black Tree. This is a Binary-Search Tree representation of a 2-3-4 tree. Each node in a Red-Black Tree is either red or black. Each node in the 2-3-4 Tree corresponds to a black node. The red nodes are the extra ones we need to add. Red-Black Trees may not be balanced (in the strict sense). However, each path from the root to a leaf must pass through thesame number of black nodes.2-3-4 tree Corresponding Red-Black Tree205 153 9 14 19722 252412195 12 153 147 9 2522242030 Nov 2009 CS 311 Fall 2009 12ReviewOther Balanced Search Trees [3/3]All balanced search trees (2-3 Trees, 2-3-4 Trees, Red-Black Trees, AVL Trees, etc.) have: O(log n) retrieve, insert, delete. O(n) traverse (sorted).Retrieve & Sorted Traverse For Red-Black Trees and AVL Trees, use the B.S.T. algorithms (traverse = inorder