Bonjour à tous,

J'essai de comprendre un code trouvé sur le net concernant une implémentation d'un b-arbre en java.

J'ai trouvé le code suivant, mais il manque le main.

Je pense qu'il faut demander dans le main :
- le degré maximun de la liste des valeurs
- la liste des fils

Malheureusement je ne sais pas comment m'y prendre.

Je souhaiterai faire fonctionner ce code avec des entiers ou des caractères, ajouter, supprimer, rechercher des entiers ou caractères.

Enfin, si cela est possible, dessiner l'arbre en fonction des données saisies.

Voici donc le code qui comporte 3 classes et une interface.

J'espère avoir été assez clair et merci de votre collaboration.

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
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
class Position {
  Noeud_Balance  Contenu;      // contenu d'un nœud
  int            Indice;       // position dans le nœud 
  Position () { 
    Contenu = null; 
    Indice = 1; 
  } 
}
 
public class Arbre_Balance { 
  Position Chemin [];
  int Sommet = -1;
  Noeud_Balance Frere;
  Affichage_BAL Activite;
  private int Degre_Max;
  private int ordre; 
  public Arbre_Balance (int Ordre, Affichage_BAL X) { 
    Degre_Max = 2 * Ordre; 
    ordre = Ordre; 
    Chemin = new Position [5]; 
    Chemin[0] = new Position ();
    Chemin[0].Contenu = new Noeud_Balance (Degre_Max + 1);
    Activite = X;
  }
          // procédures internes pour lire ou ecrire les nœuds
  private void Obtenir_Frere (int Q, int Depl) { 
    Frere = Chemin[Q-1].Contenu.Ieme_Fils (Chemin[Q-1].Indice + Depl); 
  }
  private void Descendre_Fils () { 
    Noeud_Balance NB; 
    NB = Chemin[Sommet].Contenu.Ieme_Fils (Chemin[Sommet].Indice); 
    Sommet = Sommet + 1;;    // sur le bloc fils
    Chemin[Sommet].Contenu = NB;
    Chemin[Sommet].Indice = 1;
  } 
  private void Bord_Gauche () throws StopAnim { 
      // recherche de la valeur la plus à gauche du sous-arbre
    do {
      Descendre_Fils ();
      Activite.Redessiner (Sommet);
    } while (!Chemin[Sommet].Contenu.Est_Feuille ());
  } 
  private void Valeur_Suivante () {   // remontée sur un bord droit
    while ((Sommet > 0) 
         && Chemin[Sommet].Indice > Chemin[Sommet].Contenu.Degre ()) {
      Sommet = Sommet - 1;
    } 
  }
  private void Ajuster_Avec_Droite (int Q) { 
    if (Chemin[Q].Indice > Chemin[Q].Contenu.Degre () + 1) { 
                                             // chemin par le frere
      Chemin[Q - 1].Indice = Chemin[Q - 1].Indice + 1; 
      Chemin[Q].Indice = Chemin[Q].Indice-Chemin[Q].Contenu.Degre()-1;
      Chemin[Q].Contenu = Frere;
    } else if (Chemin[Q].Indice == Chemin[Q].Contenu.Degre () + 1 
                && Sommet == Q) {  
      Sommet = Sommet - 1; // valeur passee dans le pere
    }
  } 
  private boolean Recherche_Chemin (int C) throws StopAnim { 
                // recherche d'une valeur et construction du chemin
    Sommet = 0; 
    for (;;) {
      Chemin[Sommet].Indice = Chemin[Sommet].Contenu.Rang (C); 
      Activite.Redessiner (Sommet);
      if (Chemin[Sommet].Indice <= Chemin[Sommet].Contenu.Degre ()
      && C==Chemin[Sommet].Contenu.Ieme_Valeur(Chemin[Sommet].Indice))
        return true;
      if (Chemin[Sommet].Contenu.Est_Feuille ()) return false; 
      Descendre_Fils ();
    } 
  } 
  public void Positionner (int Sur) throws StopAnim {
    if (Recherche_Chemin (Sur)) return; 
    Sommet = 0;       // sur aucun élément 
    Chemin[0].Indice = Chemin[0].Contenu.Degre() + 1;
    throw new IllegalArgumentException (); // non trouvé
  } 
  public boolean A_La_Fin () { 
    return Chemin[Sommet].Indice > (Chemin[Sommet].Contenu).Degre();
  } 
  public void Ajouter (int Val) throws StopAnim {
    int Q; 
    if (Recherche_Chemin (Val)) 
      throw new IllegalArgumentException (); // déjà existant
    Chemin[Sommet].Contenu.Inserer (Chemin[Sommet].Indice, Val); 
    Activite.Redessiner (Sommet);
                                             // adjonction feuille
    Q = Sommet;
    while (Chemin[Q].Contenu.Degre() > Degre_Max) { 
                              // le nœud courant est trop gros
      if (Q == 0) {     // il faut éclater la racine
        for (int i = Chemin.length - 1; i > 0; i--) 
          Chemin[i] = Chemin[i - 1];
        Sommet = Sommet + 1;
        Chemin[0] = new Position ();
        Chemin[0].Contenu = new Noeud_Balance (Degre_Max + 1);
        Frere = new Noeud_Balance (Degre_Max + 1); 
        Val = Chemin[1].Contenu.Eclater (ordre, Frere); 
        Chemin[0].Contenu.Initialiser_Noeud
                                    (Val,Chemin[1].Contenu,Frere); 
        Chemin[0].Indice = 1;
        Ajuster_Avec_Droite (1); 
        break;
      } 
               // ce n'est pas la racine, on retrouve son père
                    // on essaie d'abord un transfert à gauche
      if (Chemin[Q - 1].Indice != 1) { 
        Obtenir_Frere (Q, -1);
        if (Frere.Degre () < Degre_Max) {  // OK
          Chemin[Q-1].Contenu.Transfert_Droite_Gauche
                   (Chemin[Q-1].Indice-1, Frere, Chemin[Q].Contenu); 
          if (Chemin[Q].Indice > 1) // ajustement du chemin:
            Chemin[Q].Indice = Chemin[Q].Indice - 1; // reste a droite
          else { // chemin par la gauche
            Chemin[Q-1].Indice = Chemin[Q-1].Indice - 1;
            if (Sommet == Q) Sommet = Sommet - 1;//valeur chez le pere
            Chemin[Q].Contenu = Frere;
            Chemin[Q].Indice = Chemin[Q].Contenu.Degre() + 1;
          } 
          Q = Q - 1;
          break;
        } 
      } 
                    // on essaie ensuite un transfert à droite
      if (Chemin[Q - 1].Indice <= Chemin[Q - 1].Contenu.Degre ()) { 
        Obtenir_Frere (Q, +1);
        if (Frere.Degre () < Degre_Max) {  // OK
          Chemin[Q - 1].Contenu.Transfert_Gauche_Droite
                    (Chemin[Q - 1].Indice, Chemin[Q].Contenu, Frere); 
          Ajuster_Avec_Droite (Q); 
          Q = Q - 1;
          break;
        } 
      } 
                    // aucun transfert, donc on éclate le bloc
      Frere = new Noeud_Balance (Degre_Max+1); 
      Val = Chemin[Q].Contenu.Eclater(ordre, Frere); 
      Chemin[Q - 1].Contenu.Inserer (Chemin[Q-1].Indice, Val, Frere);
      Ajuster_Avec_Droite (Q); 
      Activite.Redessiner (Q);
      Q = Q - 1;
    } 
    Activite.Redessiner (Q);
  }
  public void Supprimer_Courant () throws StopAnim {
    int Q;
    boolean Au_Dela_Suivant = false; 
    int Decalage;
    if (A_La_Fin ()) throw new IllegalArgumentException ();
    Q = Sommet; 
    if (!Chemin[Q].Contenu.Est_Feuille ()) {  
      Au_Dela_Suivant = true;
      Chemin[Q].Indice += 1;
      Bord_Gauche (); // recherche supérieur pour remplacement
      Chemin[Q].Contenu.Changer_Valeur(Chemin[Q].Indice - 1, 
          Chemin[Sommet].Contenu.Ieme_Valeur (Chemin[Sommet].Indice)); 
    } 
    Chemin[Sommet].Contenu.Supprimer (Chemin[Sommet].Indice); 
    Activite.Redessiner (Sommet);
           // Q pointe sur le nœud contenant la valeur supprimée
    while (Chemin[Sommet].Contenu.Degre () < ordre) {    
                               // le nœud courant est trop petit
      if (Sommet == 0) {    // c'est la racine
        if (Chemin[Sommet].Contenu.Degre() == 0 
            && ! Chemin[Sommet].Contenu.Est_Feuille()) { 
                                        // il n'y a plus rien dedans
          for (int i = 0; i < Chemin.length - 1; i++)
            Chemin[i] = Chemin[i + 1]; 
          Q = Q - 1;
        } 
        Activite.Redessiner (Sommet);
        break;
      } 
                // ce n'est pas la racine, on retrouve le père
            // on essaie d'abord un transfert depuis la droite
      if (Chemin[Sommet-1].Indice<=Chemin[Sommet-1].Contenu.Degre()) { 
        Obtenir_Frere (Sommet, +1);
        if (Frere. Degre () > ordre) {       // OK
          Chemin[Sommet - 1].Contenu.Transfert_Droite_Gauche
                              (Chemin[Sommet - 1].Indice, 
                               Chemin[Sommet].Contenu, Frere); 
          Activite.Redessiner (Sommet);
          Sommet = Sommet - 1;
          break; // pas d’ajustement du chemin
        } 
      } 
                          // on essaie ensuite depuis la gauche
      if (Chemin[Sommet-1].Indice != 1) { 
        Obtenir_Frere (Sommet, -1);
        if (Frere.Degre () > ordre) {       // OK
          Chemin[Sommet - 1].Contenu.Transfert_Gauche_Droite
                              (Chemin[Sommet - 1].Indice - 1, 
                               Frere, Chemin[Sommet].Contenu); 
          if (Sommet - 1 == Q) {// ajustement chemin:
            Q = Sommet; // valeur suivante est descendue
            Au_Dela_Suivant = false; // BC.Indice repère la valeur
          } else 
            Chemin[Sommet].Indice += 1; // decalage
          Activite.Redessiner (Sommet);
          Sommet = Sommet - 1;
          break;
        } 
          // transfert impossible, on regroupe avec celui de gauche
        Chemin[Sommet - 1].Indice -= 1;
        Decalage = Frere.Degre() + 1;
        Chemin[Sommet - 1].Contenu.Regrouper
                              (Chemin[Sommet - 1].Indice, 
                               Frere, Chemin[Sommet].Contenu);
        Chemin[Sommet].Contenu = Frere; 
        if (Sommet - 1 == Q) {  // ajustement chemin:
          Chemin[Sommet].Indice = Decalage;
          Q = Sommet;                // valeur est descendue
          Au_Dela_Suivant = false; // reperee par BC.Indice
        } else {
          Chemin[Sommet].Indice += Decalage; // decalage
        } 
      } else {        // pas de nœud à gauche, et transfert 
                    // impossible depuis la droite, on regroupe 
                    // avec celui de droite, qui a deja été lu
        Chemin[Sommet - 1].Contenu.Regrouper
                              (Chemin[Sommet - 1].Indice, 
                               Chemin[Sommet].Contenu, Frere);
      } 
      Activite.Redessiner (Sommet);
      Sommet = Sommet - 1;    // pour continuer
    } 
    Sommet = Q;
    if (Au_Dela_Suivant) Chemin[Sommet].Indice -= 1; //retour dessus
    else Valeur_Suivante (); // controle interieur au noeud
    Activite.Redessiner (Sommet);
  } 
}
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
public class Noeud_Balance {
  private int Liste_Valeurs [];
  private Noeud_Balance Liste_Fils []; 
  private int Longueur;
  private boolean EstFeuille;
  public Noeud_Balance (int Degre_Max) { 
    Liste_Valeurs = new int [Degre_Max];
    Liste_Fils = new Noeud_Balance [Degre_Max + 1]; 
    Longueur = 0;
    EstFeuille = true;
  }
  public void Initialiser_Feuille (int Val) { 
    Longueur = 1; // vider contenu eventuel
    Liste_Valeurs[0] = Val;    // y mettre la valeur
    EstFeuille = true; 
  } 
 
