Discussion :

[chouki]

Bonjour à tous je viens de trouver le code source de la supprssion dans un AVL, mais y'a une petite instruction qui m'intrigue

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
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;
    }

Le return false c'est cette instruction qui mintrigue, si c'est un return false cela veut dire que je peux pas termnier l'execution du reste des appels recursif

Code :

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

1
2
if  (delete(P,P.getLeft(),val))  //suppression à gauche
P.setDeseq(P.getDeseq()-1);

Ce qui signifie que je met pas à jour le déséquilibre du pére du noeud qui a été supprimé, mais en principe sa se passe pas comme sa on doit mettre a jour le desq du pére, et du grd pére...jusqu'a à la racine puisque ces des appel récursifs..et c'est en fonction du deséquilibre qu'il peut y'avoir réequilibrage si nécessaire

Code :

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

return (reequilibre(PP,P)==0);//rééquilibrage si necessaire

Cordialement

[FR119492]

Salut !
Quelle est la relation entre ta question et la localisation automatique des véhicules ?
Jean-Marc Blanc

[chouki]

Heu, je suis dans un forum d'algorithmique non!

[pseudocode]

Quelle est la relation entre ta question et la localisation automatique des véhicules ?

A mon avis il parle des arbres AVL (Adelson-Velsky & Landis).

D'ou elle vient cette implémentation ?

Sinon il y a une implémentation dans le TreeList de Apache Commons Collections.

[FR119492]

A mon avis il parle des arbres AVL (Adelson-Velsky & Landis)

Peut-être, mais il devrait le dire au lieu d'utiliser des abréviations qui prêtent à confusion.

je suis dans un forum d'algorithmique non

Automatic Vehicles Localisation (AVL) est aussi basé sur des algorithmes sophistiqués.

Un principe fondamental est qu'on ne peut utiliser des abréviations dans un document qu'à la condition de les précéder du terme complet lors de leur première occurrence.
Jean-Marc Blanc

[chouki]

J'aurais du préciser avec Arbre AVL

Finalement au niveau de ce code la récursivité est mal gérée, je vais chercher pour voir si il y'a un code meilleur que celui la

Cordialement