Lab 12

Implement a binary tree with insert and contains? operations in a store-passing style.

Here are some data definitions:

; a memory location is either false or a number

(define memloc? (or/c false? number?))

; for our purposes, the only thing in memory is

; nodes:

(define-type Node

[node (val number?)

(left memloc?)

(right memloc?)])

; a store maps locations (numbers) to nodes:

(define store? (hash/c number? Node?))

; an Any*Store is just a way of bundling a value

; with a store:

(define-type Any*Store

[a*s (v any/c) (sto store?)])

(define starting-memory

(hash 0 (node 0 #f #f)))

The first location in memory, location zero, is special; its left and right pointers are always #f, and its value field indicates the last-allocated address. In order to allocate a new address, increment this counter by one and return it.

• Implement the insert method, that accepts a tree, a new value, and a store, and returns an Any*Store containing the updated tree and a new store in which the given tree now contains the given key. If the given tree is #f, it returns the newly allocated memory location along with the new store. If the given tree is non-#f, it returns the given tree along with the new store.

• Implement the contains? method, that accepts a tree, a value, and a store, and returns a boolean indicating whether the given value occurs in the tree.

Don’t use any form of mutation—mutable hash tables, boxes, etc.—for this lab.