SUNY Geneseo Department of Computer Science

Ordered Binary Tree Deletion, Part 2

Return to List of Lectures

Misc

GREAT Day

• Tuesday, April 17, all day
• Student presentations on research, art work, similar scholarly activities
• Including 4 or 5 posters on student research in CS -- what you could be doing in a year or so
• See http://www.geneseo.edu/CMS/display.php?page=5155&dpt=great for summary schedule

Questions?

Ordered Binary Tree Deletion

Make the code a bit cleaner

    // In class OrderedTree<E>
    private E root;
    private OrderedTree<E> left, right;
	
    OrderedTree<E> delete( E value ) {
        if ( ! this.isEmpty() ) {
            if ( root == value ) {
                return this.actualDelete()
            }
            else if ( value > root ) {
                right = right.delete( value )
            }
            else {
                left = left.delete( value )
            }
        }
        else {
            return this
        }
    }

    OrderedTree<E> actualDelete() {
        if ( left.isEmpty() ) {
            return right
        }
        else if ( right.isEmpty() ) {
            return left
        }
        else {
            // copy largest value in left to this, and remove
            // that largest node in left
        }
        // Don't need secondLargest
    }

Mini-assignment: fill in pseudocode for the last "else" arm above

Next

Execution time for ordered binary tree deletion

Tree traversals.