Problème : Arbre de recherche m-aire comme structure de fichiers

Fichier De ( Entier ,Vecteur ( 10 ) De Chaines ,Vecteur ( 10 ) De Entiers ,) Buffer Bufdon ;

L’entier désigne le nombre courant d’articles (clés) par bloc

Le premier vecteur : les articles ( clés )

Le deuxième vecteur : les adresses de blocs.

Initialisation

Ecrire le module Init qui initialise

- le fichier avec un seul bloc racine (bloc 1) contenant la plus grande valeur de clé possible (‘zzzz’) 

- les différents paramètres.

Recherche

Ecrire le module Rech( Cle, I) qui recherche séquentiellement dans le buffer courant la plus petite clé supérieure ou égale à Clé , rend l’indice I de l’élément trouvé.

Utiliser Rech pour Ecrire le module Recherche (Cle, trouv , q, i) qui recherche Cle dans le fichier. Si la clé n’est pas trouvée, Trouv = FAUX, Q pointe le nœud feuille et I l’indice de la plus petite clé supérieure ou égale à Cle.

Insertion

Ecrire le module Inserer_nœud ( pos, clé, -1) qui insère la paire ( Cle, -1) à la position P dans le buffer courant.

Utiliser Recherche et Inserer_nœud pour écrire le module Inserer (Cle) permettant d’insérer une clé dans le fichier

Parcours

Lister le fichier en ordre croissant.

Réorganisation

A la suite d’insertions répétées, l’arbre peut se déséquilibrer. Concevoir le module de réorganisation qui consiste donc à reconstruire un autre arbre de recherche m-aire équilibré en suivant les deux étapes suivantes :

1.Construire un fichier TOF (Tableau Ordonné Fixe) contenant toutes les clés du fichier

2. Parcourir dichotomiquement ce fichier pour construire un nouvel arbre de recherche m-aire.