Algorithmique Avancée - Contrôle Continu

Une rotation dans un arbre AVL peut modifier la structure de l'arbre et le nombre de feuilles, mais conserve le nombre de racines, de nœuds et d'arêtes.

Une double rotation dans un arbre AVL implique la rotation de deux nœuds consécutifs, un nœud puis son fils, pour rééquilibrer l'arbre.

Un tas binaire (ou tas) est une structure de données optimale pour implémenter une file de priorité car il permet d'insérer et d'extraire des éléments avec la priorité maximale ou minimale en temps logarithmique.

Un arbre AVL est une structure de données idéale pour organiser des entiers, permettant d'ajouter, de supprimer et de trouver le plus petit entier supérieur à un donné en temps logarithmique.

La complexité d'une rotation à gauche à la racine d'un arbre AVL est constante, car elle ne nécessite que la modification d'un nombre limité de pointeurs.

Un arbre AVL de hauteur 3 contient au minimum 7 nœuds. Le nombre de nœuds minimum est calculé à l'aide d'une relation de récurrence.

L'insertion de clés dans un arbre AVL vide dans un ordre précis conduit à un arrangement spécifique des nœuds. La racine de l'arbre AVL après l'insertion de toutes les clés dépendra de cette séquence d'insertions.

Dans une table à adressage direct, l'accès aux éléments est direct et rapide, ce qui rend l'insertion, la recherche et la suppression d'éléments très efficaces.

Le parcours en ordre postfixe d'un tas-min H après l'insertion de 9 est : 35, 32, 12, 23, 20, 9, 10, 70, 21, 8, 5. L'élément 9 est intégré dans le tas en respectant la propriété du tas-min.

Un arbre binaire de hauteur h contient au maximum 2^h feuilles. Chaque niveau double le nombre de nœuds, et les feuilles se trouvent au dernier niveau.

La pire performance d'une recherche d'élément dans une table de hachage à adressage fermé est linéaire, O(n), car tous les éléments peuvent se trouver dans la même chaîne.

La pire performance d'une recherche d'élément dans une table de hachage à adressage ouvert est O(m), car, dans le pire des cas, la recherche peut parcourir tout le tableau.

La fonction affiche_impair(Arbre Bin Abr) en C affiche en ordre croissant tous les éléments impairs d'un arbre binaire de recherche Abr.

La fonction nbre_feuille(Arbre Bin Ab) en C retourne le nombre de feuilles d'un arbre binaire Ab.

Un arbre AVL est un arbre binaire de recherche auto-équilibré qui maintient un ordre sur les éléments. Il permet d'effectuer les opérations d'ajout, de suppression et de recherche en temps logarithmique dans le pire des cas.

Une rotation à gauche consiste à faire pivoter le sous-arbre droit d'un nœud vers la gauche, faisant du fils gauche du nœud la nouvelle racine.

Un tas-min est une structure de données où le nœud parent est toujours plus petit que ses enfants. La propriété du tas-min est maintenue à chaque insertion ou suppression.

Une table de hachage à adressage fermé (ou chaîné) stocke les éléments dans un tableau où chaque position peut contenir une liste ou une chaîne de collisions.

Une table de hachage à adressage ouvert stocke les éléments directement dans le tableau. Les collisions sont résolues en recherchant les positions suivantes jusqu'à trouver l'élément ou un emplacement vide.

Le parcours en largeur (ou niveau) d'un arbre parcourt les nœuds niveau par niveau, de la racine aux feuilles.

Le parcours en ordre postfixe d'un arbre parcourt les nœuds du sous-arbre gauche, puis du sous-arbre droit et enfin le nœud courant lui-même.

Un arbre binaire de recherche est un arbre binaire où les nœuds sont organisés de manière à ce que pour chaque nœud, tous les nœuds du sous-arbre gauche sont plus petits que le nœud courant et tous les nœuds du sous-arbre droit sont plus grands.

La complexité d'une opération représente le temps ou l'espace requis pour exécuter l'opération. Elle est généralement exprimée en fonction de la taille de l'entrée.

O(log n) signifie que la complexité de l'opération est logarithmique en fonction de la taille de l'entrée. La complexité augmente plus lentement que la taille de l'entrée.

O(n) signifie que la complexité de l'opération est linéaire en fonction de la taille de l'entrée. La complexité augmente proportionnellement à la taille de l'entrée.

O(1) signifie que la complexité de l'opération est constante, indépendamment de la taille de l'entrée. La complexité reste la même, quelle que soit la taille de l'entrée.

Le parcours en ordre croissant d'un arbre binaire de recherche affiche les nœuds dans l'ordre croissant de leurs valeurs.