Scribd Logo
Upload

Welcome to Scribd!

  • 68 views

    CMSC 341: Binary Search Trees

    Uploaded by

    Duy Đức Trần
    The document discusses binary search trees (BSTs). It defines a BST as a binary tree where the value in each node is greater than all values in its left subtree and less than all values in its right subtree. It provides pseudocode for common BST operations like insertion, deletion, searching and traversing. It also discusses ways to iterate through a BST using different iterators and the performance of various BST operations and building a BST from an unsorted array.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd

    CMSC 341: Binary Search Trees

    Uploaded by

    Duy Đức Trần
    68 views25 pages
    The document discusses binary search trees (BSTs). It defines a BST as a binary tree where the value in each node is greater than all values in its left subtree and less than all values in its right subtree. It provides pseudocode for common BST operations like insertion, deletion, searching and traversing. It also discusses ways to iterate through a BST using different iterators and the performance of various BST operations and building a BST from an unsorted array.

    Original Title

    Bst

    Copyright

    © Attribution Non-Commercial (BY-NC)

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document discusses binary search trees (BSTs). It defines a BST as a binary tree where the value in each node is greater than all values in its left subtree and less than all values in its right subtree. It provides pseudocode for common BST operations like insertion, deletion, searching and traversing. It also discusses ways to iterate through a BST using different iterators and the performance of various BST operations and building a BST from an unsorted array.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    68 views25 pages

    CMSC 341: Binary Search Trees

    Uploaded by

    Duy Đức Trần
    The document discusses binary search trees (BSTs). It defines a BST as a binary tree where the value in each node is greater than all values in its left subtree and less than all values in its right subtree. It provides pseudocode for common BST operations like insertion, deletion, searching and traversing. It also discusses ways to iterate through a BST using different iterators and the performance of various BST operations and building a BST from an unsorted array.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 25

    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 20 A 27 25 B Describe the values which might appear in the subtrees labeled A, B, C, and D
    8/3/2007 UMBC CMSC 341 BST 3

    50 32 35 C D 60 99

    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
    inorder -- as dictated by operator< preorder, postorder, levelorder -- as dictated by the structure of the tree

    8/3/2007

    UMBC CMSC 341 BST

    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

    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

    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

    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

    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

    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 contains insert remove findMin/ Max makeEmpty assignment
    8/3/2007 UMBC CMSC 341 BST 14

    Worst Case

    Average Case

    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


    predecessor is the first node on path back to root that does not have v in its left subtree
    8/3/2007 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


    successor is first node on path back to root that does not have v in its right subtree
    8/3/2007 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.
    InOrderIterator<T> inOrderIterator(); PreOrderIterator<T> preOrderIterator(); PostOrderIterator<T> postOrderIterator(); LevelOrderIterator<T> levelOrderIterator();
    8/3/2007 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 Call List Iterator Methods


    T next() { 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 InOrderIterator { Stack<BinarySearchTree.BinaryNode<T>> _theStack; //constructor InOrderIterator(BinarySearchTree.BinaryNode<T> root){ _theStack = new Stack(); fillStack( root ); } // constructor helper function void fillStack(BinarySearchTree.BinaryNode<T> node){ while(node != null){ _theStack.push(node); node = node.left; } }

    8/3/2007

    UMBC CMSC 341 BST

    23

    Stack-Based InOrderIterator
    T next(){ BinarySearchTree.BinaryNode<T> topNode = null; try { topNode = _theStack.pop(); }catch (EmptyStackException e) { return null; } if(topNode.right != null){ fillStack(topNode.right); } return topNode.element; } boolean hasNext(){ return !_theStack.empty(); } }

    8/3/2007

    UMBC CMSC 341 BST

    24

    More Recursive BST Methods


    bool isBST ( BinaryNode<T> t ) returns true if the Binary tree is a BST const T& findMin( BinaryNode<T> t ) returns the minimum value in a BST int countFullNodes ( BinaryNode<T> t ) returns the number of full nodes (those with 2 children) in a binary tree int countLeaves( BinaryNode<T> t ) counts the number of leaves in a Binary Tree

    8/3/2007

    UMBC CMSC 341 BST

    25

    You might also like