CMSC 341 Binary Search Trees Binary Search Tree A Binary Search Tree is a Binary Tree in which at every node v the values stored in the left subtree of v are less than the value at v and the values stored in the right subtree are greater The elements in the BST must be comparable Duplicates are not allowed in our discussion Note that each subtree of a BST is also a BST 8 3 2007 UMBC CMSC 341 BST 2 A BST of integers 42 50 20 A 27 25 60 32 99 35 B C D Describe the values which might appear in the subtrees labeled A B C and D 8 3 2007 UMBC CMSC 341 BST 3 SearchTree ADT The SearchTree ADT A search tree is a binary search tree which stores homogeneous elements with no duplicates It is dynamic The elements are ordered in the following ways 8 3 2007 inorder as dictated by operator preorder postorder levelorder as dictated by the structure of the tree UMBC CMSC 341 BST 4 BST Implementation public class BinarySearchTree AnyType extends Comparable super AnyType private static class BinaryNode AnyType Constructors BinaryNode AnyType theElement this theElement null null BinaryNode AnyType theElement BinaryNode AnyType lt BinaryNode AnyType rt element theElement left lt right rt AnyType element BinaryNode AnyType left BinaryNode AnyType right The data in the node Left child Right child 8 3 2007 UMBC CMSC 341 BST 5 BST Implementation 2 private BinaryNode AnyType root public BinarySearchTree root null public void makeEmpty root null public boolean isEmpty return root null 8 3 2007 UMBC CMSC 341 BST 6 BST contains Method public boolean contains AnyType x return contains x root private boolean contains AnyType x BinaryNode AnyType t if t null return false int compareResult x compareTo t element if compareResult 0 return contains x t left else if compareResult 0 return contains x t right else return true Match 8 3 2007 UMBC CMSC 341 BST 7 Performance of contains Searching in randomly built BST is O lg n on average but generally a BST is not randomly built Asymptotic performance is O height in all cases 8 3 2007 UMBC CMSC 341 BST 8 Implementation of printTree public void printTree printTree root private void printTree BinaryNode AnyType t if t null printTree t left System out println t element printTree t right 8 3 2007 UMBC CMSC 341 BST 9 BST Implementation 3 public AnyType findMin if isEmpty throw new UnderflowException return findMin root element public AnyType findMax if isEmpty throw new UnderflowException return findMax root element public void insert AnyType x root insert x root public void remove AnyType x root remove x root 8 3 2007 UMBC CMSC 341 BST 10 The insert Operation private BinaryNode AnyType insert AnyType x BinaryNode AnyType t if t null return new BinaryNode AnyType x null null int compareResult x compareTo t element if compareResult 0 t left insert x t left else if compareResult 0 t right insert x t right else Duplicate do nothing return t 8 3 2007 UMBC CMSC 341 BST 11 The remove Operation private BinaryNode AnyType remove AnyType x BinaryNode AnyType t if t null return t Item not found do nothing int compareResult x compareTo t element if compareResult 0 t left remove x t left else if compareResult 0 t right remove x t right else if t left null t right null 2 children t element findMin t right element t right remove t element t right else t t left null t left t right return t 8 3 2007 UMBC CMSC 341 BST 12 Implementations of find Max and Min private BinaryNode AnyType findMin BinaryNode AnyType t if t null return null else if t left null return t return findMin t left private BinaryNode AnyType findMax BinaryNode AnyType t if t null while t right null t t right return t 8 3 2007 UMBC CMSC 341 BST 13 Performance of BST methods What is the asymptotic performance of each of the BST methods Best Case Worst Case Average Case contains insert remove findMin Max makeEmpty assignment 8 3 2007 UMBC CMSC 341 BST 14 Predecessor in BST Predecessor of a node v in a BST is the node that holds the data value that immediately precedes the data at v in order Finding predecessor v has a left subtree then predecessor must be the largest value in the left subtree the rightmost node in the left subtree v does not have a left subtree 8 3 2007 predecessor is the first node on path back to root that does not have v in its left subtree UMBC CMSC 341 BST 15 Successor in BST Successor of a node v in a BST is the node that holds the data value that immediately follows the data at v in order Finding Successor v has right subtree successor is smallest value in right subtree the leftmost node in the right subtree v does not have right subtree 8 3 2007 successor is first node on path back to root that does not have v in its right subtree UMBC CMSC 341 BST 16 Building a BST Given an array vector of elements what is the performance best worst average of building a BST from scratch 8 3 2007 UMBC CMSC 341 BST 17 Tree Iterators As we know there are several ways to traverse through a BST For the user to do so we must supply different kind of iterators The iterator type defines how the elements are traversed 8 3 2007 InOrderIterator T inOrderIterator PreOrderIterator T preOrderIterator PostOrderIterator T postOrderIterator LevelOrderIterator T levelOrderIterator UMBC CMSC 341 BST 18 Using Tree Iterator public static void main String args BinarySearchTree Integer tree new BinarySearchTree Integer store some ints into the tree InOrderIterator Integer itr tree inOrderIterator while itr hasNext Object x itr next do something with x 8 3 2007 UMBC CMSC 341 BST 19 The InOrderIterator is a Disguised List Iterator An InOrderIterator that uses a list to store the complete in order traversal import java util class InOrderIterator T Iterator T listIter List T theList T next TBD boolean hasNext TBD InOrderIterator BinarySearchTree BinaryNode T root TBD 8 3 2007 UMBC CMSC 341 BST 20 List Based InOrderIterator Methods constructor InOrderIterator BinarySearchTree BinaryNode T root fillListInorder theList root listIter theList iterator constructor helper function void fillListInorder List T list BinarySearchTree BinaryNode T node if node null return fillListInorder list node left list add node element fillListInorder list node right 8 3 2007 UMBC CMSC 341 BST 21 List based InOrderIterator Methods T next Call List Iterator Methods return listIter next boolean hasNext return listIter hasNext 8 3 2007 UMBC CMSC 341 BST 22 InOrderIterator Class with a Stack An InOrderIterator that uses a stack to mimic recursive traversal class