CSE 1729 Introduction to Principles of Programming November 1, 2015 Problem Set 7
1. Inlabyouimplementedmergesort.Generalizeyour(mergesort lst)functioninto(gen-mergesort f lst), where f is a comparison function that defines the sorting criteria, that is, (f x y) is #t
if x precedes y in sorted order. Show that the same input list can produce different outputs by changing the function.
2. Up to now we have sorted numbers, as they are easy to compare. But we can compare symbols as well using lexicographic order. Scheme does not have comparison functions that work with symbols, but they have comparison functions that work with strings – another datatype corresponding to sequencesofcharacterswithinquotationmarks,andthereisafunction(symbol->string x)that will give you the string representation of a symbol x. Strings can be compared using the functions (string? a b), and (string=? a b). Here is some example code:
> (symbol- >string ’aromatic) “aromatic”
> (symbol- >string ’blorch) “blorch”
> (string string #t
> (string >? (symbol- >string #f
’axiom)(symbol- >string
’axiom)(symbol- >string
’boat))
’boat))
> (string=? (symbol->string ’al)(symbol->string ’al)) #t
(a) Using this information, write Scheme functions (symbol? x y).
These should work by obtaining the string representations of the parameters using symbol->string, and using the string comparison functions. Notice that it is unnecessary to implement (symbol=?
x y), as we already have the eq? function that works for symbols.
(b) Useoneormoreofyoursymbolcomparisonfunctionstodemonstratethatyourgen-mergesort function can sort a list of symbols.
3. In lab this week, you wrote some functions to work with binary trees. In this question, you will develop some code for binary search trees, as we have been doing in lecture. The representa- tion of a binary search tree will be the same as the binary trees we used in lab, that is, a tree is a three-element list: the value of the node, the left subtree, and the right subtree, with empty trees represented as the empty list. To make it clear that we are working with binary search trees, we will use standard functions with different names: (make-bst value left right) replac- ing make-tree, (bst-value tree) replacing value, (bst-left tree) replacing left, and (bst-right tree) replacing right. These should be really easy to write given the functions you used in lab.
Unlike the binary search trees we have been discussing in lecture, for the questions here we will assume all of the values are symbols, so you will need to use your symbol? functions (as well as eq?) to build and search through your trees.
1
(a) Write the standard binary search tree functions make-bst, bst-value, bst-left, and bst-right
(b) Using these functions, write a Scheme function (bst-element? item bs-tree) that eval- uates to #t if item is the value of a node in bs-tree, #f otherwise.
(c) Using these functions, write a Scheme function (bst-insert item bs-tree) that evalu- ates to the binary search tree that that results from inserting the value item into binary search tree bs-tree. Remember that we do not allow duplicate values in our binary search trees.
(d) Write the Scheme function (bst-smallest bs-tree) that evaluates to the smallest value in binary search tree bs-tree. If there are no values in the tree, it should evaluate to ’undefined).
(e) Write the Scheme function (bst-largest bs-tree) that evaluates to the largest value in binary search tree bs-tree. If there are no values in the tree, it should evaluate to ’undefined).
(f) Define a Scheme procedure, named bst-equal?, which takes two binary search trees as parameters and returns true if the trees are identical (same values in the same places with the same structure) and false otherwise.
(g) Since these binary search trees contain symbols (their node values) without repeats, they are ideal for representing sets of symbols. Write a Scheme function (bst-subset? bst1 bst2) that evaluates to #t if the set of values in bst1 is a subset of the set of values in bst2, #f otherwise.
(h) Use bst-subset to write a Scheme function (bst-set-equal? bst1 bst2), that evalu- ates to #t if the set of values in bst1 is the same as the set of values in bst2, #f otherwise.
4. Deleting a value from a binary search tree can be tricky – when you delete a node containing a value, the result must still be a binary search tree. There is an explanation below of the various cases you will need to consider. You will do this in parts, starting with the easier cases and then solving the general problem.
For each of these delete functions, the trees that are returned must maintain the binary search tree property explained below.
(a) Define a Scheme procedure, named bst-delete-min that takes a binary search tree, bst as a parameter and returns a binary search tree with the node that contains the minimum value removed from the tree – that is, a binary search tree with the same values except for the minimum one. This procedure should not use bst-smallest or bst-delete.
(b) Define a Scheme procedure, named bst-delete-max that takes a binary search tree, bst as a parameter and returns a binary search tree with the node that contains the maximum value removed from the tree. This procedure should not use bst-largest or bst-delete.
(c) Finally, define a Scheme procedure, (bst-delete val bst) that takes a number val and a binary search tree bst as parameters and returns a binary search tree with the node that whose value is equal to val removed from the tree – that is, the values in the resultant binary search tree will be the same as the original binary search tree with the exception of val; if val is in the original tree’s set it will not be in the resultant tree’s set, but the tree will have the same set if val was not in the original set.
2
bill
al chas
hal
evan
fritz
ken
fred
joe
rip
Example 1: An example of a binary search tree.
Deleting nodes from trees Each of the above delete functions is tasked with removing one value (and its node) from the input binary search tree bst. Naturally, if bst has n nodes, the output tree has n − 1 nodes (unless the value to be removed is not in the tree) and satisfies the binary search tree property (for every node n, the nodes in the left sub-tree of n hold values smaller than the value held in n and the nodes in the right-subtree of n hold values larger than the value held in n). There are number of cases that need to be handled separately: the node n may have no sub-trees, exactly one subtree, or two subtrees. (See Example 4.) The first two situations can be handled easily (Hint: how do these two relate to bst-delete-min and bst-delete-max?). The third case, illustrated below in Example 2, requires that you restructure the tree a bit to reattach the two “orphaned” subtrees of n in an appropriate way. One can either replace the value at the deleted node with the largest value in the left subtree or the smallest value in the right subtree while removing the corresponding leaf node.
3
evan
bill
joe
al
chas
fritz
ken
fred
rip
Example 2: The same binary search tree after the removal of the value hal. Note, we chose to promote the largest value in the left subtree (joe) to the node vacated by the value hal.
4
evan
bill
fritz
al
chas
fred
joe
ken
Example 3: The same binary search tree after the removal of the value hal. Note, we chose to promote the left subtree, and connected the right subtree to the node with the largest value in the left subtree joe.
rip
bill bill
al
bill
bill
or
Example 4: There are three possibilities when finding a node to remove. For each of these we are removing the node containing bill.
5
chas al
chas