Des interpréteurs aux jeux, en passant par des méthodes efficaces de stockage et de recherche, les arbres sont omniprésents en informatique. Nous passons ici en revue quelques-unes de leurs applications.
I. Tas binaire
Un tas binaire est un arbre binaire complet à gauche, tel que le nœud racine porte une donnée supérieure à celle de tous les autres nœuds et tel que ses deux sous-arbres soient aussi des tas. L’arbre est alors un tas-max.
Un tas-min a la même structure, mais chaque nœud porte une information plus petite que tous ses descendants.
La structure de tas binaire est utilisée : dans un algorithme de tri efficace, le tri par tas ; dans la gestion des files de priorité.
II. Arbres binaires de recherche
Un arbre binaire de recherche est un arbre binaire étiqueté avec des clés tel que :
- les clés du sous-arbre gauche sont inférieures ou égales à celle de la racine ;
- les clés du sous-arbre droit sont strictement supérieures à celle de la racine ;
- les deux sous-arbres sont eux-mêmes des arbres binaires de recherche.
À noter
L’égalité est ici possible pour le sous-arbre gauche (le sous-arbre droit a des clés strictement supérieures), mais on pourrait tout aussi bien permettre l’égalité plutôt du côté droit (mais pas des deux côtés).
Les arbres binaires de recherche permettent de rechercher un élément dans un arbre de n nœuds en temps Oh où h est la hauteur de l’arbre binaire de recherche. Si l’arbre est équilibré, on a h≈log2(n) et la recherche a une complexité en temps logarithmique. Attention ! Un arbre de recherche déséquilibré (comme le peigne) peut avoir une complexité seulement linéaire.
III. Arbres de jeu
Un arbre de jeu permet de représenter toutes les positions et tous les coups possibles d’un jeu à l’aide d’un arbre (pas forcément binaire).
Voici un exemple de jeu (famille des jeux de Nim) : on dispose 5 allumettes. Chacun son tour, chaque joueur peut en prendre une ou deux. Celui qui prend la dernière gagne.
L’état du jeu est complètement défini par le nombre d’allumettes restantes et le nom du prochain joueur à jouer.
Voici l’arbre représentant toutes les parties possibles. Les nœuds indiquent le nombre d’allumettes restantes, la couleur de l’arête correspond au joueur qui doit jouer (rouge ou bleu, c’est le rouge qui commence).
L’analyse de cet arbre montre que les deux joueurs ont chacun 4 possibilités de gagner, mais que le joueur rouge a une stratégie gagnante car, avec ses choix, il peut forcer l’arrivée sur un des deux nœuds marqués d’une croix, ce que le joueur bleu ne pourra pas empêcher.
IV. Arbres représentant des expressions arithmétiques
Les quatre opérations +, −, × et ÷ sont des opérations binaires. Une expression ne comportant que ces opérations peut être représentée sous forme d’arbre binaire comportant deux sortes de nœuds : les nœuds internes sont des opérateurs et les feuilles sont des nombres.
Dans un tel arbre, l’arrangement des nœuds joue le rôle des parenthèses auxquelles nous sommes habituées. Ainsi, l’arbre ci-contre représente l’expression 6×8−2+4.
V. Arbres syntaxiques
Comme tous les langages informatiques, Python dispose d’une grammaire qui indique comment former des programmes corrects. Lorsque l’interpréteur Python lit du code source, il construit tout d’abord l’arbre syntaxique du code. En simplifiant un peu, le code source suivant pourrait être représenté par l’arbre ci-contre. Tous les traitements subséquents du code sont faits à partir de cet arbre.
