---
title: "Barnes-Hut et B-arbres"
date: "2023-05-12"
---

# Le cours précédent

## A quoi sert l'algorithme de Barnes-Hut?

. . .

* A accélérer la résolution du problème à $n$-corps avec la gravitation,
* si on peut vivre avec une réduction de précision.

## Sur quelle structure de données se base l'algorithme?

* L'arbre quaternaire.

. . .

## Quelle est l'idée générale?

. . .

* Si un groupe d'étoiles est suffisamment loin, on le modélise comme un corps unique situé en son centre de masse.
* Exemple: Si on simule plusieurs galaxies, on considère chaque galaxie comme un corps unique!
* Un arbre quaternaire est une structure parfaite pour regrouper les étoiles.


# Le cas à 10 corps

::: columns

:::: {.column width=50%}

## Illustration: le cas à 10 corps

![](figs/nbody_bare.png){width=60%}

::::

:::: {.column width=50%}

## Problématique

* On veut calculer la force sur $1$.

::::

:::

. . .


::: columns

:::: {.column width=50%}

## Illustration: le cas à 10 corps

![](figs/nbody_n2.png){width=60%}


::::

:::: {.column width=50%}

## Résultat

* Calcul et somme des forces venant des $9$ autre corps.

::::

:::

# Le cas à 10 corps

::: columns

:::: {.column width=50%}

## Réduction d'un groupe à un seul corps

![](figs/nbody_group.png){width=100%}

::::

:::: {.column width=50%}

## Idée

* On accélère le calcul en traitant un groupe comme un seul corps.
* Fonctionne uniquement si le groupe est assez loin.
* Autrement l'approximation est trop grossière.

::::

:::

# Solution: l'arbre quaternaire

## Corps célestes - arbre

![](figs/nbody_qt_withtree.png)

* On omet les nœuds vides pour éviter la surcharge.
* La numérotation est:
    * 0: ID
    * 1: SD
    * 2: IG
    * 3: SG

# Exemple d'insertion

::: columns

:::: {.column width=50%}

## Insertion corps 1

![](figs/corps1.png){width=100%}

::::

:::: {.column width=50%}

## Arbre, niveau 1

![](figs/arbre1.png){width=100%}

* Quadrant ID.
* La feuille est vide, on insère.

::::

:::

# Exemple d'insertion

::: columns

:::: {.column width=50%}

## Insertion corps 2

![](figs/corps2.png){width=100%}

::::

:::: {.column width=50%}

## Arbre, niveau 1

![](figs/arbre2.png){width=100%}

* Quadrant SD.
* La feuille est vide, on insère.

::::

:::

# Exemple d'insertion

::: columns

:::: {.column width=50%}

## Insertion corps 3 (1/N)

![](figs/corps3_1.png){width=100%}

::::

:::: {.column width=50%}

## Arbre, niveau 1

![](figs/arbre3_1.png){width=100%}

* Quadrant SD.
* La feuille est prise par 2.

::::

:::

# Exemple d'insertion

::: columns

:::: {.column width=50%}

## Insertion corps 3 (2/N)

![](figs/corps3_2.png){width=100%}

::::

:::: {.column width=50%}

## Arbre, niveau 2

![](figs/arbre3_2.png){width=100%}

* On crée un nouveau nœud.
* Deux corps dans le nœud ID.
* On crée un nouveau nœud.

::::

:::

# Exemple d'insertion

::: columns

:::: {.column width=50%}

## Insertion corps 3 (3/N)

![](figs/corps3_3.png){width=100%}

::::

:::: {.column width=50%}

## Arbre, niveau 3

![](figs/arbre3_3.png){width=100%}

* 2 va dans ID.
* 3 va dans SG.
* C'est des feuilles vides, tout va bien.

::::

:::

# Exemple d'insertion

::: columns

:::: {.column width=50%}

## Que fait-on avec les nœuds intérieurs?

* On les utilise pour:
    * stocker la masse totale;
    * stocker le centre de masse.

