Двоичное дерево поиска со списками

Question

Я хочу создать функцию inbetweenbst: int int BST -> ilist, используемую как (inbetweenbst 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))) 

EDIT:

Вот 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-> 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)])) 

Возможно, вы сможете адаптировать эту технику к своей проблеме.