Aller au contenu principal

Arbre

Description​

L'arbre binaire de recherche (binary search tree) est régulièrement utilisée pour effectuer des recherches :

  • Type : Recherche
  • Accès : Recherche et Parcours
  • Fonctionnalités : Ajouter (add), Rechercher (search), et Retirer (remove)

Implémentations​

Statique​

L'implémentation statique permet d'utiliser un arbre dont la capacité est fixe en mémoire centrale.

Arbre binaire de recherche

Dynamique​

L'implémentation dynamique permet d'utiliser un arbre dont la capacité est dynamique en mémoire centrale.

Ajouter​

Ajouter

Retirer​

Il y a deux cas lors d'un retrait dans un arbre binaire de recherche :

1. Une ou aucune branche​

Lorsque le noeud à retirer n'a qu’une seule ou aucune branche, il faut faire pointer la branche de son noeud parent vers son noeud enfant, puis libérer le noeud.

2. Deux branches​

Il n'est pas possible de simplement retirer un noeud qui a deux branches. Il faut remplacer sa donnée par la plus grande du sous-arbre de gauche ou la plus petite du sous-arbre de droite, et retirer le noeud comportant cette donnée.

Retirer

Parcours​

Un parcours (trajet en pointillé) consiste à récupérer (point noir) toutes les données d'un arbre dans un ordre précis.

Préfixe​

Pour chacun des noeuds :

  1. Ajouter la donnée au parcours.
  2. Aller vers la branche de gauche.
  3. Aller vers la branche de droite.

Préfixe

Résultat : F, B, A, D, C, E, G, I, H

Infixe​

Pour chacun des noeuds :

  1. Aller vers la branche de gauche.
  2. Ajouter la donnée au parcours.
  3. Aller vers la branche de droite.

Infixe

Résultat : A, B, C, D, E, F, G, H, I

Postfixe​

Pour chacun des noeuds :

  1. Aller vers la branche de gauche.
  2. Aller vers la branche de droite.
  3. Ajouter la donnée au parcours.

Postfixe

Résultat : A, C, E, D, B, H, I, G, F

Largeur​

Ajouter la donnée des noeuds :

  1. De haut en bas.
  2. De gauche à droite.

Largeur

Résultat : F, B, G, A, D, I, C, E, H