Binary trees in Scheme

binary_tree_1.scm

; sets as unordered lists:

; a set for now is defined as as being able 
; to undergo the following operations

; 1)  element-of-set? checks if x is in set
(define (element-of-set? x set)
  (cond ((null? set) false)
        ((equal? x (car set)) true)
        (else (element-of-set? x (cdr set)))))

; 2) adjoin set
; cons (set element) if element not in set
(define (adjoin-set x set)
  (if (element-of-set? x set)
      set
  (cons x set)))

; 3) intersection-set T(n) = revisit
(define (intersection-set set1 set2) 
  (cond ((or (null? set1) (null? set2)) '())
        ((element-of-set? (car set1) set2)
          (cons (car set1)
                (intersection-set (cdr set1) set2)))
        (else (intersection-set (cdr set1) set2))))
  
; intersection-set takes 2 sets
; returns a set that contains only the common elements

; sets as ordered lists - this speeds up traversal

(define (element-of-set? x set)
  (cond ((null? set) false)
        ((= x (car set)) true)
        ((< x (car set)) false)
        (else (element-of-set? x (cdr set)))))

; This is on average T(n) = revisit
(define (intersection-set set1 set2)
  (if (or (null? set1) (null? set2))
      '()
      (let ((x1 (car set1)) (x2 (car set2)))
        (cond ((= x1 x2)
               (cons x1
                     (intersection-set (cdr set1)
                                       (cdr set2))))
              ((< x1 x2)
               (intersection-set (cdr set1) set2))
              ((< x2 x1)
               (intersection-set set1 (cdr set2)))))))
  
; it can get even better than ordered lists
; binary trees
; each node of the tree holds one value/entry
; and links to 2 other nodes
; which may be empty
; the left is smaller, the right is greater

; define a tree based on procedure:
; each node will be a list of 3 items
; 1 - the entry at the node
; 2 - the left subtree
; 3 - the right subtree

(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))

; this needs a new element-of-set?
; T(n) = revisit

(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 (left-branch set)))))

; now adjoin-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))))))