; The below abstraction for binary trees is implemented with
; a function in order to force you to use selectors to inspect
; tree data in the interpreter.
(define (make-bintree datum left right)
(lambda (msg)
(cond ((= msg 0) datum)
((= msg 1) left)
((= msg 2) right))))
(define (datum bintree) (bintree 0))
(define (left bintree) (bintree 1))
(define (right bintree) (bintree 2))
(define the-empty-tree 'cow)
(define tet the-empty-tree)
(define (empty-tree? tree)
(eq? tree tet))
(define (leaf? bintree)
(and (not (empty-tree? bintree))
(empty-tree? (left bintree))
(empty-tree? (right bintree))))
(define bst
(make-bintree 15
(make-bintree 6
(make-bintree 2 tet tet)
tet)
(make-bintree 22
(make-bintree 17
(make-bintree 16 tet tet)
(make-bintree 19 tet tet))
(make-bintree 24 tet tet))))
Here is a picture of bst:
bst ---> 15
/ \
/ \
6 22
/ / \
/ / \
2 17 24
/ \
/ \
16 19
This is a binary tree because for every node in the tree, it has at most two children. It is a binary search tree because for every node in the tree, the data in the left subtree are smaller and the data in the right subtree are larger.
The depth of a tree is the number of nodes on the longest possible path from root to a leaf. In this case, the depth is 4, with a tie for longest path: 15-22-17-16 and 15-22-17-19.
This binary search tree is balanced based on height. That means that for every node, the depth of the left subtree and the depth of the right subtree differ by at most one.
It is not balanced based on weight. For a binary tree to be balanced based on weight, the number of nodes in the left subtree and the number of nodes in the right subtree must differ by at most one. If you look at the node containing the 15, there are two nodes in the left subtree and five in the right subtree, a difference of three.
The function list->tree takes a list of numbers, sorted in increasing order, and returns a weight-balanced binary search tree containing those numbers. Your mission in this problem is to write list->tree. An outline of a solution path is given below. If you prefer to take this on as a challenge problem, try to figure out the steps on your own.
Suppose we have the list '(1 2 3 4 5 6 7). For the tree to be weight-balanced, it would have to be stored as follows:
bst ---> 4
/ \
/ \
2 6
/ \ / \
/ \ / \
1 3 5 7
Remember that make-bintree takes a datum, a left subtree, and a right subtree as inputs. The datum for the first call to make-bintree in this example would be 4. The left subtree would contain the numbers smaller than 4. The right subtree would contain the numbers that are larger than 4.
It gets a little trickier if we have an even number of data in the list. For example consider '(1 2 3 4 5 6 7 8). For this tree to be weight-balanced, it could be stored as either of the following trees or any other where, for each node, the number of data to the left differs from the number of data to the right by at most one:
bst ---> 5
/ \
/ \
3 7
/ \ / \
/ \ / \
2 4 6 8
/
/
1
or
bst ---> 4
/ \
/ \
2 6
/ \ / \
/ \ / \
1 3 5 7
\
\
8
or
bst ---> 4
/ \
/ \
2 7
/ \ / \
/ \ / \
1 3 6 8
/
/
5
Etc.
At this point, if you want a challenge problem, skip straight to problem #6, below. Otherwise, do problems 1--5 to set up problem #6.
1. Write the function first-n that takes two inputs, a list, lyst, and a number, n. It returns a list containing the first n elements of lyst.
Examples:
> (first-n '(A B C D E) 3) (A B C) (define (first-n lyst n)
(cond ((= n 0) '())
(else (cons (car lyst) (first-n (cdr lyst) (- n 1))))))
2. Write the function part1 which takes a list as its input and returns a list containing the first half of the elements of the input list. If the input list has an odd number of elements, the extra element should NOT be part of part1. Make sure to be very careful with an input of the empty list.
Hint: The functions length, floor, and first-n from above will be helpful. A helper function may be extremely helpful.
Examples:
> (part1 '(1 2 3 4 5 6)) (1 2 3) > (part1 '(1 2 3 4 5)) ; the 3 will go into part2 (1 2) > (part1 '()) () (define (part1 lyst)
(let ((n (floor (/ (length lyst) 2))))
(first-n lyst n)))
3. Write the function rest which takes a list as its input and returns list containing those elements in the list that would not be returned by part1. Again, make sure your function handles empty lists properly.
Hint: Consider using helper function(s).
Examples:
> (rest '(1 2 3 4 5 6)) (4 5 6) > (rest '(1 2 3 4 5)) ; the 3 will go into rest (3 4 5) > (rest '()) () ; nth-cdr does n cdrs and returns the resulting list ; There are other ways to write this; I chose to use ; repeated from the homework (also seen in Simply Scheme) (define (nth-cdr lyst n)
((repeated cdr n) lyst)) ; repeated is from the homework
(define (repeated f n)
(lambda (x)
(cond ((= n 0) x)
(else (f ((repeated f (- n 1)) x)))))) (define (rest lyst)
(nth-cdr lyst (floor (/ (length lyst) 2))))
4. Write the function middle-datum which takes a list as its input and returns the middle element of the list. If the list contains an even number of elements, the middle element will be second of the two in the middle. You may assume that middle-datum will only be called with lists that contain at least one element.
Hint: Using one of the above functions should make this really easy.
Examples:
> (middle-datum '(1 2 3)) 2 > (middle-datum '(1 2 3 4)) 3 (define (middle-datum lyst)
(car (rest lyst)))
5. Write the function part2 that takes a list as its input and returns the list excluding middle-datum and part1.
Hint: Using one of the above functions should make this really easy, too.
Examples:
> (part2 '(1 2 3)) ; middle-datum is 2 (3) > (part2 '(1 2 3 4)) ; middle-datum is 3 (4) > (part2 '(1 2 3 4 5)) ; middle-datum is 3 (4 5) > (part2 '(1 2 3 4 5 6)) ; middle-datum is 4 (5 6) (define (part2 lyst)
(if (null? lyst) lyst (cdr (rest lyst))))
6. Write the function list->tree that takes a list of increasing numbers as its input and returns a weight-balanced binary search tree containing those numbers.
Example:
(define binary-tree (list->tree '(1 2 3 4 5 6 7 8)))
will result in binary-tree being as follows:
binary-tree ---> 5
/ \
/ \
3 7
/ \ / \
/ \ / \
2 4 6 8
/
/
1
(define (list->tree lyst)
; No elements in list? Return an empty tree
(cond ((null? lyst) tet)
; Otherwise, return a tree with data, which means
; we must use make-bintree since that is the only
; constructor we have for trees
(else (make-bintree (middle-datum lyst)
(list->tree (part1 lyst))
(list->tree (part2 lyst))))))