SUNY Geneseo Department of Computer Science

Tree Deletion and Traversal

Return to List of Lectures

Misc

GREAT Day

• Tomorrow (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

SOFIs

• On-line
• Now through May 2
• Check e-mail or see https://www.onlinecourseevaluations.com/login.aspx?s=geneseo

Lab 11 (tree height) due Wednesday

• Written report

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 )
                return this
            }
            else {
                left = left.delete( value )
                return this
            }
        }
        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
            secondLargest = this
            node = this.left
            while ( node.hasRight() ) {
                secondLargest = node
                node = node.right
            }
            this.root = node.root
            if ( secondLargest == this ) {
                this.left = node.left
            }
            else {
                secondLargest.right = node.left
            }
            return this
        }
    }

What are the execution times for deletion from an ordered binary search tree?

• Search part takes at most h units of time (h = height)
• Find largest left descendant takes at most h-1 units
• Total time is at most h units (since levels checked in search aren't checked in "find largest")
• Best worst case = Θ( logn )
• Worst worst case = Θ( n )
• Best best case = Θ( 1 )

Tree Traversals

Goal: Process (e.g., print) all nodes in a tree

What might a traversal algorithm look like?

• A binary tree...
  • Empty, or
  • A root with 2 binary trees

        // In class BinaryTree<E>
        private E root
        private BinaryTree<E> left, right

        traverse() {
            if ( ! this.isEmpty() ) {
                left.traverse()
                process root
                right.traverse()
            }
        }

Kinds of traversal

• preorder = root before children
• inorder = root between children
• postorder = root after children
• (also level-order, aka breadth-first)

Next

Finish traversals, maybe start heaps and priority queues

Read section 13.3.2