cours_23.md

title: "B-Arbres"
date: "2022-04-13"
patat:
  eval:
    tai:
      command: fish
      fragment: false
      replace: true
    ccc:
      command: fish
      fragment: false
      replace: true
  images:
    backend: auto

Rappel: Les B-arbres

Pourquoi utiliser un B-arbre?

. . .

À quoi ressemble un B-arbre?

. . .

Qu'est-ce qu'un B-arbre d'ordre

$n$

• Chaque page d'un arbre contient au plus
  $2\cdot n$
  clés;
• Chaque page (excepté la racine) contient au moins
  $n$
  clés;
• Chaque page qui contient
  $m$
  clés contient soit:
  • $0$
    descendants;
  • $m+1$
    descendants.
• Toutes les pages terminales apparaissent au même niveau.

Rappel: Les B-arbres

Quelques propriétés

• Dans chaque noeud les clés sont triées.
• Chaque page contient au plus
  n
  noeuds: check;
• Chaque noeud avec
  m
  clés a
  m+1
  descendants;
• Toutes les feuilles apparaissent au même niveau.

Les B-arbres

Exemple de recherche: trouver 32

. . .

• Si n plus petit que la 1e clé ou plus grand que la dernière descendre.
• Sinon parcourir (par bissection ou séquentiellement) jusqu'à trouver ou descendre entre 2 éléments.

Les B-arbres

La recherche de la clé C algorithme

0. En partant de la racine.
1. Si on est dans une feuille:
   • Si la C est dans une page, retourner la page;
   • Sinon c'est perdu.
2. Sinon:
   • Tant que C > page passer à la page suivante
   • Descendre

Les B-arbres

Exercice: insérer 22, 45, 50, 5, 32, 55, 60, 41 dans l'arbre d'ordre 2

. . .

Les B-arbres

L'algorithme d'insertion

0. Rechercher la feuille (la page a aucun enfant) où insérer;
1. Si la page n'est pas pleine insérer dans l'ordre croissant.
2. Si la page est pleine:
   1. On décale les éléments plus grand que N;
   2. On insère N dans la place "vide";
   3. On trouve la valeur médiane M de la page (quel indice?);
   4. On crée une nouvelle page de droite;
   5. On copie les valeur à droite de M dans la nouvelle page;
   6. On promeut M dans la page du dessus;
   7. On connecte le pointeur de gauche de M et de droite de M avec l'ancienne et la nouvelle page respectivement.

Les B-arbres

Pseudo-code structure de données (3min, matrix)?

. . .

struct page
    entier ordre, nb
    element tab[2*ordre + 2]

struct element
    int clé
    page pg

Les B-arbres

\footnotesize

Les fonctions utilitaires (5min matrix)

booléen est_feuille(page)     // la page est elle une feuille?
entier position(page, valeur) // à quelle indice on insère?
booléen est_dans_page(page, valeur) // la valeur est dans la page

. . .

booléen est_feuille(page) 
    retourne (page.tab[0] == vide)
entier position(page, valeur)
    i = 0
    tant que i < page.nb && val >= page.tab[i]
        i += 1
    retourne i
booléen est_dans_page(page, valeur)
    i = position(page, valeur)
    retourne (i > 0 && page.tab[i] == valeur)

Les B-arbres

\footnotesize

Les fonctions utilitaires (5min matrix)

page nouvelle_page(ordre)  // creer une page
rien liberer_memoire(page) // liberer tout un arbre!

. . .

page nouvelle_page(ordre)
    page = allouer(page)
    page.ordre = ordre
    page.nb = 0
    page.tab = allouer(2*ordre+2)
    retourner page
rien liberer_memoire(page)
    si est_feuille(page)
        liberer(page.tab)
        liberer(page)
    sinon
        pour fille dans page.tab
            liberer_memoire(fille)
        liberer(page.tab)
        liberer(page)

Les B-arbres

Les fonctions (5min matrix)

page recherche(page, valeur) // retourner la page contenant
                             // la valeur ou vide 

. . .

page recherche(page, valeur)
    si est_dans_page(page, valeur)
        retourne page
    sinon si est_feuille(page) && !est_dans_page(page, valeur)
        retourne vide
    sinon
        recherche(page.tab[position(page, valeur)], valeur)

Les B-arbres

Les fonctions

page inserer(page, valeur) // inserer une valeur

. . .

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!
    retourne page

Les B-arbres

Les fonctions

rien inserer_element(page, element) // inserer un element et voir s'il remonte

. . .

rien inserer_element(page, element)
    si est_feuille(page)
        placer(page, element)
    sinon
        sous_page = page.tab[position(page, element)].page
        inserer_element(sous_page, element)
        si element.page != vide
            placer(page, element)

Les B-arbres

Les fonctions (5min matrix)

rien placer(page, element) // inserer un élément

. . .

rien placer(page, element)
    i = position(page, element.clé)
    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)

Les B-arbres

Les fonctions (5min matrix)

rien scinder(page, element) // casser une page et remonter

. . .

rien scinder(page, element)
    new_page = new_page(page.ordre)
    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.page = new_page

Les B-arbres

Les fonctions (5min matrix)

page ajouter_niveau(page, element) // si on remonte à la racine...
                                   // on doit créer une nouvelle 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].page = element.page
    retourne tmp

Les B-arbres: suppression

Cas simplissime

. . .