Algorithmes sur les arbres

Les algorithmes sur les arbres sont principalement récursifs. Les trois parcours en profondeur d'un arbre binaire sont : préfixe (racine, gauche, droit), infixe (gauche, racine, droit) et suffixe (gauche, droit, racine). Par exemple, pour l'arbre de racine A avec fils B (gauche) et C (droit), le parcours préfixe donne A-B-C, l'infixe B-A-C et le suffixe B-C-A. Le parcours en largeur (BFS) visite les nœuds niveau par niveau en utilisant une file. Dans un ABR, la recherche compare la valeur cherchée à la racine et descend à gauche ou à droite : c'est une dichotomie sur l'arbre. L'insertion dans un ABR descend jusqu'à trouver un emplacement vide (None) et y crée un nouveau nœud. La complexité de ces opérations est O(h) où h est la hauteur de l'arbre, soit O(log n) pour un arbre équilibré.