二叉搜索树与列表

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

您或许可以将此技术应用于您的问题。