Programmation algorithmique/Arbres

Un livre de Wikilivres.
Sauter à la navigation Sauter à la recherche
Ébauche

Cette page est considérée comme une ébauche à compléter. Si vous possédez quelques connaissances sur le sujet, vous pouvez les partager en éditant dès à présent cette page (en cliquant sur le lien « modifier »).

Ressources suggérées : Aucune (vous pouvez indiquer les ressources que vous suggérez qui pourraient aider d'autres personnes à compléter cette page dans le paramètre « ressources » du modèle? engendrant ce cadre)

Algorithmique
Algorithmique
Sommaire
Modifier ce modèle


Un arbre est une structure de données hiérarchique sans cycle.

Principes[modifier | modifier le wikicode]

Un arbre est constitué de nœuds. Chaque nœud contient lui-même un ensemble de nœuds "fils" (tableau ou liste selon l'implémentation).

Le premier nœud sans père, père de tous les autres est nommé "racine de l'arbre". Généralement, seul le nœud père est conservé dans une variable, car on peut obtenir les autres nœuds en parcourant l'arbre.

Il existe 2 méthodes classiques de parcours d'arbre :

  • Parcours en Profondeur, on part de la racine et on descends jusqu'à une première feuille avant de passer aux nœuds suivant puis remonter. Dans cette représentation, les feuilles apparaissent aux côtés de leur arborescence.
  • Parcours en Largeur, les élément du niveau courant sont traités puis on passe aux éléments du niveau suivant.

Les parcours en largeur sont plus difficiles à réaliser car, en l'absence de liens entre les nœuds d'un même niveau dans la structure de données, on utilise généralement une file pour stocker temporairement les nœuds à traiter dans l'ordre approprié.

Intérêt[modifier | modifier le wikicode]

Certaines données présentent naturellement une structure d'arbre, par exemple les arbres de syntaxe dans un compilateur. Mais l'usage des arbres ne se limite pas à ces cas : ils sont notamment utilisés pour stocker des données de manière à accélérer leur temps d'accès par rapport au stockage dans un taleau ou dans une liste (complexité en temps logarithmique contre complexité en temps linéaire).

Le classement d'une série de données avec un arbre permet des recherches en log(N) si l'arbre est trié et « équilibré » (si dans tout l'arbre, pour 2 branches voisines, on a soit une longueur égale, soit une différence de longueur de 1 au maximum).

Il existe des algorithmes peu coûteux pour garder un arbre « équilibré » sur insertion ou suppression d'un élément.


Exemple :

Si chaque nœud a 2 fils, un arbre équilibré de 63 éléments aura une profondeur de seulement 6 :

  • 1er niveau = 1 nœud racine
  • 2e niveau = 2 nœuds
  • 3e niveau = 4 nœuds
  • 6e niveau = 32 nœuds

Une recherche d'un élément se fera donc bien en 6 tests, et

.

Algorithmes[modifier | modifier le wikicode]

Arbres binaires quelconques[modifier | modifier le wikicode]

Parcours en profondeur[modifier | modifier le wikicode]

Parcours préfixe[modifier | modifier le wikicode]

fonction prefixe( A: noeud)

si A‡nil /* condition */

traitement (A.¨info) /* afficher l'information contenue dans le noeud*/

prefixe (A.sag) /* Parcours préfixe sur le sous arbre gauche */

prefixe (A.sad) /* Parcours préfixe sur le sous arbre droit */

fin si

fin

Parcours infixe[modifier | modifier le wikicode]

Parcours en largeur[modifier | modifier le wikicode]

Arbres de recherche (triés)[modifier | modifier le wikicode]

Arbres de recherche équilibrés[modifier | modifier le wikicode]