Двоичное дерево поиска со списками - PullRequest
Новая
       10

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

2 голосов
/ 04 марта 2012

Я хочу создать функцию inbetweenbst: int int BST -> ilist, используемую как (inbetweenbst i j t), которая создает список всех ключей в потребляемом BST t, которые находятся строго между i и j. Если в t нет элементов с ключом в этом диапазоне, то функция должна создать пустой список. Предположим, что я ≤ 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

Ответы [ 3 ]

2 голосов
/ 04 марта 2012

Я полагаю, что процедуру 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))))))
1 голос
/ 04 марта 2012

Начните с размышления о рекурсивном методе преобразования дерева в список путем обхода по порядку. Добавьте результат рекурсивного вызова к левому дочернему элементу дерева, затем к текущему узлу, а затем результат рекурсивного вызова к правому дочернему элементу дерева; рекурсия останавливается при достижении нулевого узла.

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

В вашем коде у вас уже есть первая функция, которая называется bst-> list. Все, что вам нужно сделать, это изменить функцию, добавив еще одно условие cond (после пустого? И перед другим), чтобы оно возвращало пустое дерево, когда вы находитесь за пределами желаемого диапазона. Нет необходимости в переменной bst, т. Е. Просто t.

0 голосов
/ 04 марта 2012

В качестве подсказки по устранению вызовов 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)]))

Вот альтернативная версия.Вместо повторения и добавления, он использует вспомогательную функцию, которая принимает дополнительный параметр, который содержит плоский список всего справа от текущего аргумента.проблема.

...