#Animations interactivesCopier le lien

Chaque animation ci-dessous met en scène une structure ou un algorithme du module. Manipulez-les : le but est de voir la dynamique, pas seulement le résultat.

#Construction d'un arbre binaire de rechercheCopier le lien

Cinq insertions successives de clés : à chaque nœud rencontré, on descend à gauche si la clé est plus petite, à droite si elle est plus grande. Observez le chemin de 1 : il traverse 5 puis 3 avant de trouver sa place.

Invariant de la construction : à tout moment, pour chaque nœud de valeur v, toutes les clés de son sous-arbre gauche sont inférieures à v et toutes les clés de son sous-arbre droit sont supérieures. C'est cette propriété, pas la forme de l'arbre, qui permet la recherche en O(log n) sur un arbre équilibré.

#Tri par insertionCopier le lien

Le tri par insertion construit une zone triée à gauche, une carte à la fois : il prend l'élément suivant et le fait glisser vers la gauche jusqu'à sa place.

Invariant : au début de l'itération i, la tranche t[:i+1] contient les i+1 premiers éléments du tableau initial, triés entre eux. À la sortie, la tranche couvre tout le tableau. Coût : O(n²) au pire cas (entrée triée en ordre inverse), O(n) sur une entrée déjà presque triée.

#Pile (LIFO)Copier le lien

Une pile retire toujours l'élément le plus récemment ajouté : Last In, First Out. C'est la structure des appels de fonctions et de l'annulation (Ctrl+Z).

Invariant : on ne retire jamais autre chose que le sommet. Les opérations push et pop sont O(1).

#File (FIFO)Copier le lien

Une file retire l'élément le plus anciennement ajouté : First In, First Out. C'est la structure des files d'attente et du parcours en largeur.

Invariant : l'ordre de sortie est exactement l'ordre d'entrée. Les opérations enqueue et dequeue sont O(1) avec la bonne implémentation (deque, pas liste).

#Comment utiliser ces animationsCopier le lien

Devinez l'état suivant avant de cliquer : formuler une prédiction, puis la confronter à l'animation, est ce qui ancre la compréhension. Cherchez ensuite les cas limites : que fait le tri par insertion sur un tableau déjà trié ? Que fait la pile quand on dépile plus qu'on n'empile ? Ces questions sont celles que vos tests poseront aussi.