32
Removing ‘Florida’
Oklahoma
Colorado
Florida
❷If necessary, do some
rearranging.
33
Removing ‘Florida’
❷If necessary, do some
rearranging.
Oklahoma
Colorado
Florida
34
Removing ‘Florida’
Oklahoma
Colorado
Iowa
❷If necessary, do some
rearranging.
35
Arizona
Removing ‘Florida’
Washington
Oklahoma
Colorado
Mass.
Iowa
… and then remove
the extra copy of the
❷If necessary, do some
rearranging.
36
Here’s a good question for you: Remember that it’s hard to remove
nodes with two children. How do you know that the smallest item in the
right subtree does not have two children?
Removing ‘Florida’
Oklahoma
Colorado
Iowa
❷If necessary, do some
rearranging.
37
Removing ‘Florida’
Oklahoma
Colorado
Florida
38
Removing ‘Florida’
Oklahoma
Colorado
Iowa
39
Removing an Item with a
Given Key
❶Find the item.
❷If the item has a right child, rearrange the tree:
❐Find smallest item in the right subtree
❐Copy that smallest item onto the one that you
want to remove
40
❐Binary search trees are a good implementation of
data types such as sets, bags, and dictionaries.
❐Searching for an item is generally quick since you
Summary
41
Presentation copyright 1997 Addison Wesley Longman,
For use with
Data Structures and Other Objects Using C++
by Michael Main and Walter Savitch.
Some artwork in the presentation is used with permission from Presentation Task Force
(copyright New Vision Technologies Inc) and Corel Gallery Clipart Catalog (copyright