Cours 5 - Arbres binaires de recherche

name: inverse
layout: true
class: center, middle, inverse
---

# INFORMATIQUE 3 - CM 5
## Inès de Courchelle
## 2024-2025

![image](../img/CY-tech.png)

---
layout: false

# (Rappel) Arbre binaire
## Définition
Un arbre binaire est un arbre qui possède au maximum deux sous-arbres

---
# Problématique
## Les problèmes
1. Comment chercher un élément dans un arbre ?
2. Comment ajouter un élément dans un arbre ?

---
# Arbre binaire de recherche
## Plan
1. ABR - Définition
2. Les opérations
3. La complexité

---
# Arbre binaire de recherche
## Plan
1. .under[ABR - Définition]
2. Les opérations
3. La complexité

---
# Arbre binaire de recherche
## Définition
Un arbre binaire de recherche(ABR) est un arbre binaire dans lequel :
- les valeurs du sous arbre de gauche sont inférieur à la racine a
- les valeurs du sous arbre de droite sont supérieur à la racine a
- tout sous arbre de a est un ABR

## Exemple
<img src="img/differenceB-NB.png" width=400>

---
# Structure ABR
## En Algo
```c
STRUCTURE noeud
    val : entier
    filsG : noeud
    filsD : noeud
FIN STRUCTURE
```
## En C
```c
typedef struct noeud {
  int val;
  noeud* filsG;
  noeud* filsD;
}noeud;

typedef noeud* arbre;
```

---
# Arbre binaire de recherche
## Plan
1. ABR - Définition
2.  .under[Les opérations]
3. La complexité

---
# Créer un arbre
## En Algo
```c
Fonction creerArbreBinaire(val : entier, filsG,filsD : noeud) : noeud
VARIABLE
    a : noeud
DEBUT
    a.val <- val
    a.filsG <- filsG
    a.filsD <- filsD
    retourner a
FIN
```

## En C
```c
//Fonction creerArbreBinaire(valeur : entier, filsG: arbre, filsD : arbre) : arbre
arbre creerArbreBinaire (int val, arbre filsG, arbre filsD){
  arbre a = malloc(sizeof(noeud));
  a->val = val;
  a->filsG = filsG;
  a->filsD = filsD;
  return a;
}
```
---
# Les opérations
## let's go
1. Recherche
2. Insertion
3. Minimum
4. Maximum
5. Suppression

---
# La recherche
## Principes
- Comparaison avec la racine du noeud
  - S'il est inférieur, récursion dans le sous-arbre gauche
  - S'il est supérieur, récursion dans le sous-arbre droit
- Fin lorsque
  - La racine est égale à la valeur que l'on recherche
  - Le sous-arbre (gauche ou droit) n'existe plus, la valeur n'est pas dans l'arbre

