Удаление элемента из BST в схеме

Question

Не могу понять, как удалить элемент из BST. Это мой код

(define remove (lambda (x t)
       (if  (< x (car t)) (list (car t) (remove x (cadr t)) (caddr t))
             (if (> x (car t)) (list (car t) (cadr t) (remove x (caddr t)))
                   (if (not(and (null? (cadr t)) (null? (caddr t)))) 
                       (let ((r (minimum (caddr t)))) ((remove r t) (set-car! t r))) 
                       (list '() (cadr t) (caddr t)))))))

Минимум возвращает минимальное значение в дереве. Если я пытаюсь удалить элемент, который не является листом, он входит в бесконечный цикл. Как я могу это исправить?

Answer 1

Я думаю, что ваша самая большая проблема заключается в этом разделе:

((remove r t) (set-car! t r))

Вы удаляете r из t, но вы действительно должны удалить r из правого поддерева t. Я не уверен, почему вы используете изменчивость / настройки, либо; Я думаю, что это усложняет то, что легко может быть функцией без побочных эффектов. Я бы попробовал что-то вроде:

(list r (cadr t) (remove r (caddr t)))

Я также должен признать, что меня немного смущает ваше намерение по поводу последней строки. Для чего вы используете пустой список?

Answer 2

В качестве альтернативы вы можете посмотреть всю реализацию BST в схеме:

• http://en.literateprograms.org/Binary_tree_(Scheme)

Он очень хорошо документирован и даст вам некоторое представление о том, как вы можете структурировать код, чтобы его было легко читать и отлаживать. Особенно это относится к удалению листьев и узлов (не листьев) отдельно.