Algorithme de suppression d'un élément dans un arbre binaire de recherche

**mohsenuss91** · 20/12/2011, 18h51

salut a tous !
S.V.P, Je cherche l'algorithme de suppression d'un élément dans un arbre binaire de recherche !
voila mes essais

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
type abr=^elt;
elt=enregistrement
val:entier;
g,d:abr;
fin;
......
......
......
fonction recherche(a:abr;v:entier):abr
debut
si (a=null)alors recherche<==null
sinon si (a^.val=v)alors recherche<==a
sinon si (a^.val>v) alors recherche <==recherche(a^.g,v)
sinon recherche <==recherche (a^.d,v);
fin;
......
......
......
fonction succ(var a:abr):abr
var p:abr;
debut
si (a<>null)alors
debut
si (a^.d<>null) alors
debut
p<==a^.d;
tantque(p^.g^.g<>null)alors p<==p^.g;
fin;
succ<==p;
fin;
fin;
......
......
......
procedure supp(a:abr;v)
var x:abr; 
debut
x<==recherche(a,v);
si (x=null)alors ecrire"la valeur que vous voulez supprimé nexiste pas dans cet arbe"
sinon
debut
si((x^.g=null)et(x^.d=null)) alors dispose(x)
sinon si ((x^.d<>null)et(x^.g=null))alors
debut
s<==succ(x);
x^.val<==s^.val;
dispose(s);
fin
sinon si((x^.d<>null)et(x^.g<>null))alors
debut
s<==succ(x);
x^.val<==s^.val;
dispose(s);
fin
sinon
debut
x^.val<==x^.g^.val;
dispose(x^.g);
fin;
fin;

j'ai trouvé l'idée sur wiki (mais honnêtement j'ai pas pu le faire):
plusieurs cas sont à considérer, une fois que le nœud à supprimer a été trouvé à partir de sa clé :

* Suppression d'une feuille : Il suffit de l'enlever de l'arbre vu qu'elle n'a pas de fils.
* Suppression d'un nœud avec un enfant : Il faut l'enlever de l'arbre en le remplaçant par son fils.
* Suppression d'un nœud avec deux enfants : Supposons que le nœud à supprimer soit appelé N (le nœud de valeur 7 dans le graphique ci-dessous). On le remplace alors par son successeur le plus proche (le nœud le plus à gauche du sous-arbre droit - ci-dessous, le nœud de valeur 9) ou son plus proche prédécesseur (le nœud le plus à droite du sous-arbre gauche - ci-dessous, le nœud de valeur 6). Cela permet de garder une structure d'arbre binaire de recherche. Puis on applique à nouveau la procédure de suppression à N, qui est maintenant une feuille ou un nœud avec un seul fils.

Pour une implémentation efficace, il est déconseillé d'utiliser uniquement le successeur ou le prédécesseur car cela contribue à déséquilibrer l'arbre.

Dans tous les cas cette opération requiert de parcourir l'arbre de la racine jusqu'à une feuille : le temps d'exécution est donc proportionnel à la profondeur de l'arbre qui vaut n dans le pire des cas, d'où une complexité maximale en O(n).