Les arbres generaux1
Les arbres généraux 1. Introduction Comme mentionné au chapitre précédent, un arbre est général si les nombre d’enfants est variable pour les nœuds. Dans ce chapitre, nous allons, dans un premier temps, discuter des différentes implantations de ces arbres, et, dans un deuxième temps, étudier une classe particulière d’arbres généraux: les B-arbres.
légende : - Subtree rooted at V : sous-arbre enraciné à V
- Children of V: enfants de V - Siblings of V: soeurs/frères de V - Root : racine
2. Différentes implantations Avant de discuter des différentes implémentations d’un arbre général, regardons d’abord les différentes opérations que nous pourrions effectuer dans un arbre. La première étant d’accéder à la racine. Une autre est d’accéder aux enfants d’un nœud. Dans un arbre binaire, cette dernière opération est possible en utilisant des fonctions qui donnent des accès explicites à l’enfant gauche et enfant droit de ce nœud. Malheureusement, cette manière de procéder n’est pas possible dans le cas d’un arbre général, pour la simple raison que le nombre d’enfants n’est pas connu à priori. Une alternative est d’avoir une fonction qui prend en paramètre l’indice de l’enfant à visiter combinée à une autre fonction qui retourne le nombre d’enfants d’un nœud donnée est capable de supporter l’accès à un nœud donné ou traiter tous les nœuds. Cette manière de faire favorise l’utilisation d’un tableau (pourquoi?). En pratique, une implémentation basée sur les pointeurs est
2
souvent préférée. Une autre alternative consiste à avoir accès à l’enfant le plus à gauche d’un nœud, et une autre fonction qui a accès au frère/sœur de droite d’un nœud. Ce qui suit montre la déclaration de classes pour les arbres généraux et leur nœuds basée sur cette approche. // classe nœud pour arbre général template <class Elem> class GTNode { public: GTNode(const Elem&); // Constructeur 1 GTNode(const Elem&, GTNode<Elem>*, GTNode<Elem>*, GTNode<Elem>*); // Constructeur 2 ~GTNode(); // Destructeur Elem value(); // Retourne la valeur du noeud bool isLeaf(); // VRAI si le nœud est une feuille GTNode* parent(); // Retourne le parent GTNode* leftmost_child(); // Retourne le premier enfant GTNode* right_sibling(); // Retourne le frère de droite void setValue(Elem&); // Assigne une valeur au noeud void insert_first(GTNode<Elem>* n); // insère comme premier enfant void insert_next(GTNode<Elem>* n); // insère comme frère de droite void remove_first(); // Enlève le premier enfant void remove_next(); // Enlève le frère de droite }; // Classe arbre general class GenTree { private void printhelp(GTNode*); // print helper function public: GenTree(); // Constructeur ~GenTree(); // Destructeur void clear(); // libère les noeuds GTNode* root(); // Retourne la racine void newroot(Elem, GTNode*, GTNode*); // fusionne deux arbres };
3
Parcours d’un arbre général template <class Elem> void GenTree<Elem>:: printhelp(GTNode<Elem>* subroot) { if (subroot->isLeaf()) cout << "Leaf: "; else cout << "Internal: "; cout << subroot->value() << "\n"; for (GTNode<Elem>* temp = subroot->leftmost_child(); temp != NULL; temp = temp-> right_sibling()) printhelp(temp); }
Réponse : R A C D E B F 2.1. Implantation par le parent : Chaque nœud contient une valeur et un pointeur à son parent. Les pointeurs parents sont représentés par la position du parent dans le tableau. Cette représentation est souvent utilisée quand on veut savoir si deux objets sont dans le même arbre et aussi fusionner deux arbres en un seul arbre.
4
?
bool Gentree::differ(int a, int b) { // les noeuds a et b sont-ils dans es arbres différents? GTNode* root1 = FIND(&array[a]); // trouve la racine de a GTNode* root2 = FIND(&array[b]); // trouve la racine de b return root1 != root2; // compare les raciness } class Gentree { // General tree: UNION/FIND private: GTNode* array; // Node array int size; // Size of node array GTNode* FIND(GTNode*) const; // trouver la racine public: Gentree(int); // Constructeur ~Gentree(); // Destructor void UNION(int, int); // fusionner bool differ(int, int); // TRUE si pas dans le même arbre }; Gentree::Gentree(int sz) { // Constructeur size = sz; array = new GTNode[sz]; // Créer le noeud tableau } Gentree::~Gentree() { // Destructeur delete [] array; // libérer le noeud tableau } bool Gentree::differ(int a, int b) { // les noeuds a et b sont-ils dans des arbres différents ? GTNode* root1 = FIND(&array[a]); // touver la racine de GTNode* root2 = FIND(&array[b]); // trouver la racine de b return root1 != root2; // Comparer les raciness }
5
void Gentree::UNION(int a, int b) { // fusionner les sousarbres GTNode* root1 = FIND(&array[a]); // trouver la racine de a GTNode* root2 = FIND(&array[b]); // trouver la racine de b if (root1 != root2) root2->par = root1; // fusionner } GTNode* Gentree::FIND(GTNode* curr) const { while (curr->parent() != NULL) curr = curr->par; return curr; // At root } 2.2. Implantation par liste des enfants : La liste des nœuds est stockée dans un tableau. Chaque élément de ce tableau contient, la valeur du nœud, un pointeur vers son parent et un autre pointeur vers la liste de ses enfants de gauche vers la droite. Remarque: la combinaison d’arbre avec cette implantation est plutôt difficile à réaliser si chaque arbre est stocké dans un nœud tableau. Si les nœuds des arbres sont stockées dans un seul nœud tableau, alors ajouter l’arbre T comme un sous arbre du nœud R est fait simplement en joutant la racine de T à la liste des enfants de R 2.3. Implantation par enfant gauche – frère droit L’inconvénient de l’implantation ci-dessus est qu’il est difficile d’accéder au nœud droit d’un frère. La figure ci-dessous montre une implantation améliorée. Chaque élément du tableau stocke la valeur du nœud et des pointeurs à son parent, l’enfant le plus à gauche et le frère droit . Donc, chaque opération de ci-dessus peut être implantée en lisant la valeur directement du nœud.
6
Si deux arbres sont stockés dans le même nœud tableau, alors ajouter un arbre comme un sous arbre de l’ordre exige la manipulation de pointeurs comme suit. 2.4. Implantation par des pointeurs (1) Les implantations qu’on vient de voir ci-dessous utilisent des tableaux pour stocker l’ensemble mble des nœuds de l’arbre. À l’inverse d’un arbre binaire, le nombre d’enfants que possède un noeud es variable. Si l’on désire procéder comme on a fait pour les arbres binaires, on est obligé de mettre une limite sur le nombre d’enfants que peut avoir un noeud donné et allouer des pointeurs pour exactement ce nombre d’enfants.
Union de deux arbres
Deux inconvénients majeurs à cette implantation :
1. cette limite peut être telle que certains arbre ne pourront pas être implantée 2. une perte énorme d’espace étant donné que beaucoup de nœuds n’auront pas autant
d’enfants; ce qui va mettre ces pointeurs à NULL. 2.5. Implantation par des pointeurs (2) Une autre alternative, plus flexible, est de stoker une liste chaînée des pointeurs des enfants d’un nœud, comme illustré par la figure ci-dessous. Cette implantation et essentiellement similaire à celle de la liste des enfants vue précédemment, à la différence que les nœuds sont allouées d’une manière dynamique plutôt que de les stocker dans un tableau. 2.6. Implantation par des pointeurs (3) L’implantation, par tableau, de ‘enfant gauche – frère droit de ci-dessus’ peut être facilement adaptée à une implantation dynamique. En gros, on substitue un arbre binaire à un arbre général. Chaque nœud de cet arbre va pointer vers l’enfant le plus gauche et le frère de droite. Comme on peut le constater, à l’aide de cette implantation, nous traitons un arbre général comme un arbre binaire. La conversion se fait comme ci-dessous. Plus que cela, nous pouvons même adapter cette implantation à un ensemble d’arbres, puisque chaque racine peut être interprétée comme étant le
8
frère droit de la racine d’un autre arbre. Cette implantation est de loin la plus utilisée pour les arbres généraux. 2.7. Conversion d’un arbre général en un arbre binaire Remarquez que l’implantation enfant gauche - frère droit essentiellement stocke un arbre binaire. Pour convertir d’une manière méthodique un arbre général en un arbre binaire, on procède comme suit. Pour chaque nœud de l’arbre 1. Laisser l’enfant gauche comme tel 2. Supprimer les autres enfants de ce nœud et les chaîner à l’enfant gauche Exemple : un ensemble d’arbres généraux convertis en un arbre binaire
template <class Elem> class GTNode { private: Elem element; GTNode<Elem>*parent; // Parent GTNode<Elem>* leftchild; // Premier fils - fils gauche GTNode<Elem>* rightsib; // Frère de droite public: GTNode(const Elem&); // Constructeur GTNode(const Elem&, GTNode<Elem>*, GTNode<Elem>*, GTNode<Elem>*); ~GTNode(); // Destructeur Elem value(); // Retourne la valeur du noeud bool isLeaf(); // VRAI si le nœud est une feuille GTNode* parent(); // Retourne le parent GTNode* leftmost_child(); // Retourne le premier enfant GTNode* right_sibling(); // Retourne le frère de droite void setValue(Elem&); // Assigne une valeur au noeud
9
void insert_first(GTNode<Elem>* n); // insère comme premier enfant void insert_next(GTNode<Elem>* n); // insère comme frère de droite void remove_first(); // Enlève le premier enfant void remove_next(); // Enlève le frère de droite }; template <class Elem> GTNode<Elem>::GTNode(const Elem& value) { parent = leftchild = rightsib = NULL; element = value; } template <class Elem> GTNode<Elem>::GTNode(const Elem& value, GTNode<Elem>* par, GTNode<Elem>* leftc, GTNode<Elem>* rights) { element = value; parent = par; leftchild = leftc; rightsib = rights; } template <class Elem> GTNode<Elem>::~GTNode() { } template <class Elem> Elem GTNode<Elem>::value() { return element; } template <class Elem> bool GTNode<Elem>::isLeaf() { return leftchild == NULL; } template <class Elem> GTNode<Elem>* GTNode<Elem>::parent() { return rent; } template <class Elem> GTNode<Elem>* GTNode<Elem>::leftmost_child() { return leftchild; } template <class Elem> GTNode<Elem>* GTNode<Elem>::right_sibling() { return rightsib; } template <class Elem> void GTNode<Elem>::setValue(Elem& value) { element = value; } template <class Elem> void GTNode<Elem>::insert_first(GTNode<Elem>* n) { n->rightsib = leftchild; n->parent = this; leftchild = n; }
10
template <class Elem> void GTNode<Elem>::insert_next(GTNode<Elem>* n) { n->rightsib = rightsib; n->parent = parent; rightsib = n; } template <class Elem> void GTNode<Elem>::remove_first() { if (leftchild == NULL) return; GTNode<Elem>* temp = leftchild; leftchild = leftchild->rightsib; delete temp; // pas bon – perd son sous arbre! } template <class Elem> void GTNode<Elem>::remove_next() { if (rightsib == NULL) return; GTNode<Elem>* temp = rightsib; rightsib = rightsib->rightsib; delete temp; // pas bon -- Perd son sous-arbre! } 2.8. Implantation séquentielle On considère dans cette section une approche complètement différente pour implanter des arbres. Le but est de stocker une série de valeurs des nœuds avec un minimum d’informations nécessaire à la reconstruction de l’arbre. Cette approche est connue sous le nom de implantation séquentielle des arbres. Elle a l’avantage de sauvegarder de l,espace car aucun pointeur n’est sauvegardé. Toutefois, son désavantage est de ne pouvoir accéder un nœud qu’après avoir traité tous les nœud qui apparaissent avant ce nœud dans la liste. Autrement dit, l’avantage que nous avons eu sur toutes les implantations discutées dans le chapitres précédent est perdue, à savoir un accès en O(log n). Cette implantation est idéale pour archiver des fichiers dans un disque pour un usage ultérieur car elle sauvegarde de l’espace, et l’arbre peut être reconstruit par la suite. La méthode consiste à énumérer les nœuds dans l’ordre qu’ils apparaissent lors d’un recherche en pré fixe.
11
Exemple: Pour les arbres binaires, on utilise un symbole / pour indiquer un lien nul:
AB/D//CEG///FH//I//
AB/D//CEG///FH//I// Pour reconstruire l’arbre, on commence par mettre le nœud A comme racine. L’enfant gauche de A est B. L’enfant gauche de B est NULL. Donc le nœud D doit être l’enfant droit de B. Le nœud D a deux enfant NULL,. Donc le nœud C l’enfant droit de A, … etc. Pour montrer la difficulté d’utiliser cette implantation, considérons la recherche de l’enfant droit de la racine. Nous devons traiter avant tous les noeuds du sous-arbre gauche de cette racine. Cette implantation doit reconnaître quand un nœud est une feuille ou interne. Une manière de procéder est de lister explicitement un nœud : feuille ou interne.
A’B’/DC’E’G/F’HI
Cette approche nécessite un bit additionnel pour indiquer si le nœud est une feuille ou interne. Cependant, stoker n bits est beaucoup que de stocker n valeurs NULLS Implémenter les arbres généraux à l’aide de l’implémentation séquentielle nécessite plus d’informations à inclure dans un nœud : feuille ou interne et nombre d’enfants. Dans l’exemple suivant, le symbole parenthèse ) indique la fin de la liste d’enfant d’un noeud. Toutes les feuilles
12
sont suivies d’un ). Une feuille qui est aussi le dernier enfant pour ses parents va indiquer ceci par deux ou plus symboles ) RAC)D)E))BF)))
13
3. Les B-Arbres Parmi les les arbres génaux, on en distingue une classe particulière qui est celle des B-arbres.
3.1. Introduction
Les algorithmes de recherche, sur les très grandes collections de données, sont très différents de tout les algorithmes précédents. Tous les algorithmes précédents étaient dédiés à une utilisation en mémoire primaire.
La recherche dans de gros fichier sur disque ne peut donc pas utiliser les algorithmes précédents, pourtant très rapides. Étrangement, les algorithmes utilisés pour ce genre de tâches, peuvent retrouver un élément de données sur un disque d'une capacité allant jusqu'a 3 milliards de mots en seulement 2 ou 3 accès disques.
La mémoire secondaire est considérée comme beaucoup plus lente que la mémoire principale et comme étant paginée; c'est a dire découpée en pages pouvant contenir chacune un certain nombre d'éléments. La page est l’unité de transfert entre la mémoire centrale et le disque. Un seul accès au disque prend environ autant de temps que 200 000 instructions. La structure de données que nous introduisons ci-dessus est utilisée dans le but de réduire le nombre d’accès au disque.
Un B-arbre d'ordre m est un arbre de recherche formé de noeuds qui peuvent chacun contenir jusqu'a 2m éléments. Chaque noeud est dans une page différente du disque, et la complexité des algorithmes de recherche, adjonction et suppression d'un élément parmi n, est comptée en nombre d'accès à la mémoire secondaire est, comme on le verra plus loin, en O(logm n).
Définition: Un B-arbre d'ordre m est un arbre ayant les propriétés suivantes
• Chaque nœud a un maximum de 2m et un minimum de m éléments, excepté la racine qui peut contenir un minimum de un élément.
• Un noeud est soit une feuille (sans enfant) ou un noeud interne avec k éléments et k+1 enfants ( mkm 2≤≤ )
• If kXXX ,...,, 21 sont ces noeuds et kPPP ,...,, 10 les enfants, alors :
- 0P contient les éléments ≤ 1X
- 1P contient les éléments > 1X et ≤ 2X
- …………………
……..
14
• Toutes les feuilles sont au même niveau.
Le sous arbre le plus à gauche contient toutes les valeurs inférieures à v1, le 2ème sous-arbre contient celles comprises entre v1 et v2, et ainsi de suite.
3.2 Opérations de base sur un B-arbre
3.2.1) Recherche d’un élément
La recherche dans un B-arbre est une généralisation de la recherche dans un arbre binaire de recherche Noter que l’on doit lire le nœud cherché en mémoire secondaire, puis faire une recherche (qui peut être dichotomique, pourquoi?) dans le nœud lui-même pour accéder à l’enregistrement recherché.
15
Pseudo-code :
1. ki < x < ki+1 pour 0< i <m : x est compris entre les clés ki et ki+1, auquel cas on continue la recherche sur l’enfant pi
2. km < x : x est plus grande que toutes les clés du nœud, auquel cas on continue la recherche sur l,enfant pm
3. x < k1 : x est plus petite que toutes les clés du noeud, auquel cas on continue la recherche sur l’enfant indiquée par p0.
3.2.2 Insertion et suppression :
Les ajouts et suppressions d'éléments entraînent des opérations d'éclatement et de regroupement des sommets. Avant toute chose, il est nécessaire de retrouver (à l’aide de la fonction de recherche) la place où il faut insérer l’élément où l’élément en question.
a. Insertion
L’insertion dans un B-arbre est plus complexe que l’insertion dans un ABR. Elle utilise l’opération auxiliaire de découpage d’un nœud complet, que nous allons d’abord décrire. On rappelle qu’un nœud complet contient 2t clés. Après insertion, ce nombre devient impair. Le nœud possède donc une clé médiane. Le découpage consiste à éclater le nœud complet en deux nœuds, autour de cette clé médiane. La clé médiane (avec son enregistrement) remonte dans le nœud père, qui ne doit pas être complet avant le découpage. Chacun des deux nouveaux nœuds contient donc exactement t clés, le minimum requis. Si le nœud complet découpé était la racine (et n’a donc pas de père) une nouvelle racine va être créée pour recueillir la clé médiane, et la hauteur va augmenter de 1. C’est ainsi que croît le B-arbre: par la racine. La figure 11.2 illustre l’opération de découpage d’un nœud complet différent de la racine. La figure 11.3 illustre le cas du découpage de la racine. La figure 11.4 montre une succession d’insertions dans le même B- arbre. On montre que l’insertion dans un B-arbre nécessite O(h) = O(log n) accès à des nœuds. Remarque: certains auteurs définissent les bornes de chaque nœud, pour un arbre de degré t, comme étant t-1 et 2t-1 (comme c’est le cas ci-dessous)
16
17
Algorithme d’insertion 1. chercher le nœud où le nouvel élément doit être inséré 2. insérer l'élément dans son noeud 3. si débordement
partager le bloc en deux blocs à moitié pleins si (le noeud n'est pas la racine)
insérer de la même manière la valeur médiane dans le noeud de niveau supérieur où elle servira de critère de séparation (cette insertion peut elle-même créer une séparation dans les noeuds supérieurs)
sinon créer un nouveau noeud racine pour y mettre cette valeur médiane.
18
b. Suppression d’un élément C’est une opération relativement complexe, que nous ne détaillerons pas ici. On peut deviner cependant que la plupart du temps elle nécessite uniquement la lecture des nœuds d’un chemin jusqu’à une feuille, parce que la plupart des clés se trouvent dans les feuilles. Si tel n’est pas le cas, on recherche l’élément le plus grand à la gauche de cet élément (où l’élément le plus petit à la droite de cet élément) qui ne peut se trouver que dans une feuille. On remplace l’élément à supprimer par cet élément qui lui doit être supprimé de ce nœud terminal Dans ce qui suit, nous allons donc supposer, sans perdre de généralité, que le nœud à supprimer est dans une feuille. La suppression dans un B-arbre s’effectue également en O(h) = O(log n) accès à des nœuds. Pour retrouver la clé proprement, une recherche s’impose dans le nœud lui-même.
19
Algorithme de suppression 1. chercher le noeud s où se trouve l'élément à supprimer 2. enlever l'élément du noeud 3. si le noeud contient moins que m (l’ordre de cet arbre) éléments
si (nb. élt d'un noeud adjacent t + nb élt de s < m) - fusionner s, t et l'élément du noeud supérieur e qui les séparait en un noeud u - enlever e du noeud supérieur - remplacer les deux références à s et t par une seule référence à u - si (le noeud supérieur contient moins que m éléments)
appliquer récursivement le même traitement, sauf si c'est la racine
20
sinon - effectuer une répartition égale des éléments entre s et un noeud adjacent t, - mettre à jour l'élément séparateur dans le noeud supérieur.
3.3. Complexité Comme nous venons de le voir, le coût des opérations d’insertion, suppression et recherche est proportionnel à la hauteur de l’arbre. Dans ce qui suit, nous montrons que la hauteur d’un B-arbre est en )(log nO m . En effet, nous savons que le nombre de clés, n, dans l’arbre vérifie la relation
suivante:
≥n minimum #nœuds du B-arbre de hauteur h et de degré minimum m
Le minimum #noeuds signifie que la racine à une seule clé (deux enfants) et les autres nœuds en ont m (minimum) clés chacun (comme illustré sur la figure ci-dessous).
21
Dans ce cas, donc, nous avons une seul nœud d’une clé au niveau 1, 2 nœuds de m clés au 2ème niveau, )1(2 +m nœuds de m valeurs chacun au niveau 3 (c’est-à-dire )1(2 +mm valeurs), ….,
∑ =
1 clé
22
en mettant le 1 du coté de n, en divisant par 2 et le log des deux cotés de cette inégalité, on obtient :
)1log()1( 2
1 log +−≥
)(log nOh m=
Il est facile de déduire la complexité des opérations de recherche, d’insertion et de suppression. Dans tous les cas, ces complexités sont proportionnelles à la hauteur de l’arbre. Une fois, le nœud trouvé, il y a lieu de parcourir la liste des valeur existant dans ce nœud. Comme les valeur dans chaque nœud sont triées, on pourra appliquer l’algorithme de dichotomie pour retrouver cette valeur en )(logmO (ou en O(m) si on applique la recherche séquentielle). Comme le coût de l’opération de recherche est dominé par la recherche du nœud (page) représentant les accès au disques, on dira que les complexité de ces algorithme sont en )(log nO m .
Pour l’opération d’insertion, dans le pire cas, après avoir trouvé l’endroit où il faut insérer l’élément, on remontera l’arbre, d’éclatement en éclatement de nœud jusqu’à créer éventuellement une nouvelle racine. Ce parcours n’excédera pas la hauteur de l’arbre + 1. Autrement dit, la complexité de l’insertion est en )(log nO m .
Pour la suppression, dans le pire cas, après avoir trouvé l’emplacement de l’élément à supprimer, on remontera l’arbre, de regroupement en regroupement de nœuds jusqu’à éventuellement la racine. Dans tous les cas, ce parcours n’excédera pas la hauteur de l’arbre. Autrement dit, la complexité de la suppression est en )(log nO m .
3.4. Variantes du B-arbre
1. B+-arbre: Dan un a B+ arbres, les données sont enregistrées dans les feuilles. Les nœuds internes contiennent juste des clés qui sont utilisées pour diriger la recherche vers la feuille considérée. Par ailleurs, les données sont chacune contenues dans une feuille et sont chaînées entre-elles de telle manière que ces dernières peuvent être toutes traversées. La suppression se trouve ainsi facilitée car elle se fait sur les feuilles.
2. B*-arbre: Similaire aux B-arbres, seulement les noeuds sont occupés au moins au 2/3.
3. Compact B-arbre: Similaire aux B-arbres, seulement les nœuds sont occupés à au
moins 90%.
4. Arbres 2-3 : Ce sont des B-arbres particuliers de degrés 1. Autrement dit, chaque nœud contient 1 à 2 clés et 2 ou 3 enfants.
23
5. Arbre 2-3-4 : Pour éviter le cas de la dégénérescence de l'arbre, nous allons augmenter
les directions de recherche en autorisant les noeuds à devenir des 4 noeuds; c'est à dire un noeud possédant au maximum 4 noeuds enfants et donc 3 clés.