My IT Utilities

Arbre binaire de recherche (BST)

Partez d'un arbre binaire de recherche aléatoire et insérez, recherchez ou supprimez des valeurs pas à pas, avec sa forme en tableau et le code C++ mis en évidence.

Tout est simulé dans ce navigateur ; rien n'est envoyé à un serveur.

Aucune étape

Aucune étape

Arbre binaire de recherche

Indice du tableau

60[0]45[1]85[2]68[5]21[3]55[4]32[8]

Forme en tableau

Les enfants de l'indice i sont en 2i+1 et 2i+2.

  • Sans rapport
  • Déjà parcouru
  • En comparaison
  • Trouvé
  • Nouveau
  • À supprimer
  • Successeur

Aucune étape

Code

#include <iostream>
using namespace std;
class Node { // Un nœud contient sa valeur et des pointeurs vers ses deux enfants
private: // Attributs privés : seules les méthodes y touchent
int value;
Node* left;
Node* right;
public:
Node(int v) : value(v), left(nullptr), right(nullptr) {}
int getValue() const { return value; }
Node* getLeft() const { return left; }
Node* getRight() const { return right; }
void setValue(int v) { value = v; }
void setLeft(Node* n) { left = n; }
void setRight(Node* n) { right = n; }
};
Node* insert(Node* root, int v) { // Insère v dans l'arbre de recherche et renvoie la racine
if (root == nullptr) // Emplacement vide : le nouveau nœud va ici
return new Node(v); // Crée le nouveau nœud
if (v < root->getValue()) // Les valeurs plus petites vont à gauche et les plus grandes à droite
root->setLeft(insert(root->getLeft(), v)); // Descend dans le sous-arbre gauche
else
root->setRight(insert(root->getRight(), v)); // Descend dans le sous-arbre droit
return root;
}
int main() {
Node* root = buildTree(); // L'arbre affiché, déjà construit
root = insert(root, v); // Premier appel, depuis main
return 0; // Fin de l'opération
}

Cet outil part d'un arbre binaire de recherche (ABR) aléatoire et vous permet de le modifier à la main : saisissez une valeur de 1 à 99 et appuyez sur Insérer, Chercher ou Supprimer. Chaque opération est animée pas à pas sur l'arbre, avec des nœuds colorés selon leur rôle : en comparaison, déjà passé, nouveau, à supprimer ou successeur. En dessous, vous voyez le même arbre sous forme de tableau, avec les enfants de l'indice i en 2i+1 et 2i+2, et le code C++ surligne la ligne exécutée. Vous pouvez modifier la taille de 3 à 15 nœuds, générer un autre arbre et revenir à n'importe quelle étape. Tout est simulé dans votre navigateur.

Comment l'utiliser

  1. Réglez la taille de l'arbre avec le curseur ou appuyez sur Générer un nouvel arbre pour changer le point de départ.
  2. Saisissez une valeur de 1 à 99 et appuyez sur Insérer, Chercher ou Supprimer ; l'animation démarre toute seule.
  3. Avancez ou reculez avec les boutons d'étape précédente et suivante, ou appuyez sur Lecture et changez la vitesse.
  4. Observez les nœuds colorés, la forme tableau de l'arbre et la ligne de code C++ surlignée.

Questions fréquentes

Qu'est-ce qu'un arbre binaire de recherche et quelle propriété conserve-t-il ?
C'est un arbre binaire dans lequel chaque nœud a au plus deux enfants, toutes les valeurs du sous-arbre gauche étant inférieures à celle du nœud et toutes celles du sous-arbre droit supérieures. Grâce à cette propriété, on écarte la moitié du chemin restant à chaque comparaison.
Comment fonctionnent l'insertion et la recherche dans un ABR, et quel est leur coût ?
Toutes deux partent de la racine et comparent la valeur à chaque nœud : si elle est plus petite elles vont à gauche, si elle est plus grande, à droite. La recherche s'arrête quand la valeur est trouvée ou que nullptr est atteint ; l'insertion crée le nouveau nœud à cet emplacement vide. Leur coût est proportionnel à la hauteur de l'arbre : logarithmique s'il est équilibré et linéaire s'il forme une chaîne.
Quels sont les trois cas de suppression et pourquoi utilise-t-on le successeur infixe ?
Si le nœud est une feuille, il est simplement retiré ; s'il a un enfant, cet enfant prend sa place ; s'il en a deux, la valeur du successeur infixe, le plus petit du sous-arbre droit, y est copiée et le nœud du successeur est supprimé. Le successeur est la valeur suivante dans l'ordre, il s'insère donc à cet endroit sans casser la propriété de l'ABR, et comme il n'a pas d'enfant gauche, sa suppression relève des cas simples.
Comment un arbre est-il stocké dans un tableau et pourquoi y a-t-il des trous ?
En disposition de tas : la racine va à l'indice 0 et les enfants de l'indice i en 2i+1 et 2i+2. Si un nœud n'a pas d'enfant, cette position reste vide, et plus l'arbre est déséquilibré, plus il y a de trous, car les indices croissent avec la profondeur.

Outils associés