\begin{align}
m&=m_2+m_3,\\
\vec x &= \frac{m_2\vec x_2+m_3\vec x_3}{m}.
\end{align}

## Chaque feuille contient **une étoile**

::::

:::: {.column width=50%}

## Arbre

![](figs/arbre3_3.png){width=100%}

::::

:::

# Résumé

* Insertion du corps `c` dans le nœud `n` en partant de la racine.
* Si le nœud `n`
    * ne contient pas de corps, on y dépose `c`,
    * est interne, on met à jour masse et centre de masse. `c` est inséré récursivement dans le bon quadrant.
    * est externe, on subdivise `n`, on met à jour la masse et centre de masse, on insère récursivement les deux nœuds dans les quadrants appropriés.

## Remarque

* Il faut stocker les coordonnées des quadrants.
* Un nœud a un comportement différent s'il est interne ou externe.

# Algorithme d'insertion

## Structure de données

```C
struct node
    etoile e // externe: pour stocker 
    etoile sup_etoile // interne: pour stocker m, x
    quadrant q  // coordonnées du quadrant
    node enfants[4]
```

## Remarque: 

* On fait une simplification "moche": `sup_etoile` pourrait juste avoir une masse et une position.

# Algorithme d'insertion

\footnotesize

## Algorithme d'insertion, pseudo-code (15min, matrix)

. . .

```C
rien insertion_etoile(arbre, e)  
    si (!est_vide(arbre) && dans_le_quadrant(arbre.q, e.x)) {
        si (est_feuille(arbre))
            si (!contient_etoile(arbre))
                arbre.e = e
            sinon
                // on crée enfants et arbre.sup_etoile est initialisée
                subdivision_arbre(arbre, e) 
                pour enfant dans arbre.enfants
                    insertion_etoile(enfant, arbre.e)
                pour enfant dans arbre.enfants
                    insertion_etoile(enfant, e)
                destruction(arbre.e)
        sinon
            maj_masse_cdm(arbre.sup_etoile, e)
            pour enfant dans arbre.enfants
                insertion_etoile(enfant, e)
```

# Utilisation de l'arbre

* L'arbre est rempli: comment on calcule la force sur le corps 1?
* Parcours de l'arbre: 
    * si la distance entre 1 et le centre de masse est suffisante, on utilise la masse totale et centre de masse pour calculer la force.
    * sinon, on continue le parcours

# Calcul de la force

## Calcul de la force sur `1`

![](figs/force_1.png)

* Le cadrant ID ne contient que `1`, rien à faire.

# Calcul de la force

## Calcul de la force sur `1`

![](figs/force_2.png)

* Le cadrant SG ne contient `5` corps.

# Calcul de la force

## Calcul de la force sur `1`

![](figs/force_3.png)

* La distance entre `1` et le centre de masse de SG est `d`.

# Calcul de la force

## Calcul de la force sur `1`

![](figs/force_4.png)

* La distance entre `1` et le centre de masse de SG est `d`.
* Est-ce que `d` est assez grand?
* On va comparer avec la distance `d` avec la taille du quadrant `s`.

# Critère $\theta$

* On compare $d=||\vec x_1-\vec x_{cm}||$ avec $s$ la taille du quadrant.
* Le domain est assez éloigné si

    $$
    \frac{s}{d}<\theta,
    $$
* $\theta$ est la valeur de seuil.
* Une valeur typique est $\theta=0.5$, donc la condition devient

    $$
    d>2s.
    $$

# Calcul de la force

## Calcul de la force sur `1`

![](figs/force_4.png)

* Ici $d<2s$, domaine rejeté.
* ON descend dans l'arbre.

# Calcul de la force

## Calcul de la force sur `1`

![](figs/force_5.png)

* `s` est plus petit, mais....
* Cela ne suffit pas $d<2s$, domaine rejeté.

# Calcul de la force

## Calcul de la force sur `1`

![](figs/force_6.png)

* Les nœuds sont des feuilles, on calcule la force.
* On ajoute la force qu'ils exercent sur `1`.

# Algorithme pour le calcul de la force

