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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
|
/** suppression du min (recursif) <br> la variable min va contenir la valeur du min supprimé
@param P : Noeud de depart
@param PP : Noeud parent
public boolean delMin(AVLNode PP,AVLNode P)
{
if (P.getLeft()==null) //trouvé, c'est le min
{
min=P.getValue(); //la variable globale contient le min
//on supprime le min
if (PP==null)
root=P.getRight(); //racine
else if (PP.getRight()==P)
PP.setRight(P.getRight()); //droite
else
PP.setLeft(P.getRight()); //gauche
return true;
}else //on cherche (recursif)
{
if (delMin(P,P.getLeft()))
{
//doit mettre a jour son deseq : on demande au parent de modifier son deseq uniquement
//si son fils a son deseq qui vient de passer a 0
P.setDeseq(P.getDeseq()-1); //mise a jour du deseq
return (reequilibre(PP,P)==0);
}
}
return false;
}
/** suppression recursive */
public boolean del(int val)
{
delete(null,root,val);
return true;
}
/** reequilibre un noeud pour la suppression
@param PP parent du noeud a rééquilibrer
@param P noeud a rééquilibrer
@return le nouveau désequilibre du noeud
*/
private int reequilibre(AVLNode PP,AVLNode P)
{
if (P.getDeseq()==2 || P.getDeseq()==-2) //on doit rééquilibrer
{
if (PP==null)
{
root=reequilibrage(P); //racine
return root.getDeseq();
}else if (PP.getRight()==P) //droite
{
PP.setRight(reequilibrage(PP.getRight()));
return PP.getRight().getDeseq();
}
else
{ //gauche
PP.setLeft(reequilibrage(PP.getLeft()));
return PP.getLeft().getDeseq();
}
}
return P.getDeseq();
}
/** suppression recursive
@param P Noeud a considerer
@param PP parent de P
@param val valeur du noeud a supprimer
@return true si le noeud doit mettre a jour son deseq (usage interne a la fonction récursive)
*/
private boolean delete(AVLNode PP,AVLNode P,int val)
{
if (P==null) return false;
if (P.getValue()==val) //noeud a supprimer trouvée
{
if (P.getRight()!=null && P.getLeft()!=null) //2 fils
{
int d=P.getRight().getDeseq(); //on retiens le déseq a droite pour voir s'il a changé
boolean s=delMin(P,P.getRight()); //supprime le min a droite
// System.out.println("min deleted="+min);
//la variable globale min contient le min trouvé
P.setValue(min);
if (s || (P.getRight()!=null && P.getRight().getDeseq()==0 && P.getRight().getDeseq()!=d))
{
P.setDeseq(P.getDeseq()+1); //mise a jour du desequilibre du noeud
return (reequilibre(PP,P)==0); //on rééquilibre
}
return false; //le noeud parent n'as pas besoin de mettre a jour son deseq
}else
{
if (P.getRight()!=null) //1 fils a droite
{
//efface P
if (PP==null) //racine
root=P.getRight();
else if (PP.getRight()==P)
PP.setRight(P.getRight()); //droite
else PP.setLeft(P.getRight()); //gauche
return true; //le noeud parent doit se mettre a jour
}else //1 fils a gauche
{
//efface P
if (PP==null)
root=P.getLeft(); //racine
else if (PP.getRight()==P)
PP.setRight(P.getLeft()); //droite
else PP.setLeft(P.getLeft()); //gauche
return true; //le noeud parent doit se mettre a jour
}
}
}else //c'est pas le bon noeud, on descendre plus bas
{
//appel recursif selon la valeur du noeud a supprimer
if (val<P.getValue()) //doit aller a gauche
{
if (delete(P,P.getLeft(),val))
P.setDeseq(P.getDeseq()-1);
return (reequilibre(PP,P)==0); //rééquilibrage si necessaire
}
}
else{
if (delete(P,P.getRight(),val)) //appel recusrsif vers la droite
{
P.setDeseq(P.getDeseq()+1);
return (reequilibre(PP,P)==0); //rééquilibrage si necessaire
}
}
}
- return false;
} |
Suppression dans un AVL
Répondre avec citation
Partager