Lecture 14 Objectives

At the end of today's class you should

KNOW:

That a set is a data structure for a collection of elements without duplicates
That a set can be implemented in various ways
That the decision for choosing how to implement a data structure may depend on the application the data structure is being used for
That a binary search tree (BST) is a binary tree with an invariant
That the methods that modify a BST are responsible for maintaining the invariant
That a BST can give better runtime performance than a list
That a BST has linear worst-case performance

BE ABLE TO:

Describe the properties and operations for a set
Show the results of adding or removing an element from a BST

Sample Exam Question:

Given this BST:


                       14
                     /    \
                    /      \
                  10        36
                 /  \         \
                /    \         \
               8      12        92

Draw the BST that would result from removing the element 14. Replacements should come from the left subtree.