Pour calculer la force sur un corps `c`, on parcourt l'arbre en commençant par la racine:

* Si le nœud `n` est une feuille et n'est pas `c`, on ajoute la force dûe à `n` sur `c`;
* Sinon si $s/d<\theta$, on traite `n` comme une feuille et on ajoute la force dûe à `n` sur `c`;
* Sinon on continue sur les enfants récursivement.


## Continuons notre exemple précédent!

# Calcul de la force

## Calcul de la force sur `1`

![](figs/force_7.png)

* Il y a deux corps dans le quadrant vert.
* Quel est le critère pour remplacer les étoiles par leur centre de masse?

. . .

* Et oui! $d>2s$ on peut remplacer les étoiles par leur centre de masse!

# Algorithme du calcul de force

## Écrire le pseudo-code-code du calcul de la force

\footnotesize

```C
rien maj_force_sur_etoile(arbre, e, theta)
    si est_vide(arbre)
        retourne

    si est_feuille(arbre) && contient_etoile(arbre) && dans_le_quadrant(arbre.q, e.x)
        maj_force(e, arbre.e)
    sinon si noeud_assez_loin(arbre, e, theta)
        maj_force(e, arbre.sup_etoile)
    sinon
        pour enfant dans enfants
            maj_force_sur_etoile(enfant, e, theta)
```

# Les B-arbres

## Problématique

* Grands jeux de données (en 1970).
* Stockage dans un arbre, mais l'arbre tiens pas en mémoire.
* Regrouper les sous-arbres en **pages** qui tiennent en mémoire.

## Exemple

* 100 nœuds par page et l'arbre comporte $10^6$ nœuds:
    * Recherche B-arbre: $\log_{100}(10^6)=3$;
    * Recherche ABR: $\log_2(10^6)=20$.
* Si on doit lire depuis le disque: $10\mathrm{ms}$ par recherche+lecture:
    * $30\mathrm{ms}$ (lecture beaucoup plus rapide que recherche) vs $200\mathrm{ms}=0.2\mathrm{s}$.

## Remarques

* On sait pas ce que veut dire `B`: Bayer, Boeing, Balanced?
* Variante plus récente B+-arbres.

# Les B-arbres

## Illustration, arbre divisé en pages de 3 nœuds

![Arbre divisé en pages de 3 nœuds](figs/barbres_page3.png)

. . .

## Utilisation

* Bases de données (souvent très grandes donc sur le disque);
* Système de fichier.

# Les B-arbres

## Avantages

* Arbres moins profonds;
* Diminue les opération de rééquilibrage;
* Complexité toujours en $\log(N)$;

. . .

## Définition: 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.

# Les B-arbres

## Est-ce un B-arbre?

