Supprimer un noeud d'un arbre binaire de recherche

Suppression d'un

nœud dans un

Arbre Binaire de Recherche

C.Queinnec

Programmation récursive

(1) trouver le nœud dont la racine est l'élément
à supprimer

Si c'est une feuille, on l'élimine

mais, si au moins l'un de ses fils n'est pas vide ?

Programmation récursive

(2) Trouver le plus grand nœud à gauche

Programmation récursive

;;; max-abr: ArbreBinRecherche -> Nombre
;;; (max-abr ABR) rend le max d'un arbre binaire de recherche
;;; HYPOTHÈSE: ABR est non vide

(define (max-abr ABR)
(if (ab-noeud? (ab-droit ABR))
(max-abr (ab-droit ABR))
(ab-etiquette ABR)))

Programmation récursive

(3) Supprimer le plus grand nœud à gauche et
le replacer à la racine

Programmation récursive

;;; abr-sauf-max : ArbreBinRecherche -> ArbreBinRecherche
;;; HYPOTHÈSE: ABR est non vide
;;; (abr-sauf-max ABR) rend un arbre binaire de recherche qui
;;; contient toutes les étiquettes apparaissant dans ABR,
;;; hormis ce maximum.

(define (abr-sauf-max ABR)
(if (ab-noeud? (ab-droit ABR))
(ab-noeud (ab-etiquette ABR)
(ab-gauche ABR)
(abr-sauf-max (ab-droit ABR)))
(ab-gauche ABR)))

Programmation récursive

On peut combiner ces deux fonctions

;;; max-sauf-max : ArbreBinRecherche
;;; -> NUPLET[Nombre ArbreBinRecherche]
;;; HYPOTHÈSE: ABR est non vide
;;; (max-sauf-max ABR) rend le couple formé de la plus grande
;;; étiquette de l'arbre ABR et d'un arbre binaire de recherche
;;; qui contient toutes les étiquettes qui apparaissent dans ABR,
;;; hormis ce maximum.

(define (max-sauf-max ABR)
(if (ab-noeud? (ab-droit ABR))
(let ((m-sm-ss-ab-d (max-sauf-max (ab-droit ABR))))
(list (car m-sm-ss-ab-d)
(ab-noeud (ab-etiquette ABR)
(ab-gauche ABR)
(cadr m-sm-ss-ab-d))))
(list (ab-etiquette ABR)
(ab-gauche ABR) ) ) )

Programmation récursive

On peut, bien sûr, opérer symétriquement et, quelquefois,
c'est obligatoire!

Programmation récursive

Et voici la fonction toute entière

;;; moins-racine : ArbreBinRecherche -> ArbreBinRecherche
;;; HYPOTHÈSE: ABR non vide
;;; (moins-racine ABR) rend l'arbre binaire de recherche qui contient
;;; toutes les étiquettes qui apparaissent dans ABR hormis l'étiquette
;;; de sa racine.

(define (moins-racine ABR)
(cond ((not (ab-noeud? (ab-gauche ABR)))
(ab-droit ABR))
((not (ab-noeud? (ab-droit ABR)))
(ab-gauche ABR))
(else ; défaire le ss-ab-g --> max + ABR privé du max
(let ((m-sm-ss-ab-g (max-sauf-max (ab-gauche ABR))))
(ab-noeud (car m-sm-ss-ab-g)
(cadr m-sm-ss-ab-g)
(ab-droit ABR))))))

Programmation récursive