Corrigé 25. Enoncé
1. Mécanismes de construction dans un arbre de recherche
m-aire et dans un arbre B
Modèle sur le noeud
Logiquement, un noeud renferme les informations suivantes:
- au maximum n fils
- au maximum (n-1) clés avec les adresses vers les articles du fichier de données
- Nombre courant de clés dans le noeud
Dans les algorithmes qui suivent Ordre désigne l'ordre de l'arbre.
Le modèle peut être l'ensemble des opérations suivantes :
Nbr(Bloc) : nombre de clés du noeud contenu dans le bloc Bloc
Fils(Bloc, I) : accès au I-ième fils du noeud contenu dans le bloc
Bloc.
Clé(Bloc, I) : accès a la I-ième clé du noeud contenu dans le
bloc Bloc.
Aff_Nbr(Bloc, V): mise à jour du champ Nombre du bloc par la valeur V.
Aff_Fils(Bloc, I, P) : mise à jour du champ "I-ième
fils" du bloc par le pointeur P.
Aff_Clé(Bloc, I, Clé) : mise à jour du champ "I-ième clé" du bloc Bloc par
la clé Cle.
Adr(Bloc, I) : adresse de l'article correspondant à la I-ième clé.
Aff_Adr(Bloc, I, Adr) : mise à jour du champ " I-ième adresse vers
l'information" du bloc Bloc par l'adresse Adr.
Dans les algorithmes qui suivent on utilise le module Insererfichier(Fdon, Clé, Adresse)
qui insère l'article réduit à sa clé Clé dans le fichier des données Fdon et qui
rend dans la variable Adresse, l'adresse de l'article inséré.
Algorithme de recherche d'un article de clé donnée
Définissons d'abord le module Rech (Bloc, Clé, I) qui détermine l'indice I de la plus
petite Clé supérieure ou égale à Clé dans le bloc Bloc.
Trouv := FAUX
I := 1
TANTQUE NON Trouv ET I <= Nbr(Bloc) :
SI Clé(Bloc,I) >= Clé :
Trouv := VRAI
SINON I := I + 1 FSI
FINTANTQUE
L'algorithme qui suit recherche la Clé Clé dans l'arbre de recherche m-aire Arbre.
Si la clé est trouvée :
- Trouv est vrai,
- P pointe le numéro du bloc contenant la clé,
- I est la position de Clé dans le bloc ( ou le noeud).
Si la clé n'est pas trouvée :
- Trouv est faux,
- Q pointe le noeud qui devrait contenir la clé si elle était présente,
- I est la position de la plus petite clé supérieure à Clé.
Findex est le fichier contenant l'arbre de recherche m-aire.
Q := NIL
P := Arbre
Trouv := FAUX
TANTQUE P # NIL ET NON Trouv :
Lirebloc(Findex, P, Bloc)
Rech(Bloc, Clé, I)
Q := P
SI Clé = Clé(Bloc, I)
Trouv := VRAI
SINON P := Fils(Bloc, I) FSI
FINTANTQUE
Listage des articles en ordre croissant
Soit Arbre la racine de l'arbre de recherche m-aire ( c'est donc l'adresse de la page
racine).
Parcours( Arbre) :
SI Arbre # NIL :
Lirebloc(Findex, Arbre, Bloc)
Nt := Nbr(Bloc)
POUR I = 1, Nt :
Parcours( Fils(Bloc, I)
)
Ecrire ( Clé ( Bloc,
I) )
FINPOUR
Parcours( Fils( Bloc, Nt+1) )
FSI
Algorithme d'insertion dans un arbre de recherche m-aire "Top
Down"
Définissons d'abord le module Insérer-feuille( Bloc, Pos, Clé, Adresse) qui insère la
paire (Clé, Adresse) comme Pos-ième fils dans le bloc Bloc.
Nt := Nbr(Bloc)
Aff_Nbr(Bloc, Nt + 1)
POUR I = Nt, Pos, -1 :
Aff_Clé( Bloc, I+1, Clé(Bloc, I))
Aff_Adr( Bloc, I+1, Adr(Bloc, I))
FINPOUR
Aff_Clé(Bloc, Pos, Clé)
Aff_Adr(Bloc, Pos, Adresse)
Le module d'insertion d'une clé dans un arbre de recherche m-aire est le suivant :
SI Arbre = NIL :
Insererfichier( Fdon, Clé, Adresse)
Aff_Nbr(Bloc, 1); Aff_Clé(Bloc, 1, Clé) ;
Aff_Adr(Bloc, 1, Adresse)
POUR I =1, Ordre { Ordre de l'arbre }
Aff_Fils(Bloc, I, NIL)
FINPOUR
Allouer(P) {Allocation d'un bloc sur le disque}
Ecrirebloc(Findex, P, Bloc)
Arbre := P
SINON
Recherche( Arbre, Clé, Trouv, Q, I)
SI NON Trouv : { Bloc contient le noeud Q }
Insererfichier(Fdon,
Clé, adresse)
SI Nbr(Bloc) < Ordre
- 1
Insérer-Feuille(Bloc, I,Clé, Adresse)
Ecrirebloc(Findex, Q, Bloc)
SINON
Allouer(R)
Aff_Fils(Bloc, I, R)
Ecrirebloc(Findex, Q, Bloc)
Aff_Nbr(Bloc, 1)
Aff_Cle( Bloc,1, Clé)
Aff_Adr(Bloc, 1, Adresse)
POUR J =1, Ordre
Aff_Fils(Bloc, J, NIL)
FINPOUR
Ecrirebloc(Findex, R, Bloc)
FSI
SINON " Clé dejà insérée " FSI
FSI
Insertion dans un arbre B d'ordre n
Considérons d'abord les deux modules suivants :
1. Insertion de la paire ((Clé, Adresse), Nouveaunoeud) dans un noeud à une position
donnée.
Nous supposons que la taille du bloc de données est égale à Ordre + 1, ce qui nous
permet d'insérer la paire ((Clé, Adresse), Nouveaunoeud) même quand le noeud est plein.
Insérernoeud( Pos, Clé, Adresse, Nouveaunoeud)
Nt := Nbr(Bloc)
Aff_Nbr(Bloc, Nt + 1)
POUR I = Nt, Pos, -1
Aff_Fils(Bloc, I+2, Fils(Bloc, I+1) )
Aff_Clé(Bloc, I+1, Clé(Bloc, I))
Aff_Adr(Bloc, I+1, Adr(Bloc, I))
FINPOUR
Aff_Fils(Bloc, Pos+1, Nouveaunoeud )
Aff_Clé(Bloc, Pos, Clé)
Aff_Adr(Bloc, Pos, Adresse)
2. Module de division
En entrée :
Nd : le numéro du noeud à diviser
Pos : la position à laquelle doit être insérée la paire (( Clé,
Adresse), Nouveaunoeud)
En sortie :
Nd2 : le nouveau noeud de droite créé et
Clémilieu : la clé du milieu à mettre dans le noeud père.
Adrmilieu: l'adresse du milieu à mettre dans le noeud père.
Findex est le fichier contenant l'arbre B.
Insérernoeud( Pos, Cle, Adresse, Nouveaunoeud)
Sauv_Nbr := Nbr(Bloc)
I := ( Nbr(Bloc) DIV 2 ) + 1
Aff_Nbr(Bloc, I - 1)
Ecrirebloc(Findex, Nd, Bloc)
K := 0
POUR J=I+1, Sauv_Nbr
K := K + 1
Aff_Fils(Bloc, K, Fils(Bloc, J) )
Aff_Clé(Bloc, K, Clé(Bloc, J))
Aff_Adr(Bloc, K, Adr(Bloc, J))
FINPOUR
Aff_Fils(Bloc, K+1, Fils(Bloc, Sauv_Nbr+ 1))
Aff_Nbr(Bloc, K)
Allouer(Nd2)
Ecrirebloc(Findex, Nd2, Bloc)
Clémilieu := Clé(Bloc, I)
Adrmilieu := Adr(Bloc, I)
L'algorithme d'insertion d'une clé dans un arbre B est alors le suivant ( cas o� la clé
n'existe pas ) :
On utilise l'opération Père et Index pour remonter dans l'arbre. Père fournit un noeud
et Index une position dans le noeud.
On peut éviter ces deux opérations en construisant une pile des noeuds parcourus par le
module de recherche.
SI Arbre = NIL
Insererfichier(Fdon, Clé, Adresse)
Aff_Nbr(Bloc, 1) ; Aff_Cle(Bloc, 1, Clé) ;
Aff_Adr(Bloc, 1, Adresse)
Aff_Fils(Bloc, 1, NIL) ; Aff_Fils(Bloc, 2, NIL)
Allouer(P) {Allocation d'un bloc sur le disque}
Ecrirebloc(Findex, P, Bloc)
Arbre := P
SINON
Recherche (Arbre, Clé, Trouv, Nd, Pos)
SI NON Trouv :
Insererfichier(Fdon,
Clé, Adresse)
Nouveau_Noeud := NIL
Nouvelle-Clé := Clé
Nouvelle_Adresse :=
Adresse
F := Père(Nd)
TANTQUE F # NIL ET
Nbr(Bloc) = Ordre - 1 :
Sauv_Pos := Index(F)
Diviser(Nd , Nouvelle-Clé, Nouvelle_Adresse, Pos,
Nouveau_Noeud, Nd2, Clé-Milieu , Adr_Milieu)
Nouveau_Noeud := Nd2
Pos := Sauv_Pos
Nd := F
Lirebloc(Findex, F, Bloc)
F := Père(Nd)
Nouvelle_clé := Clé_Milieu
Nouvelle_Adresse := Adresse_Milieu
FINTANTQUE
SI Nbr(Bloc) < Ordre
- 1 :
Insérernoeud(Pos, Nouvelle_Clé, Nouvelle_Adr, Nouveau_Noeud)
Ecrirebloc(Findex, Nd, Bloc)
SINON
{ F = NIL ET Nbr(Bloc) = Ordre - 1
Donc création d'une nouvelle racine }
Diviser(Nd, Nouvelle_Clé, Nouvelle_Adresse, Pos,
Nouveau_Noeud, Nd2, Clé_Milieu, Adr_Milieu)
Aff_Nbr(Bloc, 1)
Aff_Fils(Bloc, 1, Nd)
Aff_Fils(Bloc, 2, Nd2)
Aff_Clé(Bloc, 1, Clé_Milieu)
Aff_Adr(Bloc, I, Adr_Milieu)
Allouer(Arbre)
Ecrirebloc( Findex, Arbre, Bloc)
FSI