append in doing tree traversals.
Hans* matches not only the name Hans, but also Hanson and
Hansen. The names will always be specified as strings, i.e., between
double quote marks.
The lab assignment is to become familiar with the provided code, make
the few additions to it that are needed, and make timing comparisons
between it and the (provided) alternative of simply filtering through
a list. The details of what you are supposed to do are given in a
comment at the end of the file containing the provided code. That
file is in ~max/www-docs/MC28/labs/lab5/lab5.scm,
a copy of which is attached. Here is another copy of what you are
supposed to do:
dictionary-insert! procedure and test it
by inserting some entries (such as the first few from names)
into names-by-last-name and then displaying the dictionary's
red-black tree by doing
(display-ranked-btree (red-black-tree names-by-last-name))Note that the
dictionary-insert! procedure should not be
large or complex: it just calls red-black-insert! with the
appropriate arguments.
reset-dictionary! on names-by-last-name and then inserts
the first n elements of names into names-by-last-name using
the dictionary-insert! procedure you wrote, in conjunction with
for-each (as described in section 13.4) and the first-elements-of
procedure.
binary-search-retrieve as described in 13.4, and then
define red-black-retrieve as identical to it, i.e.
(define red-black-retrieve binary-search-retrieve)and then define
dictionary-retrieve to call red-black-retrieve
on the dictionary's red-black tree using the dictionary's
key comparator and extractor. Test this using names-by-last-name.
You should be able to, for example, find all the users with your
last name, or find all users with last names of the form "Hans*",
i.e., starting with Hans.
dictionary-retrieve with list-retrieve
as the number of entries being searched is increased. You will
get the most distinct results if the search is one that matches
very few names. However, you may also want to experimentally see
what effect the number of matches has on the time for each of the two
retrieval methods.