Arbres de Recherche M-aires PDF

Arbres en Mémoire Secondaire 1. Fichiers sous forme d’Arbres de Recherche M-aires - Définitions - Algorithmes : Recherche, Inordre, Insertion et Suppression 2. Fichiers sous forme de B-Arbres - Définition et Propriétés - Algorithmes : Insertion, Suppression, Chargement optimisé - Variantes : B+ Ar...

Arbres en Mémoire Secondaire 1. Fichiers sous forme d’Arbres de Recherche M-aires - Définitions - Algorithmes : Recherche, Inordre, Insertion et Suppression 2. Fichiers sous forme de B-Arbres - Définition et Propriétés - Algorithmes : Insertion, Suppression, Chargement optimisé - Variantes : B+ Arbres, B+ Arbres préfixés, B* Arbres Pr Hidouci W.K. (http://hidouci.esi.dz) / SFSD / ESI 1  Arbres en Mémoire Secondaire Les blocs d’un fichier peuvent être organisés sous forme d’un arbre de blocs C’est utile pour représenter des arbres de recherche m-aires en Mémoire Secondaire (MS) Définitions Un arbre de recherche m-aire d’ordre N est un arbre où chaque nœud peut contenir, au maximum : N-1 valeurs ordonnées (val1,val2,...valN-1) et N fils (Fils1,Fils2,… FilsN) Pour un nœud donné, le degré représente le nombre de fils courant. Pour un nœud donné, le nombre de valeurs courantes est toujours = degré - 1 Au minimum : degré = 2 et au maximum : degré = N Propriétés a) Toutes les valeurs dans le sous-arbre Fils1 sont < val1 b) Toutes les valeurs dans le sous-arbre Filsj sont > valj-1 et < valj (avec j dans [2 , degré-1] ) c) Toutes les valeurs dans le sous-arbre Filsdegré sont > valdegré-1 Pr Hidouci W.K. (http://hidouci.esi.dz) / SFSD / ESI 2  Exemple d’arbre de recherche m-aire d’ordre 5 i 32 33 40 99 a k h 10 16 18 20 37 55 70 96 97 b g c d f e 2 3 5 9 12 14 27 30 42 47 50 54 57 60 71 76 80 94 j n 43 44 89 90 92 93 m 82 83 84 88 Le nœud racine : i Les nœuds internes : i,a,h,d,e,n Les nœuds feuilles : b,g,c,k,j,f,m La profondeur (ou hauteur) de l’arbre = 4 (le niveau de la feuille la plus éloignée) degré( a ) = 5, degré( b ) = 5, degré( c ) = 3, degré( d ) = 5, degré( e ) = 5, degré( f ) = 3, degré( g ) = 3,… etc Propriété Top-Down: Tous les nœuds internes sont pleins à 100 % (optionnellement vérifiée) Pr Hidouci W.K. (http://hidouci.esi.dz) / SFSD / ESI 3  Exemple d’arbre de recherche m-aire d’ordre 5 i 32 33 40 99 a k h 10 16 18 20 37 55 70 96 97 b g c d f e 2 3 5 9 12 14 27 30 42 47 50 54 57 60 71 76 80 94 j n 43 44 89 90 92 93 m 82 83 84 88 bloc a bloc b bloc k val 10 | 16 | 18 | 20 5 val 2| 3| 5| 9 5 val 37 | | | 2 deg deg... deg Fils b | g | -1 | -1 | c Fils -1 | -1 | -1 | -1 | -1 Fils -1 | -1 | | | Pr Hidouci W.K. (http://hidouci.esi.dz) / SFSD / ESI 4  Exemple d’arbre de recherche m-aire d’ordre 5 i 32 33 40 99 a k h 10 16 18 20 37 55 70 96 97 b g c d f e 2 3 5 9 12 14 27 30 42 47 50 54 57 60 71 76 80 94 j n 43 44 89 90 92 93 m 82 83 84 88 a b c d e f g h i j k m n 10,16,18,20 2, 3, 5, 9 27,30, , 42,47,50,54 71,76,80,94 57,60, , 12,14, , 55,70,96,97 32,33,40,99 43,44, , 37, , , 82,83,84,88 89,90,92,93....................................... Fichier organisé en arbres m-aire de recherche : les blocs sont chaînés selon une structure d’arbre m-aire → Le numéro du bloc Racine peut être gardé comme caractéristique du fichier (dans le Bloc d’entête) Pr Hidouci W.K. (http://hidouci.esi.dz) / SFSD / ESI 5 Utilisations des arbres de recherche m-aire … a1 595, ccc, 78,...... 1- Comme index en MS vers un fichier de données......... Type Tval = struct (clé , adr ) a2 243, aaa, 78 , … … … Fichier de … données … Fichier … | …,. | (243,a2) |... … Index a3 187, bbb, 21, … …,. | (595,a1) | … | … … … … | …,. | (187,a3) |... … …... 2- Comme fichier de données organisé en arbre Type Tval = Tenreg … | …,. | (243,aaa,78,...) |... Fichier de données …,. | (595,ccc,78,...) | … |… … | …,. | (187,bbb,21,...) |... Pr Hidouci W.K. (http://hidouci.esi.dz) / SFSD / ESI 6 Mécanisme de recherche i 32 33 40 99 a k h 10 16 18 20 37 55 70 96 97 b g c d f e 2 3 5 9 12 14 27 30 42 47 50 54 57 60 71 76 80 94 j n 43 44 89 90 92 93 m 82 83 84 88 La recherche d'une valeur C commence dans le nœud racine P et se poursuit le long d'une branche : 1- Si C existe dans P alors la recherche s'arrête avec succès 2- Si C n'existe pas dans P alors - soit k la position dans P où devrait se trouver C (pour que les valeurs restent ordonnées) - Si Filsk différent de -1 (nil) alors P ← Filsk ; aller à 1 - Sinon la recherche s'arrête avec échec. Ex : Rech( 47 ) → parcours de la branche : i , h , d (arrêt avec succès : P = d et k = 2) Rech( 15 ) → parcours de la branche : i , a , g (arrêt avec échec : P = g et k = 3) Pr Hidouci W.K. (http://hidouci.esi.dz) / SFSD / ESI 7 Algorithme de recherche i 32 33 40 99 a k h 10 16 18 20 37 55 70 96 97 b g c d f e 2 3 5 9 12 14 27 30 42 47 50 54 57 60 71 76 80 94 j n 43 44 89 90 92 93 buf : Tbloc m 82 83 84 88 Rech( c ) ⇒ ( trouv , numB , pos ) Ouvrir( F , … , ‘A’ ) numB ← Entete( F , 1 ) // le num du bloc Racine trouv ← faux ; i ← numB TQ ( i -1 ET non trouv ) LireDir( F , i , buf ) ; numB ← i recherche interne de c dans buf.val[ ] ⇒ ( pos , trouv ) SI (non trouv ) i ← buf.Fils[ pos ] FSI FTQ Fermer( F ) Pr Hidouci W.K. (http://hidouci.esi.dz) / SFSD / ESI 8 En gardant la trace des i blocs visités (avec une pile) 32 33 40 99 a k h 10 16 18 20 37 55 70 96 97 b g c d f e 2 3 5 9 12 14 27 30 42 47 50 54 57 60 71 76 80 94 j n 43 44 89 90 92 93 P : pile de < Tbloc , entier , entier > buf : Tbloc m 82 83 84 88 Rech( c ) ⇒ ( trouv , numB , pos ) Ouvrir( F , … , ‘A’ ) CreerPile( P ) numB ← Entete( F , 1 ) // le num du bloc Racine trouv ← faux TQ ( numB -1 ET non trouv ) LireDir( F , numB , buf ) recherche interne de c dans buf.val[ ] ⇒ ( pos , trouv ) SI (non trouv ) Empiler( P , < buf , numB, pos > ) ; numB ← buf.Fils[ pos ] FSI FTQ Fermer( F ) Pr Hidouci W.K. (http://hidouci.esi.dz) / SFSD / ESI 9  Exemple : recherche de 92 i Les blocs visités : 32 33 40 99 i h pile a k h e 10 16 18 20 37 55 70 96 97 n buf b g c d f e 2 3 5 9 12 14 27 30 42 47 50 54 57 60 71 76 80 94 j n 43 44 89 90 92 93 P : pile de < Tbloc , entier , entier > buf : Tbloc m 82 83 84 88 Rech( c ) ⇒ ( trouv , numB , pos ) Ouvrir( F , … , ‘A’ ) CreerPile( P ) numB ← Entete( F , 1 ) // le num du bloc Racine trouv ← faux TQ ( numB -1 ET non trouv ) LireDir( F , numB , buf ) recherche interne de c dans buf.val[ ] ⇒ ( pos , trouv ) SI (non trouv ) Empiler( P , < buf , numB, pos > ) ; numB ← buf.Fils[ pos ] FSI FTQ Fermer( F ) Pr Hidouci W.K. (http://hidouci.esi.dz) / SFSD / ESI 10 Parcours inordre i 32 33 40 99 a k h 10 16 18 20 37 55 70 96 97 b g c d f e 2 3 5 9 12 14 27 42 47 50 54 57 71 76 80 94 j n 43 44 89 90 92 93 m 82 83 84 88 Les valeurs seront visitées (traitées) en ordre croissant : 2, 3, 5, 9, 10, 12, 14, 16, 18, 20, 27, 32, 33, 37, 40, 42, 43, 44, 47, 50, 54, 55, 57, 70, 71,76, 80, b a g a c i k i d j d h f h e 82, 83, 84, 88, 89, 90, 92, 93, 94, 96, 97, 99 m n e h i Pr Hidouci W.K. (http://hidouci.esi.dz) / SFSD / ESI 11 Parcours inordre i 32 33 40 99 a k h 10 16 18 20 37 55 70 96 97 b g c d f e 2 3 5 9 12 14 27 42 47 50 54 57 71 76 80 94 j n 43 44 89 90 92 93 m 82 83 84 88 Inordre ( r:entier ) var buf:Tbloc // var locales i:entier SI ( r -1 ) LireDir( F , r , buf ) POUR (i = 1 , buf.deg – 1 ) Inordre( buf.fils[ i ] ) traiter la valeur buf.val[ i ]... FP Inordre( buf.fils[ buf.deg ] ) FSI Pr Hidouci W.K. (http://hidouci.esi.dz) / SFSD / ESI 12 Parcours inordre i 32 33 40 99 a k h 10 16 18 20 37 55 70 96 97 b g c d f e 2 3 5 9 12 14 27 42 47 50 54 57 71 76 80 94 j n 43 44 89 90 92 93 m 82 83 84 88 Inordre ( r:entier ) var buf:Tbloc // var locales i:entier La plus petite valeur de l’arbre (2) se trouve SI ( r -1 ) ⇒ à la 1ere position du nœud le plus à gauche. LireDir( F , i , buf ) POUR (i = 1 , buf.deg – 1 ) Inordre( buf.fils[ i ] ) (La plus grande ? ) traiter la valeur buf.val[ i ]... FP Inordre( buf.fils[ buf.deg ] ) Comment localiser le suivant inordre d’une valeur ? FSI Pr Hidouci W.K. (http://hidouci.esi.dz) / SFSD / ESI 13  i Suivant Inordre 32 33 40 99 a k h 10 16 18 20 37 55 70 96 97 d f e 2 3 5 9 12 14 27 42 47 50 54 57 71 76 80 94 b g c Filsk+1 == -1 j n 43 44 89 90 92 93 Suivant de valk (valk se trouve dans le nœud p) m 82 83 84 88 Ex : le suivant de 2 ⇒ 3, (car le fils à droite de 2 est -1) (c-a-d le fils à droite de valk est -1) (c-a-d Filsk+1 est -1) Pr Hidouci W.K. (http://hidouci.esi.dz) / SFSD / ESI 14  i Suivant Inordre 32 33 40 99 a k h 10 16 18 20 37 55 70 96 97 b g c d f e 2 3 5 9 12 14 27 42 47 50 54 57 71 76 80 94 j n 43 44 89 90 92 93 Suivant de valk (valk se trouve dans le nœud p) m 82 83 84 88 Si ( k < degré-1 && Filsk+1 == -1 ) Le suivant ← valk+1 (dans le même nœud p) Ex : le suivant de 2 ⇒ 3, le suivant de 3 ⇒ 5, le suivant de 5 ⇒ 9, le suivant de 12 ⇒ 14, le suivant de 16 ⇒ 18, le suivant de 18 ⇒ 20, le suivant de 32 ⇒ 33, …. etc Pr Hidouci W.K. (http://hidouci.esi.dz) / SFSD / ESI 15 Suivant Inordre i 32 33 40 99 Filsk+1 ¹ -1 a k h 10 16 18 20 37 55 70 96 97 b g c d f e 2 3 5 9 12 14 27 42 47 50 54 57 71 76 80 94 j n 43 44 89 90 92 93 m 82 83 84 88 Ex : le suivant de 40 ⇒ 42 (car le fils à droite de 40 est différent de -1) (c-a-d Filsk+1 est différent de -1) Pr Hidouci W.K. (http://hidouci.esi.dz) / SFSD / ESI 16  i Suivant Inordre 32 33 40 99 a k h 10 16 18 20 37 55 70 96 97 b g c d f e 2 3 5 9 12 14 27 42 47 50 54 57 71 76 80 94 j n 43 44 89 90 92 93 Suivant de valk (valkse trouve dans le nœud p) m 82 83 84 88 Si ( k < degré-1 && Filsk+1 == -1 ) Le suivant ← valk+1 (dans le même nœud p) Sinon Si ( Filsk+1 ¹ -1 ) Le suivant est la plus petite valeur du sous-arbre de racine Filsk+1 Ex : le suivant de 10 ⇒ 12, le suivant de 20 ⇒ 27, le suivant de 33 ⇒ 37, le suivant de 40 ⇒ 42, le suivant de 42 ⇒ 43, le suivant de 55 ⇒ 57, le suivant de 70 ⇒ 71 et le suivant de 80 ⇒ 82 Pr Hidouci W.K. (http://hidouci.esi.dz) / SFSD / ESI 17  i Suivant Inordre 32 33 40 99 a k h 10 16 18 20 37 55 70 96 97 b g c d f e 2 3 5 9 12 14 27 42 47 50 54 57 71 76 80 94 Filsdegré == -1 n 43 44 89 90 92 93 j m 82 83 84 88 Ex : le suivant de 27 ⇒ 32 ( car 27 est la dernière valeur du nœud et son fils droit est -1 ) ( c-a-d k == degré-1 et Filsdegré == -1 ) Pr Hidouci W.K. (http://hidouci.esi.dz) / SFSD / ESI 18  i Suivant Inordre 32 33 40 99 a k h 10 16 18 20 37 55 70 96 97 b g c d f e 2 3 5 9 12 14 27 42 47 50 54 57 71 76 80 94 j n 43 44 89 90 92 93 Suivant de valk (valk se trouve dans le nœud p) m 82 83 84 88 Si ( k < degré-1 && Filsk+1 == -1 ) Le suivant ← valk+1 (dans le même nœud p) Sinon Si ( Filsk+1 ¹ -1 ) Le suivant est la plus petite valeur du sous-arbre de racine Filsk+1 Sinon // c-a-d : Si ( k == degré-1 && Filsdegré == -1 ) Le suivant est dans le 1er ascendant duquel on est descendu par un fils autre que le dernier ( soit Filsj avec j < degré ). Le suivant est alors la valeur val j dans cet ascendant. Ex : le suivant de 9 ⇒ 10, le suivant de 14 ⇒ 16, le suivant de 27 ⇒ 32, le suivant de 37 ⇒ 40, le suivant de 44 ⇒ 47, le suivant de 54 ⇒ 55, le suivant de 57 ⇒ 70, le suivant de 88 ⇒ 89, le suivant de 93 ⇒ 94, le suivant de 94 ⇒ 96, le suivant de 97 ⇒ 99. Pr Hidouci W.K. (http://hidouci.esi.dz) / SFSD / ESI 19 Exercice Donner l’algorithme pour la requête à intervalle : « trouver toutes les valeurs de l’arbre comprises entre les bornes a et b » Indications : - utiliser l’algorithme de recherche avec une pile, pour localiser la valeur a - utiliser la pile pour accéder aux suivants inordre et parcourir ainsi l’intervalle jusqu’à atteindre ou dépasser la valeur b Pr Hidouci W.K. (http://hidouci.esi.dz) / SFSD / ESI 20 Mécanisme d’insertion Si le dernier nœud visité par la recherche n’est pas plein... a 24 40 69 82 b c d e f 2 5 12 20 27 30 42 50 55 60 71 80 90 95 97 99 g h i 10 47 48 63 65 66 Alors insérer la nouvelle valeur dans le dernier nœud visité (décalages internes au bloc) a 24 40 69 82 b c d e f 2 5 12 20 27 30 42 50 55 60 71 80 90 95 97 99 Ex : Insertion g h i de 64 10 47 48 63 64 65 66 Le dernier nœud visité Pr Hidouci W.K. (http://hidouci.esi.dz) / SFSD / ESI 21 Mécanisme d’insertion Si le dernier nœud visité par la recherche est déjà à plein 100 %... a 24 40 69 82 b c d e f 2 5 12 20 27 30 42 50 55 60 71 80 90 95 97 99 g 10 h 47 48 i 63 64 65 66 Alors allouer un nouveau bloc contenant la nouvelle valeur et le connecter avec l’arbre a 24 40 69 82 b c d e f 2 5 12 20 27 30 42 50 55 60 71 80 90 95 97 99 Ex : Insertion g h 47 48 i 10 63 64 65 66 de 61 Le dernier nœud visité n 61 Le nouveau nœud alloué Pr Hidouci W.K. (http://hidouci.esi.dz) / SFSD / ESI 22  Mécanisme d’insertion Pour insérer une nouvelle valeur V dans un arbre de recherche m-aire, il faut : 1- Rechercher V pour vérifier qu'elle n'existe pas et pour localiser le dernier nœud visité P. La recherche retourne aussi l’indice k où devrait se trouver la valeur V pour maintenir l’ordre des valeurs dans P. 2- SI P n'est pas plein, 2.1- Insérer V dans P, par décalages afin de garder le tableau de valeurs ordonné. SINON 2.2- Allouer un nouveau bloc Q, contenant une seule valeur V et 2 fils à -1 2.3- Connecter Q comme filsk de P (ce dernier filsk était forcément à -1) FSI Pourquoi ? Remarques - Maintient la propriété Top-Down - Peut engendrer un fort déséquilibre de l’arbre → Nécessite donc des réorganisations périodiques Pr Hidouci W.K. (http://hidouci.esi.dz) / SFSD / ESI 23  Mécanisme de suppression a- Suppression Logique : Ajout d’un indicateur d’effacement logique au niveau de chaque valeur i 32/f 33/f 40/f 99/f a k h 10/f 16/v 18/f 20/f 37/f 55/v 70/v 96/f 97/f b c d e 2/f 3/f 5/f 9/f 27/f 30/f 42/f 47/f 50/v 54/f 71/f 76/f 80/f 94/f f 12/f 14/f 57/v 60/f g j n 43/f 44/f 89/f 90/v 92/f 93/f m 82/v 83/f 84/f 88/v Dans cet exemple, les valeurs 16, 50, 55, 57, 70, 82, 88 et 90 ont été supprimées Pr Hidouci W.K. (http://hidouci.esi.dz) / SFSD / ESI 24  Mécanisme de suppression b- Suppression Physique d’une valeur v : 1. Rechercher le nœud contenant la valeur v ⇒ soient p le nœud trouvé et q son père (ou -1) 2. SI p est une feuille suppression de v par décalages ; SI p devient vide, libérer p (et m-a-j du père q) FSI stop 3. SINON // donc p est un nœud interne 3.1 rechercher le suivant ou le précédent inordre ⇒ valeur : v’ et nœud : p’ 3.2 remplacer v par v’ dans p 3.3 v ← v’ ; p ← p’ ; Aller à 2 a 24 40 69 82 b c d e f 2 5 12 20 27 30 42 50 55 60 71 80 90 95 97 99 g h i 10 47 48 63 65 66 Pr Hidouci W.K. (http://hidouci.esi.dz) / SFSD / ESI 25  - Suppression Physique d’une valeur v : 1. Rechercher le nœud contenant la valeur v ⇒ p 2. SI p est une feuille suppression de v par décalages ; SI p devient vide, libérer p et m-a-j son père FSI Stop 3. SINON // donc p est un nœud interne 3.1 rechercher le suivant ou le précédent inordre ⇒ valeur : v’ et nœud : p’ 3.2 remplacer v par v’ dans p 3.3 v ← v’ ; p ← p’ ; Aller à 2 Ex : sup (40) 1 rech de 40 ⇒ (a,2) // un nœud interne... a 24 40 69 82 b c d e f 2 5 12 20 27 30 42 50 55 60 71 80 90 95 97 99 g h i 10 47 48 63 65 66 Pr Hidouci W.K. (http://hidouci.esi.dz) / SFSD / ESI 26  - Suppression Physique d’une valeur v : 1. Rechercher le nœud contenant la valeur v ⇒ p 2. SI p est une feuille suppression de v par décalages ; SI p devient vide, libérer p et m-a-j son père FSI Stop 3. SINON // donc p est un nœud interne 3.1 rechercher le suivant ou le précédent inordre ⇒ valeur : v’ et nœud : p’ 3.2 remplacer v par v’ dans p 3.3 v ← v’ ; p ← p’ ; Aller à 2 Ex : sup (40) 1 rech de 40 ⇒ (a,2) // un nœud interne … 3 suiv. Inordre de 40 = 42 (d,1) et remplacement de 40 par 42 dans a // d est aussi un nœud interne... a 24 42 69 82 b c d e f 2 5 12 20 27 30 42 50 55 60 71 80 90 95 97 99 g h i 10 47 48 63 65 66 Pr Hidouci W.K. (http://hidouci.esi.dz) / SFSD / ESI 27  - Suppression Physique d’une valeur v : 1. Rechercher le nœud contenant la valeur v ⇒ p 2. SI p est une feuille suppression de v par décalages ; SI p devient vide, libérer p et m-a-j son père FSI Stop 3. SINON // donc p est un nœud interne 3.1 rechercher le suivant ou le précédent inordre ⇒ valeur : v’ et nœud : p’ 3.2 remplacer v par v’ dans p 3.3 v ← v’ ; p ← p’ ; Aller à 2 Ex : sup (40) 1 rech de 40 ⇒ (a,2) // un nœud interne … 3 suiv. Inordre de 40 = 42 (d,1) et remplacement de 40 par 42 dans a // d est aussi un nœud interne … 3 suiv. Inordre de 42 = 47 (h,1) et remplacement de 42 par 47 dans d // h est un nœud feuille … a 24 42 69 82 b c d e f 2 5 12 20 27 30 47 50 55 60 71 80 90 95 97 99 g h i 10 47 48 63 65 66 Pr Hidouci W.K. (http://hidouci.esi.dz) / SFSD / ESI 28  - Suppression Physique d’une valeur v : 1. Rechercher le nœud contenant la valeur v ⇒ p 2. SI p est une feuille suppression de v par décalages ; SI p devient vide, libérer p et m-a-j son père FSI Stop 3. SINON // donc p est un nœud interne 3.1 rechercher le suivant ou le précédent inordre ⇒ valeur : v’ et nœud : p’ 3.2 remplacer v par v’ dans p 3.3 v ← v’ ; p ← p’ ; Aller à 2 Ex : sup (40) 1 rech de 40 ⇒ (a,2) // un nœud interne … 3 suiv. Inordre de 40 = 42 (d,1) et remplacement de 40 par 42 dans a // d est aussi un nœud interne … 3 suiv. Inordre de 42 = 47 (h,1) et remplacement de 42 par 47 dans d // h est un nœud feuille … 2 suppression de 47 par décalages dans h. a 24 42 69 82 b c d e f 2 5 12 20 27 30 47 50 55 60 71 80 90 95 97 99 g h i 10 48 63 65 66 Pr Hidouci W.K. (http://hidouci.esi.dz) / SFSD / ESI 29