Numérique et sciences informatiques (spécialité) · Terminale · Structures de données

Arbres et arbres binaires de recherche

• Un arbre binaire de recherche (ABR) est un arbre binaire dont les clés sont comparables : à gauche d'un nœud les clés plus petites, à droite les clés plus grandes .
• La recherche descend depuis la racine en comparant la clé cherchée à celle du nœud : à gauche si elle est plus petite, à droite si elle est plus grande .
• Un nouveau nœud est toujours inséré comme feuille ; la forme de l'arbre dépend de l'ordre des insertions .
• La suppression d'un nœud à deux enfants demande de le remplacer par son successeur (ou son prédécesseur) pour garder la propriété d'ABR .