Binary Search TreesTreesortCS 311 Data Structures and AlgorithmsLecture SlidesFriday, November 13, 2009Glenn G. ChappellDepartment of Computer ScienceUniversity of Alaska [email protected]© 2005–2009 Glenn G. Chappell13 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.13 Nov 2009 CS 311 Fall 2009 3Unit OverviewThe Basics of TreesMajor Topics Introduction to Trees Binary Trees Binary Search Trees Treesort13 Nov 2009 CS 311 Fall 2009 4ReviewBinary Trees — What a Binary Tree IsA Binary Tree consists of a set T of nodes so that either: T is empty (no nodes), or T consists of a node r, the root, and two subtrees of r, each of which is a Binary Tree: the left subtree, and the right subtree.We make a strong distinction between left and right subtrees. Sometimes, we use them for very different things.ababDifferent Binary Trees13 Nov 2009 CS 311 Fall 2009 5ReviewBinary Trees — Three Special KindsA typical full Binary Tree:A typical complete Binary Tree:A typical balanced Binary Tree:A full Binary Tree is complete; a complete Binary Tree is balanced.Full Complete Balanced13 Nov 2009 CS 311 Fall 2009 6ReviewBinary Trees — Traversals [1/3]One thing we do with Binary Trees is to “traverse” them. Traversing a tree means visiting each node.There are three standard traversals of Binary Trees: preorder, inorder, and postorder. The name tells us where the root goes: before, in between, after.Preorder traversal: Root. Preorder traversal of left subtree. Preorder traversal of right subtree.Inorder traversal: Inorder traversal of left subtree. Root. Inorder traversal of right subtree.Postorder traversal. Postorder traversal of left subtree. Postorder traversal of right subtree. Root.13 Nov 2009 CS 311 Fall 2009 7ReviewBinary Trees — Traversals [2/3]Write preorder, inorder, and postorder traversals of the Binary Tree to the right.Preorder: 1 2 4 5 3Inorder: 4 2 5 1 3Postorder: 4 5 2 3 112 34 5root left subtreeright subtreerootleft subtreeright subtreerootleft subtreeright subtree13 Nov 2009 CS 311 Fall 2009 8ReviewBinary Trees — Traversals [3/3]Given a drawing of a Binary Tree, draw a path around it, hitting the left, bottom, and right sides of each node, as shown.The order in which the path hits the leftside of each node gives the preordertraversal. 1 2 4 5 3The order in which the path hits the bottom side of each node gives the inorder traversal. 4 2 5 1 3The order in which the path hits the rightside of each node gives the postordertraversal. 4 5 2 3 112 34 513 Nov 2009 CS 311 Fall 2009 9ReviewBinary Trees — ImplementationA common way to implement a Binary Tree is to use separately allocated nodes referred to by pointers. This is very similar to the way we implemented a Linked List. Each node has a data item andtwo child pointers: left & right. A pointer is null if there is no child.A complete Binary Tree can be implemented simply by puttingthe items in an array, and keeping track of the size of the tree. This is a nice implementation, butit is only useful in situations inwhich the tree stays complete.321527head0 1 2 3 4 5 6 7 8 9Physical StructureLogical Structure01 27 8394 5 613 Nov 2009 CS 311 Fall 2009 10Binary Search TreesWhat a Binary Search Tree IsOur final “application” of Binary Trees is our next ADT:Binary Search Tree. Think: A Binary Tree inwhich each node’ssubtrees have an orderrelationship with the node. All data items in a node’s leftsubtree are ≤ the node’s item. All data items in a node’s rightsubtree are ≥ the node’s item. Note: Sometimes we replace“≤” and “≥” by “<” and “>”, sothat items having equivalentvalues are not allowed. Thus, an inorder traversallists items in sorted order.xItems ≤ x Items ≥ xMust be ≤ xMust be ≥ x(right?)13 Nov 2009 CS 311 Fall 2009 11Binary Search TreesADT [1/3]ADT Binary Search Tree Data A collection of nodes, each with a data item. Operations create empty B.S.T. destroy. isEmpty. insert (given item [which includes a key]). delete (given key). retrieve (given key, returns item). The three traversals: preorderTraverse,inorderTraverse, postorderTraverse.1316304225282210420Here they are again13 Nov 2009 CS 311 Fall 2009 12Binary Search TreesADT [2/3]This ADT is significantly simpler than Binary Tree.What can you observe about this ADT if you remove the preorder &postorder traversals from the list of operations (leaving inorder)? The ADT no longer has anything to do with Trees. A Binary Tree might be a reasonable implementation, however.Conclusion: A Binary Search Tree is essentially a big bag that things can be thrown in and retrieved from. The main questions we answer are “Is this key in the bag?”, and if so, “What is the associated value?”13 Nov 2009 CS 311 Fall 2009 13Binary Search TreesADT [3/3]Recall the comments on the ADT SortedSequence: In practice, the ordering of a SortedSequence is often not of primary importance. Rather, we are interested in items being easy to find.Binary Search Trees are similar. Sequence & Binary Tree are position-oriented ADTs. SortedSequence & Binary Search Tree are value-oriented ADTs. Binary Search Trees are another step toward a good value-oriented ADT, and implementation thereof. But we can do both of these better, as we will see.In value-oriented ADTs, data items have a “key”. A key is the part of the data that is search for & compared. This might be the entire value. Thus, two items whose keys do not compare as “different” are, for the purposes of inclusion in (say) a Binary Search Tree, identical.13 Nov 2009 CS 311 Fall 2009 14Binary Search TreesOperations — IntroductionNow we look at the details of B.S.T. operations.Most of the B.S.T. operations are just wrappers around the essentially identical Binary Tree operations: create destroy isEmpty the three traversals copy (?)Three of them,