binäre Suchbaum im Schläger erstellen?

Question

versuchen, unveränderlichen binären Suchbaum zu erstellen. Ich habe mit create constructor begonnen, um eine leere Liste zu erstellen, und mit der Methode, Element zu Tree hinzuzufügen, indem ich den folgenden Code benutze.

#lang racket 
(define (constructTree) '()) 

(define (addToTree Tree k v) 

(cond [(null? Tree) 
      (cons Tree cons((cons k '()) v))] 
     [else 
     (cond [(>(car Tree) k) 
       (cons Tree cons((cons k '()) v)) 
       ] 
       [else 
       (cons Tree '() cons((cons k '()) v)) 
       ] 
      )] 
    ) 
) 


(define bst (addToTree (addToTree (addToTree (addToTree (constructTree)3 "3") 1 "1") 2 "2") 5 "5")) 
bst 

, was ich durch unveränderliche meine ist wenn ich (define b0 (constructTree)) nennen
b0 sollte zurückkehren '()
(define b1 (addToTree b0 4 "4"))
b1 zurückkehren sollte '(4 "4"()())
(define b2 (addToTree b1 6 "6"))
b2 zurückkehren sollte '(4 "4"() (6 "6"()()))
... etc.
aber ich bekomme diesen Fehler: Anwendung: keine Prozedur; erwartet eine Prozedur, die auf Argumente angewendet werden kann gegeben: '(3) Argumente ...:
keine Ahnung, warum ich diesen Fehler bekomme oder was ich falsch mache? Vielen Dank im Voraus.

Answer 1

Ich denke, man kann für so etwas suchen:

(define emptyTree '()) 

(define (addToTree Tree k v) 
    (match Tree 
    ['() 
    (list k v '() '())] 
    [(list key val left right) 
    (if (> k key) 
     (list key val left (addToTree right k v)) 
     (list key val (addToTree left k v) right))])) 

Beachten Sie, dass aufgrund der Unveränderlichkeit, es gibt keine Notwendigkeit, einen neuen leeren Baum jedes Mal zu konstruieren. Sie können einfach emptyTree einen Alias ​​für die leere Liste machen.