DOC PREVIEW
UMBC CMSC 341 - Binary Search Trees

This preview shows page 1-2-24-25 out of 25 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 25 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 25 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 25 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 25 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 25 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

CMSC 341Binary Search TreeA BST of integersSearchTree ADTBST ImplementationBST Implementation (2)BST “contains” MethodPerformance of “contains”Implementation of printTreeBST Implementation (3)The insert OperationThe remove OperationImplementations of find Max and MinPerformance of BST methodsPredecessor in BSTSuccessor in BSTBuilding a BSTTree IteratorsUsing Tree IteratorThe InOrderIterator is a Disguised List IteratorList-Based InOrderIterator MethodsList-based InOrderIterator Methods Call List Iterator MethodsStack-Based InOrderIteratorMore Recursive BST MethodsCMSC 341Binary Search Trees8/3/2007UMBC CMSC 341 BST2Binary 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/2007UMBC CMSC 341 BST3A BST of integers422050609935322725ABCDDescribe the values which might appear in the subtrees labeled A, B, C, and D8/3/2007UMBC CMSC 341 BST4SearchTree 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inorder -- as dictated by operator<preorder, postorder, levelorder -- as dictated by the structure of the tree8/3/2007UMBC CMSC 341 BST5BST Implementationpublic 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; // The data in the node BinaryNode<AnyType> left; // Left child BinaryNode<AnyType> right; // Right child }8/3/2007UMBC CMSC 341 BST6BST Implementation (2) private BinaryNode<AnyType> root; public BinarySearchTree( ) { root = null; } public void makeEmpty( ) { root = null; } public boolean isEmpty( ){ return root == null; }8/3/2007UMBC CMSC 341 BST7BST “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/2007UMBC CMSC 341 BST8Performance 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 cases8/3/2007UMBC CMSC 341 BST9Implementation of printTreepublic 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/2007UMBC CMSC 341 BST10BST 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/2007UMBC CMSC 341 BST11The 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/2007UMBC CMSC 341 BST12The 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/2007UMBC CMSC 341 BST13Implementations 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/2007UMBC CMSC 341 BST14Performance of BST methodsWhat is the asymptotic performance of each of the BST methods?Best Case Worst Case Average CasecontainsinsertremovefindMin/MaxmakeEmptyassignment8/3/2007UMBC CMSC 341 BST15Predecessor 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predecessor is the first node on path back to root that does not have v in its left subtree8/3/2007UMBC CMSC 341 BST16Successor 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successor is first node on path back to root that does not have v in its right subtree8/3/2007UMBC CMSC 341 BST17Building a BSTGiven an array/vector of elements, what is the performance (best/worst/average) of building a BST from scratch?8/3/2007UMBC CMSC 341 BST18Tree 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.InOrderIterator<T>


View Full Document

UMBC CMSC 341 - Binary Search Trees

Download Binary Search Trees
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Binary Search Trees and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Binary Search Trees 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?