Un Arbre Binaire de Recherche (BST) est un type particulier d’arbre binaire qui présente deux propriétés :
Tous les nœuds enfants à gauche ont une valeur inférieure à celle de leur nœud parent.
Tous les nœuds enfants à droite ont une valeur supérieure à celle de leur nœud parent.
Ainsi, pour chaque nœud, soit il ne possède pas de nœud enfant, soit il a un nœud plus petit à gauche et un nœud plus grand à droite.
Un arbre binaire de recherche avec 8 nœuds
Cette propriété est particulièrement utile pour la recherche d’éléments dans un arbre binaire. Si nous cherchons une valeur x, nous savons toujours vers quel côté nous diriger. Dans l’exemple ci-dessus, pour trouver le nœud de valeur 3, nous examinons d’abord la racine, qui a pour valeur 5. Comme 5 est supérieur à 3, nous nous déplaçons vers la gauche. Nous examinons ensuite le nœud de valeur 2 et, comme 2 est inférieur à 3, nous allons vers la droite. Nous nous retrouvons alors sur le nœud de valeur 4 ; comme 4 est supérieur à 3, nous passons à gauche. Enfin, nous trouvons le nœud de valeur 3 : 3 est égal à 3, donc nous avons trouvé l’élément recherché.
# Suppose que les nœuds inexistants sont None au lieu d’avoir la valeur 0
def search(node: Node | None, x: int):
""" Retourne True si x est présent dans l’arbre, et False sinon """
if node is None: # Si nous sommes arrivés au bout de l’arbre
return False # Nous n’avons pas trouvé la valeur x
if x == node.value: # Si x est égal à node.value
return True # => nous avons trouvé la valeur x dans l’arbre
if x < node.value: # Si x est plus petit => aller à gauche
return search(node.left) # Essayer de trouver x dans le sous-arbre gauche
return search(node.right) # Sinon, essayer dans le sous-arbre droit
Cette méthode de recherche peut se révéler très efficace si la hauteur de l’arbre reste limitée. À chaque étape, on se déplace soit à gauche soit à droite, ce qui fait que la recherche dans cet arbre binaire de recherche correspond, dans le pire des cas, à un nombre d’opérations égal à la hauteur de l’arbre.
Défi : Vérifier si l’arbre fourni est un BST
Étant donné un arbre binaire, le but est de déterminer s’il s’agit bien d’un arbre binaire de recherche.
Entrée
L’entrée contient des entiers séparés par des espaces, correspondant aux valeurs des nœuds de l’arbre binaire. L’ordre des valeurs est donné en parcourant d’abord la branche gauche, puis la droite. Un 0 indique qu’aucun nœud n’existe à cet endroit. Il est garanti que l’arbre binaire fourni est valide et que les valeurs sont uniques.
Sortie
Le programme doit imprimer Yes si l’arbre binaire est effectivement un arbre binaire de recherche, et No dans le cas contraire.
Exemples
Entrée
Sortie
1 2 3 8 5 0 0 0 0 5 8 0 0 0 0
No
5 2 7 1 4 0 0 3 0 0 0 6 8 0 0 0 0
Yes
Explication
Exemple 1 : Même si tous les nœuds enfants à droite sont plus grands que leur nœud parent, certains enfants à gauche ne sont pas inférieurs à leur nœud parent.
Exemple 2 : C’est un arbre binaire de recherche, car tous les enfants à gauche ont une valeur inférieure à celle de leur parent, tandis que les enfants à droite ont une valeur supérieure à celle de leur parent.
.png?table=block&id=18a2c681-664d-81b4-aa65-f86e5282a0b8&cache=v2)
