- Un arbre binaire de recherche est un arbre binaire auquel on impose une contrainte pour chaque nœud:
- valeurs du sous-arbre gauche sont plus petites que celle du nœud,
- valeurs du sous-arbre droit sont plus grandes que celle du nœud.
À retenir
Dans un arbre binaire de recherche équilibré, la complexité temporelle de l’algorithme de recherche est logarithmique
def rechercher(val: int, abr: list, i_pere: int) -> bool:
if abr[i_pere] == 0: # non trouvé
return False
elif abr[i_pere] == val: # trouvé
return True
elif val < abr[i_pere]: # gauche
return rechercher(val, abr, 2*i_pere+1)
else: # droit
return rechercher(val, abr, 2*i_pere+2)