Algorithmes de recherche

Parallèlement au tri, l'autre opération courante en informatique est la recherche d'objets. Un algorithme de recherche consiste en une suite finie d'opérations permettant de retrouver la position d'un enregistrement dans un ensemble (souvent volumineux) de données précédemment récoltées. Le but d'une recherche est souvent d'accéder à l'information contenue dans l'enregistrement (et pas seulement à la position de ce dernier dans l'ensemble) pour permettre un traitement. Dans cette section, nous étudierons deux algorithmes de recherches élémentaires bien adaptés aux listes contenant peu d'éléments. Ces deux méthodes, appelées recherche séquentielle et recherche dichotomique, seront implémentées de manière itérative et récursive sur des listes d'entiers distincts.

Ces algorithmes s'appliquant à des listes statiques d'entiers ne permettant que difficilement l'insertion et la suppression de nouveaux éléments, la structure d'arbre binaire de recherche sera introduite afin de pallier à ce défaut.

Le déroulement des deux algorithmes de recherche qui seront étudiés dans cette section est présenté à l'adresse https://www.cs.usfca.edu/~galles/visualization/Search.html.

Table des matières

Cette section a pour but de décrire, comparer et d'implémenter les principaux algorithmes de recherche classiques. Les liens suivants permettent d'atteindre directement ses principales parties:

• Recherche séquentielle
• Recherche dichotomique
• Structure d'arbres
• Opérations sur les arbres
• Arbre binaire AVL

Objectifs

Au terme de cette section, chaque élève devra être capable de :

• décrire le déroulement des algorithmes de recherche séquentielle et dichotomique;
• calculer le nombre moyen de comparaisons nécessaires à la recherche séquentielle pour déterminer si un élément appartient ou n'appartient pas à une liste (triée ou non);
• calculer le nombre de comparaison maximale nécessaires à la recherche dichotomique pour déterminer si un élément appartient ou n'appartient pas à une liste triée;
• implémenter l'algorithmes de recherche séquentielle de manière itérative;
• implémenter l'algorithme de recherche dichotomique de manière itérative et récursive;
• caractériser la structure d'arbre binaire de recherche;
• décrire les opérations élémentaires sur les arbres binaires de recherche;
• implémenter la structure d'arbre binaire de recherche et ses différentes opérations;
• calculer le facteur d'équilibrage des noeuds d'un arbre AVL;
• rééquilibrer un arbre AVL après insertion ou suppression.

Présentation

Cette section est complétée d'une présentation faite en classe et accessible dans l'encadré ci-dessous: