Structures de données : Arbres binaires et Arbres binaires de recherche

Un arbre binaire est dit complet si tous les niveaux sont entièrement remplis, à l'exception éventuellement du dernier niveau qui est rempli de gauche à droite.

💡 À retenir : Un arbre complet minimise la hauteur pour un nombre de nœuds donné.

Pour calculer la hauteur, on utilise la récursivité :

1. Si l'arbre est vide, la hauteur est 0.
2. Sinon, la hauteur est $1 + \max(\text{hauteur(gauche)}, \text{hauteur(droite)})$.

💡 À retenir : La hauteur dépend toujours du chemin le plus long vers une feuille.

La complexité est $O(h)$ où $h$ est la hauteur de l'arbre. Dans le meilleur des cas (arbre équilibré), $h = \log_2(n)$, donc $O(\log n)$. Dans le pire des cas (arbre filiforme), $h = n$, donc $O(n)$.

💡 À retenir : L'efficacité dépend de l'équilibre de l'arbre.

La différence est la règle de rangement : dans un ABR, les valeurs sont ordonnées (gauche < racine < droite), ce qui permet de faire des recherches rapides. Dans un arbre binaire simple, il n'y a aucune règle de positionnement.

💡 À retenir : L'ABR est optimisé pour la recherche.

Trois cas :

1. Nœud feuille : on le supprime simplement.
2. Nœud avec un seul fils : on remplace le nœud par son fils.
3. Nœud avec deux fils : on remplace la valeur par le successeur immédiat (le plus petit du sous-arbre droit) et on supprime ce successeur.

💡 À retenir : La suppression doit maintenir la propriété ABR.

C'est une fonction récursive :

1. Appel récursif sur le fils gauche.
2. Traitement (affichage) de la valeur du nœud courant.
3. Appel récursif sur le fils droit.

💡 À retenir : L'ordre est toujours Gauche -> Racine -> Droite.

Non, par définition, un arbre binaire possède une et une seule racine. Si vous avez plusieurs racines, vous avez une "forêt" d'arbres.

💡 À retenir : La racine est le point d'entrée unique.

Non, elle dépend de la structure de l'arbre. Si l'arbre est déjà très déséquilibré, l'insertion peut prendre $O(n)$.

💡 À retenir : L'insertion suit le même chemin que la recherche.

Oui, le parcours préfixe permet de reconstruire l'arbre à l'identique car il traite la racine avant ses fils, ce qui respecte la structure hiérarchique.

💡 À retenir : Préfixe = Racine en premier.

Parce qu'on peut ajouter ou supprimer des nœuds à tout moment sans avoir à redimensionner toute la structure comme dans un tableau statique.

💡 À retenir : Utilisation de pointeurs (ou références) en Python.

La taille maximale (nombre de nœuds) est $2^h - 1$.

💡 À retenir : C'est le cas d'un arbre binaire parfait.

Oui, notamment pour supprimer un arbre (libérer la mémoire) ou pour évaluer des expressions arithmétiques écrites en notation polonaise inverse.

💡 À retenir : Postfixe = Racine en dernier.