리스트가있는 바이너리 검색 트리

Question

엄밀히 말하면 i와 j 사이에있는 소비 된 BST t의 모든 키 목록을 생성하는 함수 inbetweenbst: int int BST -> ilist을 (inbetweenbst ij t)로 사용하려고합니다. 이 범위의 키가있는 요소가 t이 없으면 함수는 빈 목록을 생성해야합니다. i ≤ j이라고 가정하십시오

또한 실행 시간이 O (n)이어야합니다. 여기서 n은 t의 요소 수이고 변이를 사용하지 않아야합니다.

나는 기본적으로 나무는 바로 노드하도록 변경 다음 코드로 올라와있다

:하지만 난 내 코드 실행의 O에서 (N^2) 생각

(define (bst->list t) 
    (cond 
    [(empty? t) empty] 
    [else 
    (append (bst->list (BST-left t)) (cons (BST-key t) empty) (bst->list (BST-right t)))])) 


(define (list->bst lst) 
    (cond 
    [(empty? lst) empty] 
    [else (make-BST (first lst) empty (list->bst (rest lst)))])) 

(define (inbetweenbst i j t) 
    (define bst (list->bst (bst->list t))) 
    (cond 
    [(empty? bst) empty] 
    [(and (> (BST-key bst) i) (< (BST-key bst) j)) 
      (cons (BST-key bst) (inbetweenbst i j (BST-right bst)))] 
    [else (inbetweenbst i j (BST-right bst))])) 

을 .... 어떤 제안 O (n)을 실행하게 ... 나는 O (n) 함수 이후로 append을 사용할 수 없다. 나는 단지 cons으로 제한되어있다 ... 어떤 아이디어가 도움이 되었습니까? = D

Answer 1

본인은 다음과 같이 훨씬 간단하고 효율적으로 쓸 수 bst->list 절차를 믿는다 cons 작업.그 후, 필요한 범위에서 키를 필터링하는 절차를 구축하는 것은 사소한한다 :

(define (in-between-bst i j t) 
    (filter <???> 
      (bst->list t))) 

편집 : 여기

이 let을 사용하고 cond 대신 if을 사용하지 않고 bst->list 절차입니다 :

(define (bst->list t) 
    (inorder t empty)) 

(define (inorder tree acc) 
    (cond ((empty? tree) 
     acc) 
     (else 
     (inorder (BST-left tree) 
        (cons (BST-key tree) 
         (inorder (BST-right tree) 
           acc)))))) 

Answer 2

트리를 순차적 워크리스트로 변환하는 재귀 적 방법에 대해 생각해보십시오. 재귀 호출의 결과를 트리의 왼쪽 자식에 추가 한 다음 현재 노드에 추가하고 트리의 오른쪽 자식에 대한 재귀 호출의 결과를 추가합니다. null 노드에 도달하면 재귀가 중지됩니다.

이제 원하는 범위 내의 노드에서만 작동하는 방법으로 변환하십시오. 유일한 차이점은 널 노드에 도달하거나 원하는 범위를 벗어난 노드에 도달 할 때 재귀가 중지된다는 것입니다.

코드에는 bst-> list라는 첫 번째 기능이 이미 있습니다. 원하는 범위를 벗어 났을 때 빈 트리를 반환하는 다른 cond 절을 추가하려면 함수를 수정하면됩니다. 변수 bst는 필요하지 않습니다. 이것은 단지 t입니다.

Answer 3

append 호출을 제거하는 힌트로, S- 표현식을 원자 목록에 병합하는 간단한 기능을 고려해보십시오. 다음은 순진한 버전입니다.

;; flatten : S-expr -> (listof atom) 
(define (flatten x) 
    (cond [(null? x) 
     null] 
     [(pair? x) 
     (append (flatten (car x)) 
       (flatten (cdr x)))] 
     [else 
     (list x)])) 

다른 버전이 있습니다. 되풀이 및 추가 대신에 현재 인수의 오른쪽에있는 모든 항목의 병합 된 목록을 포함하는 추가 매개 변수를 사용하는 보조 함수를 사용합니다.

;; flatten : S-expr -> (listof atom) 
(define (flatten x) 
    (flatten* x null)) 

;; flatten* : S-expr (listof atom) -> (listof atom) 
(define (flatten* x onto) 
    (cond [(null? x) 
     onto] 
     [(pair? x) 
     (flatten* (car x) 
        (flatten* (cdr x) onto))] 
     [else 
     (cons x onto)])) 

이 기술을 문제에 적용 할 수 있습니다. 단지, 내가 모든 키의 목록을 구축 할 append를 사용하지 않는 위의 코드에서

(define (bst->list t) 
    (let inorder ((tree t) 
       (acc empty)) 
    (if (empty? tree) 
     acc 
     (inorder (BST-left tree) 
       (cons (BST-key tree) 
         (inorder (BST-right tree) 
           acc)))))) 

: