SUNY Geneseo Department of Computer Science


Ordered Binary Tree Deletion, Part 1

{Date}

CSci 240, Spring 2007
Prof. Doug Baldwin

Return to List of Lectures

Previous Lecture

Misc

"What's the Point of a CS Major?" panel

GREAT Day

Hand out Lab 11

Questions?

Ordered Binary Tree Deletion

Section 13.5.1

Typo in algorithm, pages 458 and 460

        root = left.root
        left = left.rightleft

Examples

[Changes to a Tree as Nodes are Deleted]

Make the code a bit cleaner

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

    actualDelete() {
        ...
        // Don't need secondLargest
        // Removing leaf and removing node with no right subtree
        //    are the same case: replace parent's pointer w/
        //    deletee's left pointer
    }

Next

Finish cleaning up deletion algorithm, look at execution time

No reading or mini-assignment


Next Lecture