Pk

J'ai un peu modifié inserer_element et placer, j'ai l'impression qu'il faut qqch pour eviter de refaire des "placer" dans tous les appels recursifs des qu'un scinder s'est produit, mais continuer à en faire tant qu'on scinde (je sais pas si c'est clair)

slides/cours_23.md

@@ -127,15 +127,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].clef
         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].clef == valeur)
 ```
 
 # Les B-arbres
@@ -157,6 +159,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)
@@ -183,7 +186,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)
@@ -202,9 +205,11 @@ page inserer(page, valeur) // inserer une valeur
 ```C
 page inserer(page, valeur)
     element = nouvel_element(valeur)
-    inserer_element(page, element) // on change elmement pour savoir s'il faut le remonter
-    si element.page != vide
-        page = ajouter_niveau(page, element) // si on atteint le sommet!
+    // on change element pour savoir s'il faut le remonter
+    inserer_element(page, element) 
+    si element != vide && element.page != vide
+        // si on atteint le sommet
+        page = ajouter_niveau(page, element) 
     retourne page
 ```
 
@@ -213,7 +218,8 @@ page inserer(page, valeur)
 ## Les fonctions
 
 ```C
-rien inserer_element(page, element) // inserer un element et voir s'il remonte
+// inserer un element et voir s'il remonte
+rien inserer_element(page, element) 
 ```
 
 . . .
@@ -225,7 +231,7 @@ rien inserer_element(page, element)
     sinon
         sous_page = page.tab[position(page, element)].page
         inserer_element(sous_page, element)
-        si element.page != vide
+        si element != vide && element.page != vide
             placer(page, element)
 ```
 
@@ -241,13 +247,15 @@ rien placer(page, element) // inserer un élément
 
 ```C
 rien placer(page, element)
-    i = position(page, element.clé)
+    i = position(page, element.clef)
     pour i de 2*page.ordre à i+1
         page.tab[i+1] = page.tab[i]
     page.tab[i+1] = element
     page.nb += 1
     si page.nb > 2*page.ordre
         scinder(page, element)
+    sinon
+        element = vide
 ```
 
 # Les B-arbres
@@ -266,7 +274,7 @@ rien scinder(page, element)
     new_page.nb = page.ordre
     pour i de 0 à ordre inclu
         new_page.tab[i] = page.tab[i+ordre+1]
-    element.clé = page.tab[ordre+1].clé
+    element.clef = page.tab[ordre+1].clé
     element.page = new_page
 ```
 
@@ -285,7 +293,7 @@ page ajouter_niveau(page, element) // si on remonte à la racine...
 page ajouter_niveau(page, element) 
     tmp = nouvelle_page(page.ordre)
     tmp.tab[0].page = page
-    tmp.tab[1].clé = element.clé
+    tmp.tab[1].clef = element.clef
     tmp.tab[1].page = element.page
     retourne tmp
 ```

[orestis.malaspin]

c'est au cas où l'allocation de élément a merdé?

sinon jevois pas pourquoi avoir si element != vide

[orestis.malaspin]

pareil qu'avant, d'habitude je vérifie pas si l'alloc à foirer...

[orestis.malaspin]

je me dis que rien faire c'est ok. on veut pas tuer l'élément...

[pierre.kunzli]

C'est pas pour tuer l'élément, c'est que sinon on aura un appel à placer dans tout les retours récursifs après inserer_element dans inserer_element ... vois tu ce que je veux dire ?

[pierre.kunzli]

Alors qu'une fois qu'un "placer" se fait sans scinder, faut pas refaire des placer plus haut dans l'arbre. Ou ça se fait par un autre moyen ?

[orestis.malaspin]

ah non mais je suis con comme un balais. il manque un

si est_dans_page(page, element.clef)
    retourne

dans placer. Ensuite je pense que c'est ok. Comme ça on modifie pas l'argument de placer. Tu en dis quoi?

[pierre.kunzli]

Baaa pas sur. Il y a des appels recursifs à inserer_element qui vont aboutir sur un placer. Dans ce placer, il se peut qu'on scinde et qu'on se retrouve avec un element.page != vide (élément promu). Il faut alors le placer après le retour de inserer_element. Mais pour les autres appels à inserer_element qui restent empilés ? il faut leur signaler qu'il ne faut pas faire de placer (element va pointer sur l'élément qui a été promu plus bas dans l'arbre).