CMSC15100 Autumn 2010: Homework 4

Due Tuesday, October 26 at 10pm.

Setup

This assignment should be done using the Intermediate student language.

Exercise 1: Binary search trees

A binary search tree (BST) is a binary tree labeled with the elements of an ordered set (e.g., numbers), such that the following invariant holds for all of the nodes in the tree:

If nd is a node in the tree with label a, left child l and right child r, then the labels of the nodes in l will be less than a and the labels of the nodes in r will be greater than a.

We can define a BST using the following data definition:

;; A bst (binary-search tree) is either ;; - a leaf represented by 'leaf, or ;; - a bst-node (define-struct bst-node (val ; : number left ; : bst right ; : bst ))

Binary search trees are useful, because they allow efficient search for elements. For example, the following function checks to see if a number is in the BST in expected O(log N) time:

;; bst-member? : bst number -> boolean ;; returns #t if num is in bst ;; (define (bst-member? bst num) ...) (define (bst-member? bst num) (cond [(equal? bst 'leaf) #f] [(< num (bst-node-val bst)) (bst-member? (bst-node-left bst) num)] [(> num (bst-node-val bst)) (bst-member? (bst-node-right bst) num)] [else #t]))

Develop a function

;; inorder : bst -> (sorted-list number) ;; returns the elements of bst in ascending order ;; (define (inorder bst) ...) (check-expect (inorder 'leaf) '()) (check-expect (inorder (make-bst-node 2 (make-bst-node 1 'leaf 'leaf) (make-bst-node 3 'leaf 'leaf))) '(1 2 3))

Develop a function

;; insert : bst number -> bst ;; returns a BST that is bst with num added to it. ;; (define (insert bst num) ...) (check-expect (insert 'leaf 1) (make-bst-node 1 'leaf 'leaf)) (check-expect (insert (make-bst-node 1 'leaf 'leaf) 1) (make-bst-node 1 'leaf 'leaf)) (check-expect (insert (make-bst-node 1 'leaf 'leaf) 0) (make-bst-node 1 (make-bst-node 0 'leaf 'leaf) 'leaf)) (check-expect (insert (make-bst-node 1 'leaf 'leaf) 2) (make-bst-node 1 'leaf (make-bst-node 2 'leaf 'leaf)))

Section 14.2 in HtDP discusses binary search trees, but note that they use a different reresentation than this exercise.

Exercise 2: Heaps

Another kind of ordered tree structure is a heap, which can be defined as follows:

;; A heap is either ;; - a leaf represented by 'leaf, or ;; - a heap-node (define-struct heap-node (val ; : number left ; : heap right ; : heap ))

A node (make-heap-node v l r) must satisfy the invariant that every value in l and r is greater than or equal to v. In otherwords, for any path from the root to a leaf, the values are ordered by <=. Heaps are often used to represent priority queues.

Develop a function

;; least : heap -> number ;; returns the smallest element in the heap, or else #f for an empty heap. ;; (define (least heap) ...)

Develop a function

;; heap-insert : heap number -> heap ;; inserts the number into the heap ;; (define (least heap) ...)

The result must satisfy the heap invariant. Note that a heap can have multiple occurances of the same value.