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 nud int Indice; // position dans le nud 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 nuds 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 nud 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 nud contenant la valeur supprimée while (Chemin[Sommet].Contenu.Degre () < ordre) { // le nud 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 dajustement 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 nud à 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; }![]()
Partager