list - 带列表的二叉搜索树

Question

我想创建一个函数 in Betweenbst: int int BST -> ilist，用作 (in Betweenbst i j t)，它生成所使用的 BST t 中严格位于 i 之间的所有键的列表和 j。如果 t 中没有任何元素的键在此范围内，则该函数应生成一个空列表。假设 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))))))