  public void Initialiser_Noeud (int Val_Separ, 
                                  Noeud_Balance Gauche, 
                                  Noeud_Balance Droite) {
    Longueur = 1; // vider contenu eventuel
    Liste_Valeurs[0] = Val_Separ;    // y mettre la valeur
    EstFeuille = false; 
    Liste_Fils[0] = Gauche; // mettre les 
    Liste_Fils[1] = Droite; // deux fils
  }
  public int Degre () { return Longueur ; } 
  public boolean Est_Feuille () { return EstFeuille; } 
  public int Rang (int La_Cle) { 
    int Debut = 0;                    // recherche de sa place
    int Fin = Longueur - 1;
    int Milieu;
    if (Fin < 0 || Liste_Valeurs[Fin] < La_Cle)
      return Fin + 2;
    while (Debut < Fin) { 
      Milieu = (Debut + Fin) / 2; 
      if (Liste_Valeurs[Milieu] < La_Cle ) Debut = Milieu + 1;
      else Fin = Milieu;
    } 
    return Debut + 1; 
  } 
  public int Ieme_Valeur (int Indice) { 
    return Liste_Valeurs[Indice - 1]; 
  } 
  public Noeud_Balance Ieme_Fils (int Indice) { 
    return Liste_Fils[Indice - 1]; 
  } 
  public void Inserer(int Indice, int Val) {
    for (int j = Longueur; j >= Indice; j--)           // deplacements
      Liste_Valeurs [j] = Liste_Valeurs [j - 1];
    Longueur = Longueur + 1;
    Liste_Valeurs [Indice - 1] = Val; 
  } 
  public void Inserer(int Indice, int Val, Noeud_Balance Q) {
    for (int j = Longueur; j >= Indice; j--)           // deplacements
      Liste_Valeurs [j] = Liste_Valeurs [j - 1];
    Longueur = Longueur + 1;
    Liste_Valeurs [Indice - 1] = Val; 
    for (int j = Longueur; j >= Indice + 1; j--)       // deplacements
      Liste_Fils [j] = Liste_Fils [j - 1]; 
    Liste_Fils [Indice] = Q; 
  } 
  public void Supprimer (int Indice) {
    Longueur = Longueur - 1;
    for (int j = Indice; j <= Longueur; j++)           // deplacements
      Liste_Valeurs [j - 1] = Liste_Valeurs [j]; 
    if (!EstFeuille) { 
      for (int j = Indice + 1; j <= Longueur + 1; j++) // deplacements
      Liste_Fils [j - 1] = Liste_Fils [j]; 
    } 
  } 
  public void Changer_Valeur (int Indice, int Val) { 
    Liste_Valeurs[Indice - 1] = Val; 
   }
  public int Eclater(int En, Noeud_Balance Nouveau) { 
    int Val_Separ; 
    int K; 
    Val_Separ = Liste_Valeurs[En]; 
    Nouveau.Longueur = Longueur - En - 1;
    for (K = En + 2; K <= Longueur; K++) 
      Nouveau.Liste_Valeurs[K - En - 2] = Liste_Valeurs[K - 1]; 
    if (EstFeuille) Nouveau.EstFeuille = true;
    else { 
      Nouveau.EstFeuille = false;
      for (K = En + 2; K <= Longueur + 1; K++) 
        Nouveau.Liste_Fils[K - En - 2] = Liste_Fils[K - 1]; 
    } 
    Longueur = En;
    return Val_Separ; 
  } 
  public void Regrouper (int Indice, 
                          Noeud_Balance Gauche, 
                          Noeud_Balance Droite) {
    int Degre_G = Gauche.Degre ();
    int Degre_D = Droite.Degre ();
    int K; 
    Gauche.Liste_Valeurs[Degre_G] = Liste_Valeurs[Indice-1];
    for (K = 1; K <= Degre_D; K++) 
      Gauche.Liste_Valeurs[Degre_G+K] = Droite.Liste_Valeurs[K-1];
    if (!Gauche.Est_Feuille()) {
      for (K = 1; K <= Degre_D + 1; K++) 
        Gauche.Liste_Fils[Degre_G+K] = Droite.Liste_Fils[K-1];
      } 
    Gauche.Longueur = Gauche.Longueur + Droite.Longueur + 1;
    Supprimer (Indice); 
  } 
  public void Transfert_Droite_Gauche (int Indice,
                  Noeud_Balance Gauche, Noeud_Balance Droite) { 
    Gauche.Inserer (Gauche.Longueur + 1, Liste_Valeurs[Indice - 1],
                                         Droite.Liste_Fils[0]); 
    Liste_Valeurs[Indice - 1] = Droite.Liste_Valeurs[0]; 
    Droite.Longueur = Droite.Longueur - 1;
    for (int j = 1; j <= Droite.Longueur; j++)        // deplacements
      Droite.Liste_Valeurs [j - 1] = Droite.Liste_Valeurs [j]; 
    if (!Droite.EstFeuille) { 
      for (int j = 1; j <= Droite.Longueur + 1; j++)  // deplacements
        Droite.Liste_Fils [j - 1] = Droite.Liste_Fils [j]; 
    }
  } 
  public void Transfert_Gauche_Droite (int Indice,
                  Noeud_Balance Gauche, Noeud_Balance Droite) {
    int Degre_G = Gauche.Degre ();
    for (int j = Droite.Longueur; j >= 1; j--)        // deplacements
      Droite.Liste_Valeurs [j] = Droite.Liste_Valeurs [j - 1];
    Droite.Longueur = Droite.Longueur + 1;
    Droite.Liste_Valeurs [0] = Liste_Valeurs[Indice - 1]; 
    Liste_Valeurs[Indice - 1] = Gauche.Liste_Valeurs[Degre_G - 1];
    if (!Droite.EstFeuille) {
      for (int j = Droite.Longueur; j >= 1; j--)      // deplacements
        Droite.Liste_Fils [j] = Droite.Liste_Fils [j - 1]; 
      Droite.Liste_Fils [0] = Gauche.Liste_Fils[Degre_G]; 
    } 
    Gauche.Longueur = Gauche.Longueur - 1; 
  } 
}
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
public class StopAnim extends Exception { 
  public StopAnim () {super();}
}
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
interface Affichage_BAL { 
  void Redessiner (int L_Indice) throws StopAnim;
}