appendin 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
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-by-last-nameand 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.
names-by-last-nameand then inserts the first n elements of
dictionary-insert!procedure you wrote, in conjunction with
for-each(as described in section 13.4) and the
binary-search-retrieveas described in 13.4, and then define
red-black-retrieveas identical to it, i.e.
(define red-black-retrieve binary-search-retrieve)and then define
red-black-retrieveon 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.
list-retrieveas 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.