Enoncé 25 : Arbres de recherche m-aires - Arbres B  Corrigé 25

Problème : Mécanismes de construction d'un arbre de recherche m-aire et d'un arbre B

Un arbre de recherche m-aire d'ordre n (arm) est un arbre dans lequel chaque nœud a au plus n fils et (n-1) clés. Logiquement la structure d'un nœud est la suivante:

(p1, k1, p2, k2, ... ,kn-1, pn)

Toutes les clés strictement inférieures à k1 sont dans le sous arbre pointé par p1.

Toutes les clés supérieures à kn-1 sont dans le sous arbre pointé par pn.

Toutes les clés supérieures à ki-1 et inférieures à ki sont dans le sous arbre pointé par pi, i= 2, 3, .. , n-1.

On convient de choisir un arm comme méthode d'accès à un fichier. Chaque nœud représente alors un bloc sur le disque. Le bloc est l'unité de transfert entre la mémoire principale et le disque. Dans chaque nœud et pour toute clé on ajoute un pointeur vers l'information qui se trouve dans un autre fichier structuré sous forme d'un ensemble de blocs contigus. Nous supposons que l'article est réduit à sa clé.

On veut aussi écrire les algorithmes indépendamment de la structure du nœud. Par conséquent, il faut définir un modèle sur le nœud qui est un ensemble d'opérations paramètrées. Par exemple, si Bloc est le buffer contenant un nœud de l'arm, on peut définir :

- Fils(Bloc, I) : accès au I-ième fils du nœud.

- Clé(Bloc, I) : accès à la I-ième clé du nœud.

Etc...

Algorithmes demandés :

* Recherche d'un article de clé donnée

* Listage de toutes les clés du fichier en ordre croissant

Un arm est dit TOP-DOWN si tout nœud non rempli est une feuille. Quand un nœud est rempli, on crée un autre nœud dans lequel on met la donnée et on fait du nœud créé un fils du nœud plein.

** Ecrire l'algorithme d'insertion d'un article de clé donnée.

On veut changer la manière de construire l'arm. Quand un nœud est rempli, on l'éclate en deux nœuds selon la clé du milieu. Cette dernière est transférée dans le nœud père, à moins que celui-ci est plein auquel cas on l'éclate de la même manière. Et récursivement...

*** Donner l'algorithme d'insertion

On utilisera le module Insérerfichier( Fdon, Clé, Adresse) qui insère l'article réduit à sa clé Clé dans le fichier des données Fdon et qui rend dans Adresse l'adresse de l'article inséré.

* * * * *