Удаление элемента из 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)

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