Suppression d'un élément d'un BST dans le schéma

Question

Je n'arrive pas à comprendre comment supprimer un élément du BST. Ceci est mon 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))))))) 

Le minimum renvoie la valeur minimale dans l'arborescence. Si j'essaie de supprimer un élément qui n'est pas une feuille, il passe dans une boucle infinie. Comment puis-je le réparer?

Answer 1

Je pense que votre plus gros problème réside dans cette section:

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

Vous retirez r de t, mais vous devriez vraiment supprimerons r du sous-arbre droit de t. Je ne suis pas sûr de savoir pourquoi vous utilisez mutabilité/réglage, soit; Je pense que cela complique les choses dans ce qui pourrait facilement être une fonction sans effet secondaire. Je voudrais essayer quelque chose comme:

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

Je dois aussi admettre que je suis un peu confus au sujet de votre intention avec la dernière ligne. À quoi utilisez-vous la liste vide?

Answer 2

Comme alternative, vous pouvez jeter un oeil ici pour la mise en œuvre l'ensemble de la BST dans le schéma:

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

Il est très bien documenté et vous donnerait un peu de perspicacité au sujet la façon dont vous pouvez structurer le code pour qu'il soit facile à lire et à déboguer. En particulier, il traite les retraits de feuilles et de nœuds (non-feuilles) séparément.