3I009 1 Indexation : arbres B+ et tables de hachage (3 pts)
10 juin 2016 Dans cet exercice on considère des arbres B+ d'ordre 2 (les noeuds ... - A → B : b1=B
Un exemple de structure de données hiérarchique : larbre B+
l'arbre B+. Maude Manouvrier. Page 2. Arbre B. Arbre B (R. Bayer et C. McCreight 1972)
Corrigé des exercices
– SiA=(Fgx
Conception dalgorithmes Principes et 150 exercices non corrigés
arbre (b) est un second arbre préfixe. Le coût L(A) de l'arbre préfixe A se définit par la longueur de la chaîne de bits résultant du codage du texte t par ...
Les possessifs exercices et corrigé
7. Complétez les phrases suivantes avec les pronoms possessifs qui conviennent. 1. Cet arbre est à vos voisins ? Oui c'est .
Les démonstratifs exercices et corrigé
Exercices et corrigé. Les adjectifs. 1. Complétez avec ce cette ou ces. 1 Cet arbre est exotique. 2. Ces hélices (f) tournent vite. Cette hélice ...
Langage C : énoncé et corrigé des exercices IUP GéniE
par tree . Exercice 48 Ecrire une f onction A r b re con s truire ( c ha r * s E x pre ss ion int iI ndice D e b ut
Module 7 - Arbres de décisions Exercices - Corrigé
Exercices - Corrigé. Exercice 2. L'entropie peut être calculée selon plot ( arbre uniform=TRUE
Parcours dun arbre binaire
ordre infixe : ch
Les arbres-B
L'arbre-B (o`u B-Tree en anglais) est une SDD utilisée dans les do- maines des : syst`emes de gestion de fichiers : ReiserFS (version modifiée.
Aucun titre de diapositive
Arbre B. Arbre B (R. Bayer et C. McCreight 1972)
EXERCICES corrigés de PROBABILITES
Exercice n°1: Détermine les probabilités p(A) puis p(B) et p(C). 2. Représente l'expérience par un arbre pondéré ( on fait figurer sur chaque branche la.
Exercices corrigés Initiation aux bases de données
Correction de l'exercice 2. A ne peut pas être clé de R car la valeur a1 de A se répètent dans la relation R. De même pour. B (b1) et C (c2).
Terminale S - Probabilités Exercices corrigés
F. Laroche. Probabilités exercices corrigés. Correction. 1.a. Arbre pondéré : Evénement A : chemin. Evénement B : chemin. Evénement C : chemin. B. B. B.
10 EXERCICES DE 60 PHRASES CHACUN –avec corrigé. 600
Exercices préparatoires au TECFÉE. CORRIGÉ. Partie 1. PARTIE A. 1. L'orthographe grammaticale et la morphologie. 1. b) Une immense banderole bleu lavande
Langage C : énoncé et corrigé des exercices IUP GéniE
par tree . Exercice 48 Ecrire une f onction A r b re con s truire ( c ha r * s E x pre ss ion int
Les possessifs exercices et corrigé
7. Complétez les phrases suivantes avec les pronoms possessifs qui conviennent. 1. Cet arbre est à vos voisins ? Oui c'est .
PROBABILITES – EXERCICES CORRIGES
Exercice n°1. B l'événement : "La carte choisie est rouge (cœur ou carreau)". ... L'arbre ci-contre indique la répartition selon le niveau et la.
Systèmes de Gestion de Bases de Données – 3I009 1 Indexation
Dans cet exercice on considère des arbres B+ d'ordre 2 (les noeuds et les CORRIGÉ. UPMC. Réponse : Solution: Insertion de 28 et 31 dans F3 : F3 (27
Les B-arbres
Un B-arbre est un arbre de la recherche avec une rami?cation importante et une hauteur plutôt faible En pratique un noeud de notre arbre est une page de notre disque externe
Les B-arbres
Arbre B+ d’ordre m Tout nœud d’index a au maximum m nœuds fils - un nœud possède au minimum [m/2] fils - la racine possède au minimum 2 fils - tout nœud d’index contient k fils et (k-1) clés L’arbre est équilibré (balanced tree) -t ous les nœuds feuilles sont au même niveau - la hiérarchie de l'arbre grossit par la racine :
Searches related to b arbre exercices corrigés PDF
1 a Constmire un arbre de dénombrement de toutes les combinaisons possibles de 3 boules b Combien de combinaisons y a-t-il ? 2 A l'aide de l'arbre de dénombrement calculer la probabilité des événements suivants A : On a 2 boules rouges C : On n'a pas de boule bleue EXERCICE 4A 4 B : On a une boule de chaque couleur
Comment calculer la complexité d’un arbre ?
Hypothèses pour le calcul de la complexité:—La racine du B-arbre se trouve toujours en mémoire principal : on n’a pas de LIRE-DISQUE; ce-pendant, il faudra effectuer un ÉCRITURE-DISQUElors de la modi?cation de la racine.—Tout noeud passé en paramètre devra subir un LIRE-DISQUE. Théorème. Soit T un B-arbre à n élément de degré minimal t2.
Quelle est la hauteur d’un arbre ?
Algorithmes et structures de donn´ees : TD 1 Corrig´e D´essiner cet arbre. Quelle est la hauteur de l’arbre ? La hauteur de l’arbre est 3. 3. Est-ce que cet arbre est un arbre entier, un arbre parfait (=complet), et/ou un arbred´eg´en´er´e ? Cet arbre est entier car chaque noued a zero ou deux ?ls.
Comment savoir si un arbre est équilibré?
Arbre B+ d’ordre m Tout nœud d’index a au maximum mnœuds fils - un nœud possède au minimum[m/2] fils - la racine possède au minimum 2 fils - tout nœud d’index contient k fils et (k-1) clés L’arbre est équilibré (balanced tree)
Comment créer un arbre binaire de recherche ?
Etablir la structure de donn´eesptnoeud ?pour cet arbre binaire de recherche contenantune cl´e (integer) et deux pointeurs, un pour le sous-arbre gauche, et un pour le sous-arbredroite. 2. Ecrire une fonctionfunction max(noeud : mum de l’abre de recherche. 3. Ecrire une fonctionfunction min(noeud : mum de l’abre de recherche.
Les arbres-B
G´eraldine Del Mondo, Nicolas Delestre
Fond´e sur le cours de M. Michel Mainguenaud - Dpt ASI arbre-B - v1.61 / 31Plan...
1D´eifinition
2Recherche dans un Arbre-B
3Insertion dans un Arbre-B
4Suppression dans un Arbre-B
arbre-B - v1.62 / 31D´eifinition
Contexte
L'arbre-B (o`uB-Treeen anglais) est une SDD utilis´ee dans les do- maines des :syst`emes de gestion de ifichiers : ReiserFS (version modiifi´ee des arbres-B) ou Btrfs (B-Tree ifile system)bases de donn´ees : gestion des index L'arbre-B reprend le concept d'ABR ´equilibr´e mais en stockant dans un noeudkvaleurs (nomm´ees cl´es dans le contexte des arbres-B) et en r´ef´eren¸cantk+ 1 sous arbres :≪ minimise la taille de l'arbre et r´eduit le nombre d'op´erations d'´equilibrage ≫(Wikip´edia)utile pour un stockage sur une unit´e de masse arbre-B - v1.63 / 31D´eifinition
Arbre-B
D´eifinitionArbre-B
longueur `a 1 pr`es3Un noeud est : •Soit terminal (feuille) •Soit poss`ede (k+ 1) ifils tels que les cl´es du i`eme ifils ont des valeurs comprises entre les valeurs du (i-1)`eme eti`eme cl´es du p`ere arbre-B - v1.64 / 31D´eifinition
Structure d'un noeud
D´eifinitionNoeud
•kcl´es tri´ees •k+ 1 pointeurs tels que : T oussont difff ´erentsde NIL si le noeud n'est pas une feuilleT ous` aNIL si le noeud est un efeuille P
0k 1P 1k 2P 2..P k-1k kP kk2 k-1kkarbre-B - v1.65 / 31 D´eifinition
Capacit´e
Nombre de cl´es
Arbre-B d'ordremet de hauteurh:
,→Nombre de cl´e(s) minimal = 2∗(m+ 1)h-1 ,→Nombre de cl´es maximal = (2∗m+ 1)h+1-1 Exemple :m= 100,h= 2 : Nombre maximal de cl´es≈8 000 000Stockage sur disque ,→Un noeud = Un bloc (ensemble de secteurs)arbre-B - v1.66 / 31 D´eifinition
Exemple
Exemple :Arbre-B d'ordre 251
11 30 2 712 15 2235 4166 78
53 54 6368 69 71 7679 84 93
D´eifinition
Conception
Conception d´etaill´ee
TypeArbreB=ˆNoeud
TypeNoeud= Structure
nbCles :NaturelNonNul cles :Tableau[1..MAX] deValeur sousArbres :Tableau[0..MAX] deArbreB ifinstructure ... tel que le typeValeurposs`ede un ordre totalInformation Contrairement au premier cours sur les SDD, nous utiliserons ici aucune fonction/proc´edure d'encapsulation arbre-B - v1.68 / 31 Recherche d'un ´el´ement de cl´ec1 / 3P
0k 1P 1k 2P 2..P k-1k kP kk1 2 k-1kkPrincipe `A partir de la racine, pour chaque noeud examin´e :La cl´eCest pr´esente (recherche qui peut ˆetre dichotomique)
→succ`esCkk→recherche dans le sous-arbre le plus `a droite (via le pointeurPk)k irecherche dans le sous-arbre (via le pointeurPi)Si l'arbre est vide (pointeur vaut NIL)→´echec Recherche d'un ´el´ement de cl´ec2 / 3fonctionestPresent(a : ArbreB, c : Valeur) : Booleen debut sia=NIL alors retournerFAUX sinon sicaˆ.cles[aˆ.nbCles]alors sinon siresalors retournerVRAI sinon retournerestPresent(ssArbre,c) ifinsi ifinsi ifinsi ifinsi ifin Recherche d'un ´el´ement de cl´ec3 / 3fonctionestPresentDansNoeud(n : Noeud, c : Valeur) : Booleen, ArbreB
D´eclarationg,d,m :NaturelNonNul
debut g←1 d←n.nbCles tant queg̸=dfaire m←(g+d) div 2 sin.cles[m]≥calors d←m sinon g←m+1 ifinsi ifintantque sin.cles[g]=calors retournerVRAI,NIL sinon retournerFAUX, sousArbres[g-1] ifinsi ifinRemarque getdr´ef´erencent la position de l'´el´ement sup´erieur ou ´egal `a la valeur recherch´ee
Insertion dans un arbre-B d'ordremPrincipe
1L'insertion se fait r´ecursivement au niveau des feuilles
2Si un noeud a alors plus 2m+ 1 cl´es, il y a ´eclatement du
noeud et remont´ee (grˆace `a la r´ecursivit´e) de la cl´e m´ediane au niveau du p`ere3Il y a augmentation de la hauteur de l'arbre lorsque la racine se retrouve avec 2m+ 1 cl´es ,→l'augmentation de la hauteur de l'arbre se fait donc au niveau de la racine! Exemple : cas d'un noeud plein 1 / 2
Exemple :Insertion de75?51
11 30 2 712 15 2235 4166 78
53 54 6368 69 71 7679 84 93
1Eclatement du noeud en deux :
Les (deux) plus
p etites cl ´esrestent dans le noeud Les (deux) plus
gran des cl ´essont ins ´er´eesdans un nouveau noeud2Remont´ee de la cl´e m´ediane dans le noeud p`ere (e.g. ici71) Exemple : cas d'un noeud plein 2 / 2
Exemple :Insertion de75?51
11 30 2 712 15 2235 4166717853 54 6368 69757679 84 93
1Eclatement du noeud en deux :
Les (deux) plus
p etites cl ´esrestent dans le noeud Les (deux) plus
gran des cl ´essont ins ´er´eesdans un nouveau noeud2Remont´ee de la cl´e m´ediane dans le noeud p`ere (e.g. ici71) Insertion Arbre-B
Exemple : cas de l'augmentation de la hauteur 1 / 2 Arbre-B d'ordre 2 :5 11 16 21
1 2 3 46 7 8 1012 13 14 1517 18 19 2022 23 24 25
Insertion cl´e9→Eclatement + remont´ee de la cl´e8au noeud p`ereRemont´ee de la cl´e8au noeud p`ere→Eclatement + cr´eation nouvelle
racine (e.g. ici11)arbre-B - v1.615 / 31 Insertion Arbre-B
Exemple : cas de l'augmentation de la hauteur 2 / 2 Arbre-B d'ordre 2 :11
581 2 3 46 791016 21
12 13 14 1517 18 19 2022 23 24 25
Insertion cl´e9→Eclatement + remont´ee de la cl´e8au noeud p`ereRemont´ee de la cl´e8au noeud p`ere→Eclatement + cr´eation nouvelle
racine (e.g. ici11) ,→Augmentation d'une unit´e de la hauteurarbre-B - v1.616 / 31 Insertion Arbre-B
Algorithme 1 / 2
Pr´erequis
On suppose poss´eder les fonctions/proc´edures suivantes :fonctioncreerFeuille(c :Tableau[1..MAX] deValeur, nb :NaturelNonNul) :
ArbreBfonctionestUneFeuille(a : ArbreB) : Booleenproc´edureeclater(E/Sa : ArbreB,Eordre :NaturelNonNul)
⌊pr´econdition(s)aˆ.nbCles=2*ordre+1fonctionpositionDInsertion(a : ArbreB, c : Valeur) : NaturelNonNulproc´edureinsererUneCleDansNoeud(E/Sn : Noeud,Ec : Valeur, pos :
NaturelNonNul)proc´edureinsererRacineDeTailleUnDansNoeud(E/Sn : Noeud,Eracine : ArbreB, pos :NaturelNonNul)
⌊pr´econdition(s)racineˆ.nbCles=1arbre-B - v1.617 / 31 Insertion Arbre-B
Algorithme 2 / 2
proc´edureinserer(E/Sa : ArbreB,Ec : Valeur, ordre :NaturelNonNul) ⌊pr´econdition(s)2*ordreD´eclarationtab :Tableau[1..MAX] deValeur debut sia =NIL alors tab[1]←c a←creerFeuille(tab,1) sinon pos←positionDInsertion(a,c) siestUneFeuille(a)alors insererUneCleDansNoeud(aˆ,c,pos) siaˆ.nbCles>2*ordrealors eclater(a, ordre) ifinsi sinon ssArbre←aˆ.sousArbres[pos-1] inserer(ssArbre,c,ordre) sissArbre̸= aˆ.sousArbres[pos-1]alors siaˆ.nbCles>2*ordrealors eclater(a, ordre) ifinsi ifinsi ifinsi ifinsi ifinarbre-B - v1.618 / 31 Suppression Arbre-B
Supression dans un arbre-B d'ordremPrincipe
1La suppression se fait toujours au niveau des feuilles
,→Si la cl´e `a supprimer n'est pas dans une feuille, alors la remplacer par la plus grande valeur des plus petites (ou plus petite valeur des plus grandes) et supprimer cette derni`ere2Si la suppression de la cl´e d'une feuille (r´ecursivement d'un
noeud) am`ene `a avoir moins demcl´es :1Combinaison avec un noeud voisin (avant ou apr`es) 2Descente de la cl´e associant ces deux noeuds (´eclatement du
noeud si n´ecessaire et donc remont´e d'une nouvelle cl´e) ,→la r´ecursivit´e de ce principe peut ammener `a diminuer la hauteur de l'arbre (par le haut) arbre-B - v1.619 / 31 Suppression Arbre-B
Ex. cas 1 : tr`es simple
Arbre-B d'ordre 2 :10 15 27
12 14202526Rappel: ici nombre de cl´es par noeud non racine>1
,→Exemple :Suppression de la cl´e25?M´ethode 1Suppression de la valeur (d´ecalage des valeurs dans le tableau)
arbre-B - v1.620 / 31 Suppression Arbre-B
Ex. cas 2 : simple 1 / 2
Arbre-B d'ordre 2 :1015 27
12 142025Rappel: ici nombre de cl´es par noeud non racine≥2
,→Exemple :Suppression de la cl´e25?M´ethode 1Combinaison avec un noeud voisin
2Descente de la cl´e (ici15 )
3Suppression du noeud
arbre-B - v1.621 / 31 Suppression Arbre-B
Ex. cas 2 : simple 2 / 2
Arbre-B d'ordre 2 :10 27
12 14 15 20 Rappel: ici nombre de cl´es par noeud non racine≥2 ,→Exemple :Suppression de la cl´e25?M´ethode 1Combinaison avec un noeud voisin ([12 14] et 20)
2Descente de la cl´e m´ediane (ici15 )
3Suppression du noeud
arbre-B - v1.622 / 31 Suppression Arbre-B
Ex. cas 3 : avec ´eclatement 1 / 2
Arbre-B d'ordre 2 :4 8
,→Exemple :Suppression de la cl´e6?Suppression cl´e6→Combinaison [1 2 3] et 7 + descente de la cl´e4 au
noeud ifilsDescente de la cl´e4 au noeud ifils →Redistribution + remont´ee de cl´e m´ediane (e.g. ici3)arbre-B - v1.623 / 31 Suppression Arbre-B
Ex. cas 3 : avec ´eclatement 2 / 2
Arbre-B d'ordre 2 :3 8
1 247 ,→Exemple :Suppression de la cl´e6?Suppression cl´e6→Combinaison [1 2 3] et 7 + descente de la cl´e4 au
noeud ifilsDescente de la cl´e4 au noeud ifils →Redistribution + remont´ee de cl´e m´ediane (e.g. ici3)arbre-B - v1.624 / 31 Suppression Arbre-B
Ex. cas 4 : avec un nombre de cl´es inf´erieurs `am1 / 2 Arbre-B d'ordre 2 :11
3 8 1 2479 1016 2111
8 1 2 3 7 9 1016 21
,→Exemple :Suppression de la cl´e4?Combinaison ([1 2] et 7) + descente de la cl´e3 arbre-B - v1.625 / 31 Suppression Arbre-B
Ex. cas 4 : avec un nombre de cl´es inf´erieurs `am2 / 2 Arbre-B d'ordre 2 :811 16 21
1 2 3 79 10
,→Exemple :Suppression de la cl´e4?Combinaison + descente de la cl´e3 Combinaison (8 et [16 21]) + descente de la cl´e 11 ,→Diminution d'une unit´e de la hauteurarbre-B - v1.626 / 31 Suppression Arbre-B
Ex. cas 5 : suppression non feuille
Arbre-B d'ordre 2 :581 2 34 6 79 1048
1 2 36 79 10
,→Exemple :Suppression de la cl´e5?M´ethode 1Recherche d'une cl´e adjacenteA ` ala cl ´e` asupp rimer→on
choisit la plus grande du sous a rbregauche 2Remplacement de la cl´e `a supprimer parA 3Suppression de la cl´eA du sous a rbregauche
arbre-B - v1.627 / 31 Suppression Arbre-B
Algorithme 1 / 4
Pr´erequis
On suppose poss´eder les fonctions/proc´edures suivantes :fonctionplusGrandeValeur(a : ArbreB) :Valeur
⌊pr´econdition(s)a̸=NILfonctionpositionCleDansNoeudRacine(a : ArbreB, c : Valeur) : Entier
⌊pr´econdition(s)a̸=NIL -1 si non pr´esentfonctionpositionSsArbrePouvantContenirValeur(a : Arbre, c : Valeur) : Naturelfonctionfreres(a : ArbreB, posSsArbre :Naturel) :ArbreB, ArbreB
⌊pr´econdition(s)a̸=NILet aˆ.sousArbres[posSsArbre]̸=NILproc´eduresupprimerCleDansNoeudFeuille(E/Sn : Noeud,Ec : Valeur)proc´edurecopierValeurs(StDest :Tableau[1..MAX] deValeur,EtSource :Tableau[1..MAX] deValeur,
indiceDebutDest, indiceDebutSource, nb :NaturelNonNul) ⌊pr´econdition(s)indiceDebutSource+nb NaturelNonNul)arbre-B - v1.628 / 31
Suppression Arbre-B
Algorithme 2 / 4
Cas simples
proc´eduresupprimer(E/Sa : ArbreB,Ec : Valeur, ordre :NaturelNonNul, frereG, frereD : ArbreB, clePere :
Valeur)
D´eclaration...
debut sia̸=NIL alors pos←positionCleDansNoeudRacine(a,c) siestUneFeuille(a)alors sipos̸= -1alors sifrereG =NILet frereD =NILet aˆ.nbCles=1alors desallouer(a)// n'est possible que pour la racine sinon Algo #1 : supprimer c dans une feuille
ifinsi ifinsi sinon sipos = -1alors sinon // cas # 5 des exemples aˆ.valeurs[pos]←cleRemplacement c←cleRemplacement posSsArbre←pos-1 ifinsi Algo #2 : supprimercdans un sous-arbre de rang posSsArbre ifinsi ifinsi ifinarbre-B - v1.629 / 31 Suppression Arbre-B
Algorithme 3 / 4
Algo #1 : supprimercdans une feuillesupprimerCleDansNoeudFeuille(aˆ,c) siaˆ.nbCles2*ordrealors eclater(res, ordre) ifinsi ifinsiarbre-B - v1.630 / 31 Suppression Arbre-B
Algorithme 4 / 4
Algo #2 : supprimercdans le sous-arbrefrereG,frereD←freres(a,posSsArbre) temp←aˆ.sousArbres[posSsArbre] supprimer(temp,c,ordre,frereG,frereD, tempˆ.valeurs[posSsArbre]) sitemp̸= aˆ.sousArbres[posSsArbre]alors //cas ou il y a eu combinaison avec un frere sitempˆ.nbCles=1alors // cas #3 des exemples : il y a eu ´eclatement apr`es combinaison sinon // cas #2 des exemples aˆ.sousArbres[posSsArbre]←temp ifinsi ifinsiExercice Comment prendre en compte le cas #4 des exemples?
arbre-B - v1.631 / 31quotesdbs_dbs15.pdfusesText_21
D´eifinition
Capacit´e
Nombre de cl´es
Arbre-B d'ordremet de hauteurh:
,→Nombre de cl´e(s) minimal = 2∗(m+ 1)h-1 ,→Nombre de cl´es maximal = (2∗m+ 1)h+1-1 Exemple :m= 100,h= 2 : Nombre maximal de cl´es≈8 000 000Stockage sur disque ,→Un noeud = Un bloc (ensemble de secteurs)arbre-B - v1.66 / 31D´eifinition
Exemple
Exemple :Arbre-B d'ordre 251
11 302 712 15 2235 4166 78
53 54 6368 69 71 7679 84 93
D´eifinition
Conception
Conception d´etaill´ee
TypeArbreB=ˆNoeud
TypeNoeud= Structure
nbCles :NaturelNonNul cles :Tableau[1..MAX] deValeur sousArbres :Tableau[0..MAX] deArbreB ifinstructure ... tel que le typeValeurposs`ede un ordre totalInformation Contrairement au premier cours sur les SDD, nous utiliserons ici aucune fonction/proc´edure d'encapsulation arbre-B - v1.68 / 31Recherche d'un ´el´ement de cl´ec1 / 3P
0k 1P 1k 2P 2..P k-1k kP kk2 k-1kkPrincipe `A partir de la racine, pour chaque noeud examin´e :La cl´eCest pr´esente (recherche qui peut ˆetre dichotomique)
→succ`esCkk→recherche dans le sous-arbre le plus `a droite (via le pointeurPk)k irecherche dans le sous-arbre (via le pointeurPi)Si l'arbre est vide (pointeur vaut NIL)→´echec Recherche d'un ´el´ement de cl´ec2 / 3fonctionestPresent(a : ArbreB, c : Valeur) : Booleen debut sia=NIL alors retournerFAUX sinon sicaˆ.cles[aˆ.nbCles]alors sinon siresalors retournerVRAI sinon retournerestPresent(ssArbre,c) ifinsi ifinsi ifinsi ifinsi ifin Recherche d'un ´el´ement de cl´ec3 / 3fonctionestPresentDansNoeud(n : Noeud, c : Valeur) : Booleen, ArbreB
D´eclarationg,d,m :NaturelNonNul
debut g←1 d←n.nbCles tant queg̸=dfaire m←(g+d) div 2 sin.cles[m]≥calors d←m sinon g←m+1 ifinsi ifintantque sin.cles[g]=calors retournerVRAI,NIL sinon retournerFAUX, sousArbres[g-1] ifinsi ifinRemarque getdr´ef´erencent la position de l'´el´ement sup´erieur ou ´egal `a la valeur recherch´ee
Insertion dans un arbre-B d'ordremPrincipe
1L'insertion se fait r´ecursivement au niveau des feuilles
2Si un noeud a alors plus 2m+ 1 cl´es, il y a ´eclatement du
noeud et remont´ee (grˆace `a la r´ecursivit´e) de la cl´e m´ediane au niveau du p`ere3Il y a augmentation de la hauteur de l'arbre lorsque la racine se retrouve avec 2m+ 1 cl´es ,→l'augmentation de la hauteur de l'arbre se fait donc au niveau de la racine! Exemple : cas d'un noeud plein 1 / 2
Exemple :Insertion de75?51
11 30 2 712 15 2235 4166 78
53 54 6368 69 71 7679 84 93
1Eclatement du noeud en deux :
Les (deux) plus
p etites cl ´esrestent dans le noeud Les (deux) plus
gran des cl ´essont ins ´er´eesdans un nouveau noeud2Remont´ee de la cl´e m´ediane dans le noeud p`ere (e.g. ici71) Exemple : cas d'un noeud plein 2 / 2
Exemple :Insertion de75?51
11 30 2 712 15 2235 4166717853 54 6368 69757679 84 93
1Eclatement du noeud en deux :
Les (deux) plus
p etites cl ´esrestent dans le noeud Les (deux) plus
gran des cl ´essont ins ´er´eesdans un nouveau noeud2Remont´ee de la cl´e m´ediane dans le noeud p`ere (e.g. ici71) Insertion Arbre-B
Exemple : cas de l'augmentation de la hauteur 1 / 2 Arbre-B d'ordre 2 :5 11 16 21
1 2 3 46 7 8 1012 13 14 1517 18 19 2022 23 24 25
Insertion cl´e9→Eclatement + remont´ee de la cl´e8au noeud p`ereRemont´ee de la cl´e8au noeud p`ere→Eclatement + cr´eation nouvelle
racine (e.g. ici11)arbre-B - v1.615 / 31 Insertion Arbre-B
Exemple : cas de l'augmentation de la hauteur 2 / 2 Arbre-B d'ordre 2 :11
581 2 3 46 791016 21
12 13 14 1517 18 19 2022 23 24 25
Insertion cl´e9→Eclatement + remont´ee de la cl´e8au noeud p`ereRemont´ee de la cl´e8au noeud p`ere→Eclatement + cr´eation nouvelle
racine (e.g. ici11) ,→Augmentation d'une unit´e de la hauteurarbre-B - v1.616 / 31 Insertion Arbre-B
Algorithme 1 / 2
Pr´erequis
On suppose poss´eder les fonctions/proc´edures suivantes :fonctioncreerFeuille(c :Tableau[1..MAX] deValeur, nb :NaturelNonNul) :
ArbreBfonctionestUneFeuille(a : ArbreB) : Booleenproc´edureeclater(E/Sa : ArbreB,Eordre :NaturelNonNul)
⌊pr´econdition(s)aˆ.nbCles=2*ordre+1fonctionpositionDInsertion(a : ArbreB, c : Valeur) : NaturelNonNulproc´edureinsererUneCleDansNoeud(E/Sn : Noeud,Ec : Valeur, pos :
NaturelNonNul)proc´edureinsererRacineDeTailleUnDansNoeud(E/Sn : Noeud,Eracine : ArbreB, pos :NaturelNonNul)
⌊pr´econdition(s)racineˆ.nbCles=1arbre-B - v1.617 / 31 Insertion Arbre-B
Algorithme 2 / 2
proc´edureinserer(E/Sa : ArbreB,Ec : Valeur, ordre :NaturelNonNul) ⌊pr´econdition(s)2*ordreD´eclarationtab :Tableau[1..MAX] deValeur debut sia =NIL alors tab[1]←c a←creerFeuille(tab,1) sinon pos←positionDInsertion(a,c) siestUneFeuille(a)alors insererUneCleDansNoeud(aˆ,c,pos) siaˆ.nbCles>2*ordrealors eclater(a, ordre) ifinsi sinon ssArbre←aˆ.sousArbres[pos-1] inserer(ssArbre,c,ordre) sissArbre̸= aˆ.sousArbres[pos-1]alors siaˆ.nbCles>2*ordrealors eclater(a, ordre) ifinsi ifinsi ifinsi ifinsi ifinarbre-B - v1.618 / 31 Suppression Arbre-B
Supression dans un arbre-B d'ordremPrincipe
1La suppression se fait toujours au niveau des feuilles
,→Si la cl´e `a supprimer n'est pas dans une feuille, alors la remplacer par la plus grande valeur des plus petites (ou plus petite valeur des plus grandes) et supprimer cette derni`ere2Si la suppression de la cl´e d'une feuille (r´ecursivement d'un
noeud) am`ene `a avoir moins demcl´es :1Combinaison avec un noeud voisin (avant ou apr`es) 2Descente de la cl´e associant ces deux noeuds (´eclatement du
noeud si n´ecessaire et donc remont´e d'une nouvelle cl´e) ,→la r´ecursivit´e de ce principe peut ammener `a diminuer la hauteur de l'arbre (par le haut) arbre-B - v1.619 / 31 Suppression Arbre-B
Ex. cas 1 : tr`es simple
Arbre-B d'ordre 2 :10 15 27
12 14202526Rappel: ici nombre de cl´es par noeud non racine>1
,→Exemple :Suppression de la cl´e25?M´ethode 1Suppression de la valeur (d´ecalage des valeurs dans le tableau)
arbre-B - v1.620 / 31 Suppression Arbre-B
Ex. cas 2 : simple 1 / 2
Arbre-B d'ordre 2 :1015 27
12 142025Rappel: ici nombre de cl´es par noeud non racine≥2
,→Exemple :Suppression de la cl´e25?M´ethode 1Combinaison avec un noeud voisin
2Descente de la cl´e (ici15 )
3Suppression du noeud
arbre-B - v1.621 / 31 Suppression Arbre-B
Ex. cas 2 : simple 2 / 2
Arbre-B d'ordre 2 :10 27
12 14 15 20 Rappel: ici nombre de cl´es par noeud non racine≥2 ,→Exemple :Suppression de la cl´e25?M´ethode 1Combinaison avec un noeud voisin ([12 14] et 20)
2Descente de la cl´e m´ediane (ici15 )
3Suppression du noeud
arbre-B - v1.622 / 31 Suppression Arbre-B
Ex. cas 3 : avec ´eclatement 1 / 2
Arbre-B d'ordre 2 :4 8
,→Exemple :Suppression de la cl´e6?Suppression cl´e6→Combinaison [1 2 3] et 7 + descente de la cl´e4 au
noeud ifilsDescente de la cl´e4 au noeud ifils →Redistribution + remont´ee de cl´e m´ediane (e.g. ici3)arbre-B - v1.623 / 31 Suppression Arbre-B
Ex. cas 3 : avec ´eclatement 2 / 2
Arbre-B d'ordre 2 :3 8
1 247 ,→Exemple :Suppression de la cl´e6?Suppression cl´e6→Combinaison [1 2 3] et 7 + descente de la cl´e4 au
noeud ifilsDescente de la cl´e4 au noeud ifils →Redistribution + remont´ee de cl´e m´ediane (e.g. ici3)arbre-B - v1.624 / 31 Suppression Arbre-B
Ex. cas 4 : avec un nombre de cl´es inf´erieurs `am1 / 2 Arbre-B d'ordre 2 :11
3 8 1 2479 1016 2111
8 1 2 3 7 9 1016 21
,→Exemple :Suppression de la cl´e4?Combinaison ([1 2] et 7) + descente de la cl´e3 arbre-B - v1.625 / 31 Suppression Arbre-B
Ex. cas 4 : avec un nombre de cl´es inf´erieurs `am2 / 2 Arbre-B d'ordre 2 :811 16 21
1 2 3 79 10
,→Exemple :Suppression de la cl´e4?Combinaison + descente de la cl´e3 Combinaison (8 et [16 21]) + descente de la cl´e 11 ,→Diminution d'une unit´e de la hauteurarbre-B - v1.626 / 31 Suppression Arbre-B
Ex. cas 5 : suppression non feuille
Arbre-B d'ordre 2 :581 2 34 6 79 1048
1 2 36 79 10
,→Exemple :Suppression de la cl´e5?M´ethode 1Recherche d'une cl´e adjacenteA ` ala cl ´e` asupp rimer→on
choisit la plus grande du sous a rbregauche 2Remplacement de la cl´e `a supprimer parA 3Suppression de la cl´eA du sous a rbregauche
arbre-B - v1.627 / 31 Suppression Arbre-B
Algorithme 1 / 4
Pr´erequis
On suppose poss´eder les fonctions/proc´edures suivantes :fonctionplusGrandeValeur(a : ArbreB) :Valeur
⌊pr´econdition(s)a̸=NILfonctionpositionCleDansNoeudRacine(a : ArbreB, c : Valeur) : Entier
⌊pr´econdition(s)a̸=NIL -1 si non pr´esentfonctionpositionSsArbrePouvantContenirValeur(a : Arbre, c : Valeur) : Naturelfonctionfreres(a : ArbreB, posSsArbre :Naturel) :ArbreB, ArbreB
⌊pr´econdition(s)a̸=NILet aˆ.sousArbres[posSsArbre]̸=NILproc´eduresupprimerCleDansNoeudFeuille(E/Sn : Noeud,Ec : Valeur)proc´edurecopierValeurs(StDest :Tableau[1..MAX] deValeur,EtSource :Tableau[1..MAX] deValeur,
indiceDebutDest, indiceDebutSource, nb :NaturelNonNul) ⌊pr´econdition(s)indiceDebutSource+nb NaturelNonNul)arbre-B - v1.628 / 31
Suppression Arbre-B
Algorithme 2 / 4
Cas simples
proc´eduresupprimer(E/Sa : ArbreB,Ec : Valeur, ordre :NaturelNonNul, frereG, frereD : ArbreB, clePere :
Valeur)
D´eclaration...
debut sia̸=NIL alors pos←positionCleDansNoeudRacine(a,c) siestUneFeuille(a)alors sipos̸= -1alors sifrereG =NILet frereD =NILet aˆ.nbCles=1alors desallouer(a)// n'est possible que pour la racine sinon Algo #1 : supprimer c dans une feuille
ifinsi ifinsi sinon sipos = -1alors sinon // cas # 5 des exemples aˆ.valeurs[pos]←cleRemplacement c←cleRemplacement posSsArbre←pos-1 ifinsi Algo #2 : supprimercdans un sous-arbre de rang posSsArbre ifinsi ifinsi ifinarbre-B - v1.629 / 31 Suppression Arbre-B
Algorithme 3 / 4
Algo #1 : supprimercdans une feuillesupprimerCleDansNoeudFeuille(aˆ,c) siaˆ.nbCles2*ordrealors eclater(res, ordre) ifinsi ifinsiarbre-B - v1.630 / 31 Suppression Arbre-B
Algorithme 4 / 4
Algo #2 : supprimercdans le sous-arbrefrereG,frereD←freres(a,posSsArbre) temp←aˆ.sousArbres[posSsArbre] supprimer(temp,c,ordre,frereG,frereD, tempˆ.valeurs[posSsArbre]) sitemp̸= aˆ.sousArbres[posSsArbre]alors //cas ou il y a eu combinaison avec un frere sitempˆ.nbCles=1alors // cas #3 des exemples : il y a eu ´eclatement apr`es combinaison sinon // cas #2 des exemples aˆ.sousArbres[posSsArbre]←temp ifinsi ifinsiExercice Comment prendre en compte le cas #4 des exemples?
arbre-B - v1.631 / 31quotesdbs_dbs15.pdfusesText_21
`A partir de la racine, pour chaque noeud examin´e :La cl´eCest pr´esente (recherche qui peut ˆetre dichotomique)
→succ`esCRecherche d'un ´el´ement de cl´ec3 / 3fonctionestPresentDansNoeud(n : Noeud, c : Valeur) : Booleen, ArbreB
D´eclarationg,d,m :NaturelNonNul
debut g←1 d←n.nbCles tant queg̸=dfaire m←(g+d) div 2 sin.cles[m]≥calors d←m sinon g←m+1 ifinsi ifintantque sin.cles[g]=calors retournerVRAI,NIL sinon retournerFAUX, sousArbres[g-1] ifinsi ifinRemarquegetdr´ef´erencent la position de l'´el´ement sup´erieur ou ´egal `a la valeur recherch´ee
Insertion dans un arbre-B d'ordremPrincipe
1L'insertion se fait r´ecursivement au niveau des feuilles
2Si un noeud a alors plus 2m+ 1 cl´es, il y a ´eclatement du
noeud et remont´ee (grˆace `a la r´ecursivit´e) de la cl´e m´ediane au niveau du p`ere3Il y a augmentation de la hauteur de l'arbre lorsque la racine se retrouve avec 2m+ 1 cl´es ,→l'augmentation de la hauteur de l'arbre se fait donc au niveau de la racine!Exemple : cas d'un noeud plein 1 / 2
Exemple :Insertion de75?51
11 302 712 15 2235 4166 78
53 54 6368 69 71 7679 84 93
1Eclatement du noeud en deux :
Les (deux) plus
p etites cl ´esrestent dans le noeudLes (deux) plus
gran des cl ´essont ins ´er´eesdans un nouveau noeud2Remont´ee de la cl´e m´ediane dans le noeud p`ere (e.g. ici71)Exemple : cas d'un noeud plein 2 / 2
Exemple :Insertion de75?51
11 302 712 15 2235 4166717853 54 6368 69757679 84 93
1Eclatement du noeud en deux :
Les (deux) plus
p etites cl ´esrestent dans le noeudLes (deux) plus
gran des cl ´essont ins ´er´eesdans un nouveau noeud2Remont´ee de la cl´e m´ediane dans le noeud p`ere (e.g. ici71)Insertion Arbre-B
Exemple : cas de l'augmentation de la hauteur 1 / 2Arbre-B d'ordre 2 :5 11 16 21
1 2 3 46 7 8 1012 13 14 1517 18 19 2022 23 24 25
Insertion cl´e9→Eclatement + remont´ee de la cl´e8au noeud p`ereRemont´ee de la cl´e8au noeud p`ere→Eclatement + cr´eation nouvelle
racine (e.g. ici11)arbre-B - v1.615 / 31Insertion Arbre-B
Exemple : cas de l'augmentation de la hauteur 2 / 2Arbre-B d'ordre 2 :11
581 2 3 46 791016 21
12 13 14 1517 18 19 2022 23 24 25
Insertion cl´e9→Eclatement + remont´ee de la cl´e8au noeud p`ereRemont´ee de la cl´e8au noeud p`ere→Eclatement + cr´eation nouvelle
racine (e.g. ici11) ,→Augmentation d'une unit´e de la hauteurarbre-B - v1.616 / 31Insertion Arbre-B
Algorithme 1 / 2
Pr´erequis
On suppose poss´eder les fonctions/proc´edures suivantes :fonctioncreerFeuille(c :Tableau[1..MAX] deValeur, nb :NaturelNonNul) :
ArbreBfonctionestUneFeuille(a : ArbreB) : Booleenproc´edureeclater(E/Sa : ArbreB,Eordre :NaturelNonNul)
⌊pr´econdition(s)aˆ.nbCles=2*ordre+1fonctionpositionDInsertion(a : ArbreB, c : Valeur) : NaturelNonNulproc´edureinsererUneCleDansNoeud(E/Sn : Noeud,Ec : Valeur, pos :
NaturelNonNul)proc´edureinsererRacineDeTailleUnDansNoeud(E/Sn : Noeud,Eracine :ArbreB, pos :NaturelNonNul)
⌊pr´econdition(s)racineˆ.nbCles=1arbre-B - v1.617 / 31Insertion Arbre-B
Algorithme 2 / 2
proc´edureinserer(E/Sa : ArbreB,Ec : Valeur, ordre :NaturelNonNul) ⌊pr´econdition(s)2*ordreSuppression Arbre-B
Supression dans un arbre-B d'ordremPrincipe
1La suppression se fait toujours au niveau des feuilles
,→Si la cl´e `a supprimer n'est pas dans une feuille, alors la remplacer par la plus grande valeur des plus petites (ou pluspetite valeur des plus grandes) et supprimer cette derni`ere2Si la suppression de la cl´e d'une feuille (r´ecursivement d'un
noeud) am`ene `a avoir moins demcl´es :1Combinaison avec un noeud voisin (avant ou apr`es)2Descente de la cl´e associant ces deux noeuds (´eclatement du
noeud si n´ecessaire et donc remont´e d'une nouvelle cl´e) ,→la r´ecursivit´e de ce principe peut ammener `a diminuer la hauteur de l'arbre (par le haut) arbre-B - v1.619 / 31Suppression Arbre-B
Ex. cas 1 : tr`es simple
Arbre-B d'ordre 2 :10 15 27
12 14202526Rappel: ici nombre de cl´es par noeud non racine>1
,→Exemple :Suppression de la cl´e25?M´ethode1Suppression de la valeur (d´ecalage des valeurs dans le tableau)
arbre-B - v1.620 / 31Suppression Arbre-B
Ex. cas 2 : simple 1 / 2
Arbre-B d'ordre 2 :1015 27
12 142025Rappel: ici nombre de cl´es par noeud non racine≥2
,→Exemple :Suppression de la cl´e25?M´ethode1Combinaison avec un noeud voisin
2Descente de la cl´e (ici15 )
3Suppression du noeud
arbre-B - v1.621 / 31Suppression Arbre-B
Ex. cas 2 : simple 2 / 2
Arbre-B d'ordre 2 :10 27
12 14 15 20 Rappel: ici nombre de cl´es par noeud non racine≥2 ,→Exemple :Suppression de la cl´e25?M´ethode1Combinaison avec un noeud voisin ([12 14] et 20)
2Descente de la cl´e m´ediane (ici15 )
3Suppression du noeud
arbre-B - v1.622 / 31Suppression Arbre-B
Ex. cas 3 : avec ´eclatement 1 / 2
Arbre-B d'ordre 2 :4 8
,→Exemple :Suppression de la cl´e6?Suppression cl´e6→Combinaison [1 2 3] et 7 + descente de la cl´e4 au
noeud ifilsDescente de la cl´e4 au noeud ifils →Redistribution + remont´ee de cl´e m´ediane (e.g. ici3)arbre-B - v1.623 / 31Suppression Arbre-B
Ex. cas 3 : avec ´eclatement 2 / 2
Arbre-B d'ordre 2 :3 8
1 247,→Exemple :Suppression de la cl´e6?Suppression cl´e6→Combinaison [1 2 3] et 7 + descente de la cl´e4 au
noeud ifilsDescente de la cl´e4 au noeud ifils →Redistribution + remont´ee de cl´e m´ediane (e.g. ici3)arbre-B - v1.624 / 31Suppression Arbre-B
Ex. cas 4 : avec un nombre de cl´es inf´erieurs `am1 / 2Arbre-B d'ordre 2 :11
3 81 2479 1016 2111
8 1 2 37 9 1016 21
,→Exemple :Suppression de la cl´e4?Combinaison ([1 2] et 7) + descente de la cl´e3 arbre-B - v1.625 / 31Suppression Arbre-B
Ex. cas 4 : avec un nombre de cl´es inf´erieurs `am2 / 2Arbre-B d'ordre 2 :811 16 21
1 2 3 79 10
,→Exemple :Suppression de la cl´e4?Combinaison + descente de la cl´e3 Combinaison (8 et [16 21]) + descente de la cl´e 11 ,→Diminution d'une unit´e de la hauteurarbre-B - v1.626 / 31Suppression Arbre-B
Ex. cas 5 : suppression non feuille
Arbre-B d'ordre 2 :581 2 34 6 79 1048
1 2 36 79 10
,→Exemple :Suppression de la cl´e5?M´ethode1Recherche d'une cl´e adjacenteA ` ala cl ´e` asupp rimer→on
choisit la plus grande du sous a rbregauche 2Remplacement de la cl´e `a supprimer parA3Suppression de la cl´eA du sous a rbregauche
arbre-B - v1.627 / 31Suppression Arbre-B
Algorithme 1 / 4
Pr´erequis
On suppose poss´eder les fonctions/proc´edures suivantes :fonctionplusGrandeValeur(a : ArbreB) :Valeur
⌊pr´econdition(s)a̸=NILfonctionpositionCleDansNoeudRacine(a : ArbreB, c : Valeur) : Entier
⌊pr´econdition(s)a̸=NIL-1 si non pr´esentfonctionpositionSsArbrePouvantContenirValeur(a : Arbre, c : Valeur) : Naturelfonctionfreres(a : ArbreB, posSsArbre :Naturel) :ArbreB, ArbreB
⌊pr´econdition(s)a̸=NILet aˆ.sousArbres[posSsArbre]̸=NILproc´eduresupprimerCleDansNoeudFeuille(E/Sn : Noeud,Ec : Valeur)proc´edurecopierValeurs(StDest :Tableau[1..MAX] deValeur,EtSource :Tableau[1..MAX] deValeur,
indiceDebutDest, indiceDebutSource, nb :NaturelNonNul)⌊pr´econdition(s)indiceDebutSource+nb proc´eduresupprimer(E/Sa : ArbreB,Ec : Valeur, ordre :NaturelNonNul, frereG, frereD : ArbreB, clePere :NaturelNonNul)arbre-B - v1.628 / 31
Suppression Arbre-B
Algorithme 2 / 4
Cas simples
Valeur)
D´eclaration...
debut sia̸=NIL alors pos←positionCleDansNoeudRacine(a,c) siestUneFeuille(a)alors sipos̸= -1alors sifrereG =NILet frereD =NILet aˆ.nbCles=1alors desallouer(a)// n'est possible que pour la racine sinon Algo #1 : supprimer c dans une feuille
ifinsi ifinsi sinon sipos = -1alors sinon // cas # 5 des exemples aˆ.valeurs[pos]←cleRemplacement c←cleRemplacement posSsArbre←pos-1 ifinsi Algo #2 : supprimercdans un sous-arbre de rang posSsArbre ifinsi ifinsi ifinarbre-B - v1.629 / 31 Suppression Arbre-B
Algorithme 3 / 4
Algo #1 : supprimercdans une feuillesupprimerCleDansNoeudFeuille(aˆ,c) siaˆ.nbClesSuppression Arbre-B
Algorithme 4 / 4
Algo #2 : supprimercdans le sous-arbrefrereG,frereD←freres(a,posSsArbre) temp←aˆ.sousArbres[posSsArbre] supprimer(temp,c,ordre,frereG,frereD, tempˆ.valeurs[posSsArbre]) sitemp̸= aˆ.sousArbres[posSsArbre]alors //cas ou il y a eu combinaison avec un frere sitempˆ.nbCles=1alors // cas #3 des exemples : il y a eu ´eclatement apr`es combinaison sinon // cas #2 des exemples aˆ.sousArbres[posSsArbre]←temp ifinsi ifinsiExercice Comment prendre en compte le cas #4 des exemples?
arbre-B - v1.631 / 31quotesdbs_dbs15.pdfusesText_21
[PDF] structure de données les arbres exercices corrigé
[PDF] arbre binaire de recherche suppression
[PDF] exercices sur les arbres binaires en c
[PDF] exercice corrigé arbre rouge et noir
[PDF] arbre binaire de recherche en c
[PDF] les arbres en c openclassroom
[PDF] arbre binaire de recherche algorithme
[PDF] arbre binaire de recherche algorithme suppression
[PDF] parcours en profondeur arbre
[PDF] arbre binaire complet
[PDF] dénombrement cours
[PDF] arbre de probabilité pile ou face
[PDF] arbre de probabilité seconde
[PDF] arbre probabilité conditionnelle