## Objectifs
- Utiliser la recherche dichotomique
- Gagner en complexité (ne pas parcourir tous les noeuds de l'arbre)

---
# La recherche
## L'algo
```c
Fonction rechercheArbre (val : entier, a : arbre) : arbre
  SI estArbreVide(a) ALORS
    retourner a
  SINON
      SI a.val = val ALORS
        retourner a
      FIN SI
      SI val < a.val ALORS
        retourner rechercheArbre(val, a.filsG)
      SINON
        retourner rechercheArbre(val, a.filsD)
      FIN SI
FIN
```

---
# La recherche
## Illustration
Nous considérons l'arbre suivant :
<img src="img/abrExemple.png" width=300>

## Nous recherchons
<img src="img/valeurCherchee.png" width=50>

---
# La recherche
## Illustration
<img src="img/ABR-recherche1.png" width=400>

---
# La recherche
## Illustration
<img src="img/ABR-recherche2.png" width=450>

---
# La recherche
## Illustration
<img src="img/ABR-recherche3.png" width=450>

---
# La recherche
## Illustration
<img src="img/ABR-recherche4.png" width=600>

---
# La recherche
## Illustration
<img src="img/ABR-recherche5.png" width=500>

---
# La recherche
## Illustration
<img src="img/ABR-recherche6.png" width=500>

---
# La recherche
## Illustration
<img src="img/ABR-recherche7.png" width=700>

---
# L'insertion
## Principe
- L'élément est déjà dans l'arbre .arrow[] on ne l'ajoute pas
- On descend au bout de la branche concernée

---
# L'insertion
## L'algo
```c
Fonction insertionArbre (val : entier, a : arbre) : arbre
DEBUT
  SI estArbreVide(a) ALORS
    a <- creerArbreBinaire(val,NULL,NULL)
  SINON
    SI(val< a.val) ALORS
      a.filsG <-  insertionArbre(val,a.filsG)
    SINON
      a.filsD <- insertionArbre(val,a.filsD)
    FIN SI
  FIN SI
  retourner a
FIN
```

---
# L'insertion
## Illustration
<img src="img/ABR-insert1.svg" width=700>

---
# L'insertion
## Illustration
<img src="img/ABR-insert2.svg" width=700>

---
# L'insertion
## Illustration
<img src="img/ABR-insert3.svg" width=700>

---
# L'insertion
## Illustration
<img src="img/ABR-insert4.svg" width=700>

---
# L'insertion
## Illustration
<img src="img/ABR-insert5.svg" width=700>

---
# L'insertion
## Illustration
<img src="img/ABR-insert6.svg" width=700>

---
# L'insertion
## Illustration
<img src="img/ABR-insert8.svg" width=700>

---
# L'insertion
## Illustration
<img src="img/ABR-insert9.svg" width=700>

---
# L'insertion
## Illustration
<img src="img/ABR-insert10.svg" width=700>

---
# L'insertion
## Illustration
<img src="img/ABR-insert11.svg" width=700>

---
# L'insertion
## Illustration
<img src="img/ABR-insert12.svg" width=700>

---
# L'insertion
## Illustration
<img src="img/ABR-insert13.svg" width=700>

---
# L'insertion
## Illustration
<img src="img/ABR-insert14.svg" width=700>

---
# L'insertion
## Illustration
<img src="img/ABR-insert15.svg" width=700>

---
# L'insertion
## Illustration
<img src="img/ABR-insert16.svg" width=700>

---
# L'insertion
## Illustration
<img src="img/ABR-insert17.svg" width=700>

---
# L'insertion
## Illustration
<img src="https://c.tenor.com/EaiZyP9eR2kAAAAC/this-is-not-over-butters-stotch.gif" width=200>

---
# L'insertion
## Illustration
<img src="img/ABR-insert18.svg" width=700>

- Les appels récursifs de la fonction insertion arbre ne nous ont pas emmené jusqu'au retourner
- Il faut que l'on reconstruise l'arbre jusqu'au début sinon on l'aura perdu

---
# L'insertion
## Illustration
<img src="https://c.tenor.com/UBDLTMhiO6MAAAAC/cassette-player-tape.gif" width=450>

---
# L'insertion
## Illustration
<img src="img/ABR-insert19.svg" width=700>

---
# L'insertion
## Illustration
<img src="img/ABR-insert20.svg" width=700>

---
# L'insertion
## Illustration
<img src="img/ABR-insert21.svg" width=700>

---
# Le min
## Principe
On parcours l'arbre à gauche jusqu'à la dernière feuille  (la branche la plus à gauche de l'arbre).

## L'algo
```c
FONCTION minArbre (a : arbre) : entier
DEBUT
  SI a.filsG = NULL ALORS
    retourner a.val
  SINON
    retourner minArbre(a.filsG)
  FIN SI
FIN

```
---
# Le min
## Illustration
<img src="img/ABR-min1.svg" width=700>

---
# Le min
## Illustration
<img src="img/ABR-min2.svg" width=700>

---
# Le min
## Illustration
<img src="img/ABR-min3.svg" width=700>

---
# Le min
## Illustration
<img src="img/ABR-min4.svg" width=700>

Ensuite, il faut remonter le résultat dans les différents appels (comme d'hab)

---
# Le max
## Principe
On parcours l'arbre à droite jusqu'à la dernière feuille

## L'algo
```c
FONCTION maxArbre (a : arbre) : entier
DEBUT
  SI a.filsD = NULL
    retourner a.val
  SINON
    retourner maxArbre(a.filsD)
  FIN SI
FIN
```

---
# La suppression
## Principe
Supprimer un élément n'est pas immédiat car il ne faut pas compromettre la relation d'ordre sur les éléments dans l'arbre.
<img src="https://c.tenor.com/QufqbwXItD4AAAAC/theodoros.gif" width=50>

## Plusieurs cas
#### cas 1
Suppression d'un élément dans un noeud feuille

#### cas 2
Suppression d'un élément dans un noeud à un fils

#### cas 3
Suppression d'un élément dans un noeud à deux fils

---
# La suppression
## Cas 1 : la feuille
.pull-left[
- Le plus simple
- On supprime directement la feuille
]
.pull-right[
##### Valeur à supprimer :
<img src="img/valeurCherchee.png" width=50>
]

---
# La suppression
## Cas 1 : la feuille
.pull-left[
- Le plus simple
- On supprime directement la feuille
]
.pull-right[
##### Valeur à supprimer :
<img src="img/valeurCherchee.png" width=50>
]

---
# La suppression
## Cas 1 : la feuille

.pull-left[
- Le plus simple
- On supprime directement la feuille
]
.pull-right[
##### Valeur à supprimer :
<img src="img/valeurCherchee.png" width=50>
]

---
# La suppression
## Cas 2 : le fils unique
.pull-left[
On remplace le noeud par son fils
]
.pull-right[
##### Valeur à supprimer :
<img src="img/val18.svg" width=50>
]

---
# La suppression
## Cas 2 : le fils unique
.pull-left[
On remplace le noeud par son fils
]
.pull-right[
##### Valeur à supprimer :
<img src="img/val18.svg" width=50>
]

---
# La suppression
## Cas 2 : le fils unique
.pull-left[
On remplace le noeud par son fils
]
.pull-right[
##### Valeur à supprimer :
<img src="img/val18.svg" width=50>
]

---
# La suppression
## Cas 3 : la suppression d'un noeud à 2 fils
.pull-left[
Comment on fait ?
]
.pull-right[
##### Valeur à supprimer :
<img src="img/valeurCherchee19.png" width=50>
]

---
# La suppression
## Cas 3 : la suppression d'un noeud à 2 fils
.pull-left[
Il faut remplacer le noeud par son prédécesseur direct
]
.pull-right[
##### Valeur à supprimer :
<img src="img/valeurCherchee19.png" width=50>
]

---
# La suppression
## L'algo
```c
FONCTION supprArbre (val : entier, a : arbre) : arbre
VARIABLE
    max : entier
DEBUT
    SI estArbreVide(a) ALORS
        retourner a
    SINON SI (val > a.val) ALORS
        retourner creerArbreBinaire(a.val,a.filsG,supprArbre(val,a.filsD))
    SINON SI (val < a.val) ALORS
        retourner creerArbreBinaire(a.val,supprArbre(val,a.filsG),a.filsD)
    SINON
        max <- maxArbre(a.filsG)
        retourner creerArbreBinaire(max,supprArbre(max,a.filsG),a.filsD)
    FIN SI
FIN
```

---
# La suppression
## Illustration
<img src="img/ABR-suppression1.svg" width=500>

---
# La suppression
## Illustration
<img src="img/ABR-suppression2.svg" width=700>

---
# Les opérations
## Le résumé
.pull-left[
##### Fonctions
1. Recherche
2. Insertion
3. Minimum
4. Maximum
5. Suppression
]

.pull-right[
##### Objectifs
- Utiliser la récursivité
- Garder l'ordre de grandeur dans l'arbre binaire
- Comprendre les mécaniques de parcours d'un arbre
- Gagner en complexité
]

---
# Arbre binaire de recherche
## Plan
1. ABR - Définition
2.  Les opérations
3. .under[La complexité]

---
# La complexité
## Rappel
- Comparer et mesurer les performances d'algorithmes répondant à un même problème
- Réduire le temps d'exécution d'algorithme
- Utiliser au minimun la mémoire

---
# Les classes
## Appelation
.pull-left[
 \\[Ο(1) :  constante \\]
 \\[Ο(n) :  linéaire \\]
 \\[Ο(n log n) :  quasi-linéaire \\]
 \\[Ο(N^a) :  polynomiale \\]
 \\[Ο(e^n) :  exponentielle \\]
  \\[Ο(ln(n)) : complexité-logarithmique \\]
]

<br>

## En pratique
- Les algorithmes à complexité quasi-linéaire et en dessous sont très efficaces
- Avec données réduites, les algorithmes polynomiaux sont encore applicables
- Un algorithme à complexité exponentielle est inutilisable

---
# La représentation Graphique
## Illustration
<img src="img/classe_comp.png"  width=450/>

---
# La complexité
## Les opérations
.pull-left[
1. Recherche
2. Insertion
3. Minimum
4. Maximum
5. Suppression
]
.pull-right[

]

---
# La complexité
## Les opérations
.pull-left[
1. .under[Recherche]
2. Insertion
3. Minimum
4. Maximum
5. Suppression
].
.pull-right[
Le nombre d'appels dépend de la hauteur de l'arbre :
 \\[ meilleur : Ο(log_2(n)), arbre - equilibre - binaire \\]
 \\[ meilleur : Ο(log_3 (n)), arbre - equilibré - ternaire \\]
 - pire cas : Ο(n), si l'arbre est dégénéré
]
---
# Rappel
## Arbre équilibré
Un arbre est dit équilibré si, pour tous les nœuds, la différence entre la hauteur du sous-arbre gauche et du sous-arbre droit est inférieure à 1

## Arbre dégénéré
Un arbre binaire dégénéré est un arbre dans lequel tous les nœuds internes n'ont qu'un seul fils.

---
# La complexité
## Les opérations
.pull-left[
1. Recherche
2. .under[Insertion]
3. Minimum
4. Maximum
5. Suppression
]
.pull-right[
Le nbre d'appels dépend de la hauteur :
 \\[ meilleur : Ο(log_2(n)), arbre - equilibre - binaire \\]
 \\[ meilleur : Ο(log_3 (n)), arbre - equilibré - ternaire \\]
 - pire cas : Ο(n), si l'arbre est dégénéré
]

---
# La complexité
## Les opérations
.pull-left[
1. Recherche
2. Insertion
3. .under[Minimum]
4. Maximum
5. Suppression
]
.pull-right[
Le nbre d'appels dépend de la hauteur :
 \\[ meilleur : Ο(log_2(n)), arbre - equilibre - binaire \\]
 \\[ meilleur : Ο(log_3 (n)), arbre - equilibré - ternaire \\]
 - pire cas : Ο(n), si l'arbre est dégénéré
]

---
# La complexité
## Les opérations
.pull-left[
1. Recherche
2. Insertion
3. Minimum
4. .under[Maximum]
5. Suppression
]
.pull-right[
Le nbre d'appels dépend de la hauteur :
 \\[ meilleur : Ο(log_2(n)), arbre - equilibre - binaire \\]
 \\[ meilleur : Ο(log_3 (n)), arbre - equilibré - ternaire \\]
 - pire cas : Ο(n), si l'arbre est dégénéré
]

---
# La complexité
## Les opérations
.pull-left[
1. Recherche
2. Insertion
3. Minimum
4. Maximum
5. .under[Suppression]
]
.pull-right[
Le nbre d'appels dépend de la hauteur :
 \\[ meilleur : Ο(log_2(n)), arbre - equilibre - binaire \\]
 \\[ meilleur : Ο(log_3 (n)), arbre - equilibré - ternaire \\]
 - pire cas : Ο(n), si l'arbre est dégénéré
]

---
# Bilan
## Définition
..otro-blockquote[Les arbres binaires sont des cas particuliers d'arbre : dans un arbre binaire, on a au maximum 2 branches qui partent d'un élément. ]

## Objectifs
- Traiter de l'information efficacement
- Se familiariser avec des représentation de données non linéaire
- Manipuler des algorithmes de décisions

---
# Sitographie
## ABR
<a href="https://info.blaisepascal.fr/nsi-arbres-binaires-de-recherche" target="_blank">Info blaise pascal</a>
<a href="https://rmdiscala.developpez.com/cours/LesChapitres.html/Cours4/Chap4.7.htm#Degr%E9" target="_blank"> Rmdiscala </a>

<a href="https://www.delftstack.com/fr/tutorial/data-structure/binary-search-tree/" target="_blank"> Delftstack </a>

<a href="https://henri-garreta.developpez.com/tutoriels/algorithmique/cours-structure-donnee/?page=quelques-arbres-particuliers" target="_blank">Henri Garreta</a>

<a href="https://developpement-informatique.com/article/172/types-darbre-binaire" target="_blank"> Developpement-informatique </a>

<a href="http://nsi4noobs.fr/IMG/pdf/e1_tnsi_arbres_binaires.pdf" target="_blank"> nsi for noobs </a>

<a href="https://fr.wikipedia.org/wiki/Arbre_binaire_de_recherche" target="_blank"> wikipedia </a>