Aller au contenu

TNSI : Introduction aux Arbres⚓︎

Joke 😅⚓︎


Vous pensez que ça n'existe pas?

"Finalement, après des années de recherche,
j'ai trouvé un vrai Arbre" !

Exemples d'Utilisation des Arbres⚓︎

Arbre des Expressions Syntaxiques⚓︎

G--xx---x++---+33x--355x--522+--244+--4

Arbre 1 : Arbre des Expressions Arithmétiques

Les \(4\) opérations \(+, −, ×\) et \(\div\) sont des opérations binaires. Une expression ne comportant que ces symboles peut donc être représentée sous forme d'un arbre (binaire) comportant deux sortes de noeuds : les noeuds internes sont des opérations, les feuillles sont des nombres.

Dans un tel arbre, l'arrangement des noeuds joue le rôle des parenthèses auxquelles nous sommes habitués. Ici, l'arbre peut représenter l'opération \((3\times 5) - (2+4)\)

Arbre de Jeu⚓︎

Arbre 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)

Exemple 1 : Jeu de Nim⚓︎

G55445--43235--323134--312224--2223232--2315132--1521231--2112131--1211121--1102021--0213122--1305022--0514123--1407023--0701011--0103012--0304013--0406014--0608015--08

Arbre 2 : Arbre de Jeu (de Nim)

L'arbre ci-dessus modélise un jeu de Nim, dont on rappelle les Règles du Jeu :
On dispose de \(5\) allumettes. Chacun son tour, chaque joueur peut en prendre \(1\) ou \(2\). Celui qui prend la dernière allumette gagne.

L'état du jeu est totalement défini par le nombre d'allumettes à jouer restantes et le nom du prochain joueur à jouer.

  • Les (valeurs des) noeuds indiquent le nombre d'allumettes à jouer restantes,
  • la couleur de l'arête indique quel joueur doit jouer (Rouge ou Bleu). Le Rouge commence

Cet arbre montre que les deux joueurs ont chacun \(4\) possiblités de gagner, mais que le joueur Rouge a une stratégie gagnante car, s'il choisit bien ses coups, il est sûr de gagner sans que le joueur Bleu ne pourra empêcher.

Exemple 2: Jeu du Morpion (Algorithme MiniMax)⚓︎

Arbre 4 : Arbre de Jeu du Morpion (Algorithme MiniMax).
Dans un jeu où on ne retrouve pas deux fois la même position dans la même partie, le graphe des positions est sans cycle, donc c'est un arbre.

Dans cet exemple modélisant les positions du jeu de Morpion (Algorithme MiniMax) :

1⃣ On commence par étiqueter les feuilles, qui modélisent des parties finies, en convenant de coder le résultat final (Gain ou Utilité) :

  • +1 pour une victoire de X, et
  • −1 pour une défaite de X,
  • 0 pour un nul (égalité)

2⃣ À l'étage supérieur, on étiquette chaque noeud parent p (récursivement), en raisonnant comme suit :

  • Si le noeud parent correspond au tour de X (ou Joueur Max), le (minimax du) noeud parent vaut le maximum des valeurs (minimax) des noeuds enfants
  • Si le noeud parent correspond au tour de O (ou Joueur Min), le (minimax du) noeud parent vaut le minimum des valeurs (minimax) des noeuds enfants

3⃣ Stratégies de Jeu À chaque tour, la meilleure stratégie de jeu:

  • pour le jour Max (X), consiste à choisir le Max des noeuds enfants
  • pour le jour Min (O), consiste à choisir le Min des noeuds enfants

4⃣ On peut prouver qu'il y a match nul pour deux joueurs qui ont la meilleure stratégie.

Arbre Syntaxique de Code⚓︎

CodeiiRangeRange33Range--3Body2BodyAssign2AssignBody2--Assign2a2aBody1BodyAssign1AssignBody1--Assign1ForForBody1--ForPrintPrintBody1--Printa1aAssign1--a122Assign1--2Assign2--a2\*Assign2--\</em>For--iFor--RangeFor--Body2a4aPrint--a4a3a\<em>--a355\</em>--5

Arbre 3 : Arbre Syntaxique du code ci-dessous ...

a = 2
for i in range(3):
  a = a * 5
print(a)

Comme tous les langages de programmation, Python dispose d'une grammaire qui indique comment former des programmes corrects du point de vue de la syntaxe, qu'il puisse comprendre. L'interpréteur Python lit le code source puis construit l'arbre syntaxique du code. En simplifiant un peu, le code source précédent pourrait être représenté par l'arbre ci-dessus. Tous les traitements futurs du code seront faits à partir de cet arbre.

Tas⚓︎

Code10108810--842410--42558--5668--641422242--221142--121233v15--415--216--36--v1

Arbre 5 : Un Tas (ici un Tas-max)

Tas

Un Tas est un arbre "complet" (à gauche) dont chaque noeud est supérieur ou égal à chacun de ses enfants

Cette structure de données est utilisée dans deux situations classiques:

  • pour implémenter les Files de Priorité, car un tas permet de retirer efficacement l'élément de priorité maximale (resp. minimale)
  • pour implémenter le Tri par Tas : qui est un algorithme de tri efficace

Arbres Binaires de Recherche⚓︎

Code88338--310108--10113--1663--6v110--v1141410--14446--4776--7131314--13v214--v2

Arbre 6 : Arbre Binaire de Recherche (ABR)

ABR - Arbres Binaires de Recherche

Un Arbre Binaire de Recherche - ABR est un Arbre Binaire (chaque noeud admet un sous-arbre Gauche et un sous-arbre Droit) étiquetté avec des clés (=les valeurs des noeuds), pour lequel :

  • les clés du sous-arbre-gauche sont (toutes) inférieures ou égales à celles de la racine
  • les clés du sous-arbre-droit sont (toutes) supérieures ou égales à celles de la racine
  • les deux sous-arbres (Gauche et Droit) sont eux-mêmes des arbres Binaires de Recherche

Comme son nom l'indique, cette structure de données est utilisée pour rechercher efficacement un élément dans un arbre (Complexité en temps logarithmique lorsque l'arbre est dit bien équilibré)

Principal Intérêt des Arbres? (Spoiler) 🙈 🙊 🙉⚓︎

Dans les Listes / Piles / Files, la Recherche / l'Insertion / la Suppression d'un élément est proportionnel à la taille \(n\) de la Liste / Pile / File, donc en temps linéaire \(O(n)\)

Le principal intérêt des arbres est la complexité de leurs opérations:

  • Pour un arbre quelconque:
    • La Recherche d'un élément admet une complexité en temps en \(O(h)\), où \(h\) désigne la hauteur de l'arbre.
    • L'Insertion d'un élément admet une complexité en temps en \(O(h)\), où \(h\) désigne la hauteur de l'arbre.
    • La Suppression d'un élément admet une complexité en temps en \(O(h)\), où \(h\) désigne la hauteur de l'arbre.
      Cela peut sembler déjà intéressant, mais il existe des cas dégénérés le rendant moins intéressant. Néanmoins :
  • Si de plus on choisit l'arbre de sorte qu'il soit bien équilibré (en un certain sens à préciser), Alors la hauteur \(h\) sera logarithmique : \(h= O(\log_2(n))\).
    Par conséquent, la Recherche/Insertion/Suppression d'un élément dans un Arbre équilibré sera en temps logarithmique \(O(\log_2(n))\)