Skip to content

Instantly share code, notes, and snippets.

@abhi18av
Forked from zallarak/binary_tree_1.scm
Created January 15, 2020 15:32
Show Gist options
  • Save abhi18av/85576e3f865358be2106e254e8985e50 to your computer and use it in GitHub Desktop.
Save abhi18av/85576e3f865358be2106e254e8985e50 to your computer and use it in GitHub Desktop.
Binary trees in Scheme
; 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))))))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment