バイナリ検索ツリーのリスト

Question

厳密にiとjの間にある、消費されたBST tのすべてのキーのリストを生成する関数inbetweenbst: int int BST -> ilistを（betweenbetweenbst ij t）として作成します。この範囲のキーを持つtに要素がない場合、関数は空のリストを生成するはずです。私は以下のように仮定します。

また、実行時間がO（n）でなければなりません。ここで、nはtの要素数であり、突然変異を使用しません。

私は基本的に唯一の右のノードを持つようにツリーを変更し、次のコード、が出ている

：....任意の提案を

(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^2）を考えますO（n）を実行するには...私はかなりO（n）の機能以来appendを使用することはできません、私はconsに制限されています...私はアイデアを失った、任意の提案は助けになる？ = D

Answer 1

：上記のコードで

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

、私は、すべてのキーのリストを構築するためにappendを使用していませんよcons操作。その後、必要な範囲内のキーをフィルタリングする手順を構築することは簡単でなければなりません：

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

EDIT：

ここbst->list手順はletを使用して、代わりにifのcondを使用せずに、です：

(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節を追加する（空の後とelseの前に）関数を変更するだけです。変数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)])) 

この手法を問題に適応させることができます。私は手順bst->listはこのような非常に簡単かつ効率的な方法で書くことができると信じて