![B-arbre d'ordre 2.](figs/barbres_exemple.png)

. . .

## Oui!

* Dans chaque nœud les clés sont **triées**.
* Chaque page contient au plus $n$ nœuds: check;
* Chaque nœud avec $m$ clés a $m+1$ descendants;
* Toutes les feuilles apparaissent au même niveau.

# Les B-arbres

## Exemple de recherche: trouver `32`

![B-arbre d'ordre 2.](figs/barbres_exemple.png)
 
. . .

* 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

## Disclaimer

* Inspiration de <https://en.wikipedia.org/wiki/B-tree>

## Exemples d'insertion: `1`

![B-arbre d'ordre 1.](figs/barbres_1.svg)
 
. . .

* L'arbre est vide, on insère juste dans la première page.

# Les B-arbres

## Exemples d'insertion: `2`

![B-arbre d'ordre 1. Nombre pages max = 2.](figs/barbres_2.svg)
 
. . .

* La première page est pas pleine, on insère dans l'ordre (après 1).

# Les B-arbres

## Exemples d'insertion: `3`

![B-arbre d'ordre 1.](figs/barbres_2.svg){width=50%}

* Comment on insère (1min de réflexion avant de donner une réponse!)?

# Les B-arbres

## Exemples d'insertion: `3`

![B-arbre d'ordre 1. Nombre pages max = 2.](figs/barbres_3.svg){width=50%}
 
. . .

* La page est pleine, on crée deux enfants.
* On choisit, `2`, la médiane de `1, 2, 3` et il est inséré à la racine.
* `1` descend à gauche, `3` descend à droite.

# Les B-arbres

## Exemples d'insertion: `4`

![B-arbre d'ordre 1.](figs/barbres_3.svg){width=50%}
 
* Comment on insère (1min de réflexion avant de donner une réponse!)?

# Les B-arbres

## Exemples d'insertion: `4`

![B-arbre d'ordre 1. Nombre enfants 0 ou 2.](figs/barbres_4.svg){width=50%}
 
. . .

* On pourrait insérer à droite de `2`, mais... ça ferait 2 parents pour 2 enfants (mais `m` parents => `m+1` enfants ou `0`);
* On descend à droite (`4 > 2`);
* On insère à droite de `3`.

# Les B-arbres

## Exemples d'insertion: `5`

![B-arbre d'ordre 1.](figs/barbres_4.svg){width=50%}
 
* Comment on insère (1min de réflexion avant de donner une réponse!)?

# Les B-arbres

## Exemples d'insertion: `5`

![B-arbre d'ordre 1.](figs/barbres_5.svg)
 
. . .

* On descend à droite (on peut pas insérer à la racine comme pour `4`);
* On dépasse la capacité de l'enfant droite;
* `4`, médiane de `3, 4, 5`, remonte à la racine;
* On crée un nouveau nœud à droite de `4`;
* La règle `m => m+1` est ok.

# Les B-arbres

## Exemples d'insertion: `6`

![B-arbre d'ordre 1.](figs/barbres_5.svg){width=50%}
 
* Comment on insère (1min de réflexion avant de donner une réponse!)?

# Les B-arbres

## Exemples d'insertion: `6`

![B-arbre d'ordre 1.](figs/barbres_6.svg)
 
. . .

* `6 > 4` on descend à droite;
* `6 > 5` et on a à la place à droite, on insère.

# Les B-arbres

## Exemples d'insertion: `7`

![B-arbre d'ordre 1.](figs/barbres_6.svg){width=50%}
 
* Comment on insère (1min de réflexion avant de donner une réponse!)?

# Les B-arbres

## Exemples d'insertion: `7`

![B-arbre d'ordre 1.](figs/barbres_7.svg){width=50%}
 
. . .

* `7 > 4` on descend à droite;
* `7 > 6` mais on a dépassé la capacité;
* `6` est la médiane de `5, 6, 7`, remonte à la racine;
* `5` reste à gauche, `7` à droite, mais `6` fait dépasser la capacité de la racine;
* `4` est la médiane de `2, 4, 6`, `4` remonte, `2` reste à gauche, `6` à droite.

# 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, on sépare la page en son milieu :
    1. On trouve la médiane, `M`, de la page;
    2. On met les éléments `< M` dans la page de gauche de `M` et les `> M` dans la page de droite de `M`;
    3. `M` est insérée récursivement dans la page parent.

# Les B-arbres

## Exercice: insérer `22, 45, 50` dans l'arbre d'ordre 2 (3min matrix)

![](figs/barbres_ex1.png)

. . .

![](figs/barbres_ex2.png)


# Les B-arbres

## Exercice: insérer `5` dans l'arbre d'ordre 2 (3min matrix)

![](figs/barbres_ex2.png)

. . .

![](figs/barbres_ex3.png)

# Les B-arbres

## Exercice: insérer `32, 55, 60` dans l'arbre d'ordre 2 (3min matrix)

![](figs/barbres_ex3.png)

. . .

![](figs/barbres_ex4.png)

# Les B-arbres

## Exercice: insérer `41` dans l'arbre d'ordre 2 (3min matrix)

![](figs/barbres_ex4.png)

. . .

![](figs/barbres_ex5.png)

# Les B-arbres

## 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, 32, 41,
* Dans un B-arbre d'ordre 2.

