Overblog Suivre ce blog
Editer l'article Administration Créer mon blog
cryptologie

cryptographie & cryptanalyse

Petit aperçu arbres binaires de recherches

Publié le 3 Février 2015 par Levy

Petit aperçu arbres binaires de recherches

La propriété d’arbre binaire de recherche permet d’afficher toutes les clés de l’arbre dans l’ordre trié à l’aide d’un algorithme récursif simple, appelé parcours infixe : la clé de la racine d’un sous-arbre est imprimée entre les clés du sous-arbre de gauche et les clés du sous-arbre de droite. (De même, un parcours préfixe imprimera la racine avant les valeurs de chacun de ses sous-arbres et un parcours postfixe imprimera la racine après les valeurs de ses sous-arbres.) Pour imprimer tous les éléments d’un arbre binaire de recherche T à l’aide de la procédure suivante, on appelle PARCOURS-INFIXE(racine[T]).

Parcours-Infixe
si x!=Null
alors Parcours-infixe(gauche[x])
afficher clé[x]
Parcours-Infixe(droite[x])

Requête dans un arbre binaire de recherche

Une opération très courante sur un arbre binaire de recherche est la recherche d’une clé stockée dans l’arbre. En dehors de l’opération RECHERCHER, les arbres binaires de recherche peuvent supporter des requêtes comme MINIMUM, MAXIMUM, SUCCESSEUR et PRÉDÉCESSEUR. Dans cette section, on examinera ces opérations et on montrera que chacune peut s’exécuter dans un temps O(h) sur un arbre binaire de recherche de hauteur h.

Recherche
On utilise la procédure suivante pour rechercher un noeud ayant une clé donnée dans
un arbre binaire de recherche. Étant donné un pointeur sur la racine de l’arbre et une
clé k, ARBRE-RECHERCHER retourne un pointeur sur un noeud de clé k s’il en existe
un ; sinon, elle retourne NULL.
ARBRE-RECHERCHER(x, k)

si x = NULL ou k = clé[x]
alors retourner x
si k < clé[x]
alors retourner ARBRE-RECHERCHER(gauche[x], k)
sinon retourner ARBRE-RECHERCHER(droite[x], k)

Commenter cet article

video production orange county 25/02/2017 11:20

Thank you for your generosity in sharing so much of your knowledge.