라켓에 이진 검색 트리를 만드시겠습니까?

Question

변경할 수없는 이진 검색 트리를 만들려고합니다. 나는 빈리스트를 생성하기 위해 생성자를 생성하고 다음 코드를 사용하여 트리에 하나씩 요소를 추가하는 메서드로 시작했다.

#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 

내가 불변을 의미하는 것은 내가 '()
(define b1 (addToTree b0 4 "4"))
b1이 '(4 "4"()())
(define b2 (addToTree b1 6 "6"))
b2이 ... '(4 "4"() (6 "6"()()))
등을 반환해야합니다 반환해야합니다 반환해야
b0(define b0 (constructTree))를 호출하는 경우 입니다.
하지만이 오류가 발생합니다 : 응용 프로그램 : 프로 시저가 아닙니다; 주어진 인수에 적용 할 수있는 절차는 다음과 같습니다. '(3) arguments ... :
이 오류가 발생하는 이유는 무엇입니까? 미리 감사드립니다.

Answer 1

난 당신이 뭔가를 찾고있을 것 같아요 : 불변성 때문에, 새로운 빈 나무마다를 구성 할 필요가 없습니다

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

하는 것으로. emptyTree을 빈 목록의 별칭으로 만들면됩니다.