;; Die ersten drei Zeilen dieser Datei wurden von DrRacket eingefügt. Sie enthalten Metadaten
;; über die Sprachebene dieser Datei in einer Form, die DrRacket verarbeiten kann.
#reader(lib "DMdA-vanilla-reader.ss" "deinprogramm")((modname set-tree) (read-case-sensitive #f) (teachpacks ()) (deinprogramm-settings #(#f write repeating-decimal #f #t none explicit #f ())))
; Schnittstelle für Mengen reeller Zahlen:
; Mengensignatur: set

(provide set empty-set add-set elem?)

; Ein Knoten besteht aus
; - einem Eintrag (real)
; - ein linker Teilbaum
; - ein rechter Teilbaum
(define-record-procedures node
  make-node
  node?
  (node-entry node-left node-right))

; Ein Binärbaum ist eins der folgenden:
; - ein leerer Baum (empty-list)
; - ein Baumknoten (node)
(define btree
  (signature (mixed empty-list
                    node)))

(: make-node (real btree btree -> node))
(: node? (any -> boolean))
(: node-entry (node -> real))
(: node-left (node -> btree))
(: node-right (node -> btree))


; Implementierung von Mengen als geordnete Listen
(define set (signature btree))

; Leere Menge
(: empty-set set)
(define empty-set empty)

; Ist ein Element in der Menge?
(: elem? (real set -> boolean))
(define elem?
  (lambda (x s)
    (cond ((empty? s) #f)
          ((= x (node-entry s)) #t)
          ((< x (node-entry s)) (elem? x (node-left s)))
          (else (elem? x (node-right s))))))
           
; Hinzufügen eines Elementes
(: add-set (real set -> set))
; Wichtig: Ordnung des Binärbaums muss garantiert werden!
(define add-set
  (lambda (x s)
    (cond ((empty? s) (make-node x empty empty))
          ((= x (node-entry s)) s)
          ((< x (node-entry s)) (make-node (node-entry s)
                                           (add-set x (node-left s))
                                           (node-right s)))
          (else (make-node (node-entry s)
                           (node-left s)
                           (add-set x (node-right s)))))))

(define set13 (add-set 1 (add-set 3 empty-set)))
(define set12 (add-set 2 (add-set 1 empty-set)))

(check-expect (elem? 1 set13) #t)
(check-expect (elem? 1 set12) #t)
(check-expect (elem? 3 set12) #f)