Pk

Fait des petites modifs sur les pseudo codes b arbre. Il me semble qu'il manquait un bout de critere pour décider qu'il faut ajouter un niveau. Je te laisse vérifier.

slides/cours_22.md

@@ -289,7 +289,7 @@ patat:
 
 ## Exercice (matrix, 15min)
 
-* Insérer 20, 40, 10, 30, 15, 35, 7, 26, 18, 22, 5, 42, 13, 46, 27, 8, 32, 38, 24, 45, 25, 2, 14, 28, 29, 41,
+* Insérer 20, 40, 10, 30, 15, 35, 7, 26, 18, 22, 5, 42, 13, 46, 27, 8, 32, 38, 24, 45, 25, 2, 14, 28, 32, 41,
 * Dans un B-arbre d'ordre 2.
 
 # Les B-arbres
@@ -411,15 +411,17 @@ booléen est_dans_page(page, valeur) // la valeur est dans la page
 
 ```C
 booléen est_feuille(page) 
-    retourne (page.tab[0] == vide)
+    retourne (page.tab[0].pg == vide)
+
 entier position(page, valeur)
     i = 0
-    tant que i < page.nb && val >= page.tab[i]
+    tant que i < page.nb && val > page.tab[i+1].val
         i += 1
     retourne i
+
 booléen est_dans_page(page, valeur)
     i = position(page, valeur)
-    retourne (i > 0 && page.tab[i] == valeur)
+    retourne (page.nb > 0 && page.tab[i+1].val == valeur)
 ```
 
 # Les B-arbres
@@ -441,6 +443,7 @@ page nouvelle_page(ordre)
     page.nb = 0
     page.tab = allouer(2*ordre+2)
     retourner page
+
 rien liberer_memoire(page)
     si est_feuille(page)
         liberer(page.tab)
@@ -467,7 +470,7 @@ page recherche(page, valeur) // retourner la page contenant
 page recherche(page, valeur)
     si est_dans_page(page, valeur)
         retourne page
-    sinon si est_feuille(page) && !est_dans_page(page, valeur)
+    sinon si est_feuille(page) 
         retourne vide
     sinon
         recherche(page.tab[position(page, valeur)], valeur)
@@ -478,17 +481,17 @@ page recherche(page, valeur)
 ## Les fonctions
 
 ```C
-page inserer(page, valeur) // inserer une valeur
+page inserer_valeur(page, valeur) // inserer une valeur
 ```
 
 . . .
 
 ```C
-page inserer(page, valeur)
+page inserer_valeur(page, valeur)
     element = nouvel_element(valeur)
     // on change element pour savoir s'il faut le remonter
     inserer_element(page, element) 
-    si element.page != vide
+    si element.page != vide && page.nb > 2*page.ordre
         // si on atteint le sommet!
         page = ajouter_niveau(page, element) 
     retourne page
@@ -499,8 +502,7 @@ page inserer(page, valeur)
 ## Les fonctions
 
 ```C
-// inserer un element et voir s'il remonte
-rien inserer_element(page, element) 
+rien inserer_element(page, element) // inserer un element et voir s'il remonte
 ```
 
 . . .
@@ -512,6 +514,7 @@ rien inserer_element(page, element)
     sinon
         sous_page = page.tab[position(page, element)].page
         inserer_element(sous_page, element)
+        // un element a été promu
         si element.page != vide
             placer(page, element)
 ```
@@ -528,10 +531,10 @@ rien placer(page, element) // inserer un élément
 
 ```C
 rien placer(page, element)
-    i = position(page, element.clé)
-    pour i de 2*page.ordre à i+1
+    pos = position(page, element.clé)
+    pour i de 2*page.ordre à pos+1
         page.tab[i+1] = page.tab[i]
-    page.tab[i+1] = element
+    page.tab[pos+1] = element
     page.nb += 1
     si page.nb > 2*page.ordre
         scinder(page, element)
@@ -562,10 +565,8 @@ rien scinder(page, element)
 ## Les fonctions (5min matrix)
 
 ```C
-// si on remonte à la racine...
-// on doit créer une nouvelle racine
-page ajouter_niveau(page, element) 
-                                   
+page ajouter_niveau(page, element) // si on remonte à la racine...
+                                   // on doit créer une nouvelle racine
 ```
 
 . . .