CS 22
Clab 13: More on Binary Search Trees (BST)
I'll analyze the running time of bst search under a couple of
balance assumptions.
Then, do the following exercises for BSTs and sets implemented
by them.
- exercise 2.63 on page 158
- exercise 2.64 on page 159
- exercise 2.65 on page 160
Here are the three trees from Figure 2.16.
<![CDATA[
(define tre1 '(7 (3 (1 () ()) (5 () ())) (9 () (11 () ()))))
(define tre2 '(3 (1 () ()) (7 (5 () ())(9 () (11 () ())))))
(define tre3 '(5 (3 (1 () () ) ()) (9 (7 () ()) (11 () ()))))
]]>
Here is code from pages 155-159
<![CDATA[
define (entry tree) (car tree))
(define (left-branch tree) (cadr tree))
(define (right-branch tree) (caddr tree))
(define (make-tree entry left right)
(list entry left right))
(define (element-of-set? x set)
(cond ((null? set) false)
((= x (entry set)) true)
((< x (entry set))
(element-of-set? x (left-branch set)))
((> x (entry set))
(element-of-set? x (right-branch set)))))
(define (adjoin-set x set)
(cond ((null? set) (make-tree x '() '()))
((= x (entry set)) set)
((< x (entry set))
(make-tree (entry set)
(adjoin-set x (left-branch set))
(right-branch set)))
((> x (entry set))
(make-tree (entry set)
(left-branch set)
(adjoin-set x (right-branch set))))))
;; EXERCISE 2.63
(define (tree->list-1 tree)
(if (null? tree)
'()
(append (tree->list-1 (left-branch tree))
(cons (entry tree)
(tree->list-1 (right-branch tree))))))
(define (tree->list-2 tree)
(define (copy-to-list tree result-list)
(if (null? tree)
result-list
(copy-to-list (left-branch tree)
(cons (entry tree)
(copy-to-list (right-branch tree)
result-list)))))
(copy-to-list tree '()))
;; EXERCISE 2.64
(define (list->tree elements)
(car (partial-tree elements (length elements))))
(define (partial-tree elts n)
(if (= n 0)
(cons '() elts)
(let ((left-size (quotient (- n 1) 2)))
(let ((left-result (partial-tree elts left-size)))
(let ((left-tree (car left-result))
(non-left-elts (cdr left-result))
(right-size (- n (+ left-size 1))))
(let ((this-entry (car non-left-elts))
(right-result (partial-tree (cdr non-left-elts)
right-size)))
(let ((right-tree (car right-result))
(remaining-elts (cdr right-result)))
(cons (make-tree this-entry left-tree right-tree)
remaining-elts))))))))
]]>
ask any questions you may have.
<![CDATA[
]]>