二叉搜索樹與列表

Question

我想創建一個功能inbetweenbst: int int BST -> ilist，作爲（inbetweenbst I J T），產生全部消耗BST牛逼是嚴格i和j之間的鍵的列表。如果在這個範圍內沒有任何元素，那麼該函數應該產生一個空列表。假設我≤Ĵ

此外，我必須確保運行時間必須是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）...我很漂亮，我不能使用append，因爲它的一個O（n）函數，我只限於cons ...我迷失在想法中，任何建議都會有幫助嗎？ = d

Answer 1

我相信bst->list可以寫成一個更簡單和有效的方法是這樣的過程：

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

編輯：

這裏是bst->list程序，而無需使用let和使用cond代替if：

(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

由想着遞歸方法通過有序步行到一棵樹轉換到一個列表開始。將遞歸調用的結果附加到樹的左側子節點，然後是當前節點，然後將遞歸調用的結果添加到樹的右側子節點;當您到達空節點時，遞歸會停止。

現在將其轉換爲僅在所需範圍內的節點上運行的方法。唯一的區別是當你到達一個空節點時，或者當你到達一個超出所需範圍的節點時遞歸停止。

在代碼中，你已經擁有了第一個功能，稱爲BST->列表。所有你需要做的就是修改函數來添加另一個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)])) 

您或許可以將此技術應用於您的問題。