Löschen eines Elements aus einem BST in Schema

Question

Ich kann nicht herausfinden, wie ein Element aus dem BST zu löschen. Das ist mein Code

(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))))))) 

Minimum gibt den Mindestwert im Baum zurück. Wenn ich versuche, ein Element zu löschen, das kein Blatt ist, geht es in eine Endlosschleife. Wie kann ich es reparieren?

Answer 1

Ich denke, Ihr größtes Problem in diesem Abschnitt liegt:

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

Du r von t entfernen, aber Sie sollten wirklich r vom rechten Teilbaum von t werden entfernt. Ich bin nicht sicher, warum Sie auch Mutabilität/Einstellung verwenden; Ich denke, es macht Dinge komplizierter, was leicht eine Nebeneffektfunktion sein könnte. Ich würde versuchen, etwas wie:

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

Ich muss auch zugeben, dass ich ein bisschen verwirrt über Ihre Absicht mit der letzten Zeile bin. Wofür verwendest du die leere Liste?

Answer 2

Als Alternative können Sie einen Blick hier für die gesamte Umsetzung von BST in Schema nehmen:

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

Es ist sehr gut dokumentiert ist und Sie einen kleinen Einblick geben würde, So können Sie den Code so strukturieren, dass er leicht zu lesen und zu debuggen ist. Insbesondere behandelt es Blatt- und Knoten (Nicht-Blatt) -Entnahmen separat.