Structures de données avancées

1. La pile suit le principe LIFO (Last In, First Out) : le dernier élément ajouté est le premier à sortir.
2. La file suit le principe FIFO (First In, First Out) : le premier élément ajouté est le premier à sortir.

💡 À retenir : Pile = assiettes empilées ; File = file d'attente à la caisse.

1. Si tu as une boucle de $n$ itérations contenant une autre boucle de $n$ itérations, la complexité est $O(n \times n) = O(n^2)$.
2. Si les boucles sont successives, on additionne : $O(n + n) = O(n)$.

💡 À retenir : Les boucles imbriquées multiplient la complexité, les boucles successives l'additionnent.

Oui, tout à fait. Il suffit d'insérer et de supprimer toujours au niveau de la tête de la liste. Cela garantit une complexité en $O(1)$ pour les deux opérations.

💡 À retenir : La liste chaînée est une structure flexible pour simuler d'autres structures.

L'ABR permet de chercher, insérer ou supprimer un élément très rapidement. En moyenne, la complexité est de $O(\log n)$ au lieu de $O(n)$ pour une liste simple.

💡 À retenir : L'ABR est idéal pour les recherches rapides.

Dans une implémentation par tableau, on vérifie si l'indice du sommet est égal à taille_max - 1. Si c'est une liste chaînée, elle est rarement "pleine" sauf si la mémoire vive est saturée.

💡 À retenir : La condition de débordement dépend de la structure sous-jacente.

1. Parcourir le sous-arbre gauche.
2. Traiter le nœud racine.
3. Parcourir le sous-arbre droit.

💡 À retenir : Infixe = Gauche -> Racine -> Droite.

Les pointeurs permettent de lier les éléments entre eux sans avoir besoin d'un espace mémoire contigu, contrairement aux tableaux. Cela facilite l'insertion et la suppression.

💡 À retenir : Les pointeurs offrent une gestion dynamique de la mémoire.

Un nœud feuille est un nœud qui n'a aucun enfant (ni à gauche, ni à droite).

💡 À retenir : Une feuille est la terminaison d'une branche.

Non. La récursivité est élégante mais peut causer un "stack overflow" (débordement de pile) si la profondeur est trop grande. Une boucle est souvent plus performante en mémoire.

💡 À retenir : Utilisez la récursivité pour la lisibilité, les boucles pour la performance.

1. Trouver le nœud précédent celui à supprimer.
2. Faire pointer le suivant du précédent vers le suivant du nœud à supprimer.
3. Libérer la mémoire du nœud supprimé.

💡 À retenir : Il faut toujours garder une référence sur le nœud précédent.

C'est $O(n)$ car il faut parcourir la liste nœud par nœud depuis le début pour atteindre l'index souhaité.

💡 À retenir : Contrairement au tableau, l'accès direct n'existe pas en liste chaînée.

Parce que le premier élément qui entre dans la file est le premier à être traité, comme dans une file d'attente réelle.

💡 À retenir : FIFO = First In, First Out.