Structures de données: Arbres

Arbres

• Les arbres sont des structures de données importantes et utilisées en informatique.
• Ils sont utilisés dans les arbres généalogiques, les arbres de classification et les arbres d'expression.
• Un arbre est un ensemble de nœuds reliés entre eux par des arêtes.
• Trois propriétés caractérisent les arbres enracinés :
  • Un nœud particulier est désigné comme racine.
  • Chaque nœud (autre que la racine) est relié à un nœud parent par une arête.
  • Un arbre est connexe (il existe un chemin entre chaque paire de nœuds).
  • Un arbre est sans cycle.
• Un nœud peut avoir 0 ou plusieurs fils.
• Chaque nœud a exactement un père (sauf la racine).

Définition récursive des arbres

• Un nœud unique est un arbre, où le nœud est la racine.
• Si r est un nouveau nœud, et T1, T2,…, Tk sont des arbres ayant pour racines r1, r2,…, rk respectivement, alors l'arbre avec r comme racine et r1, r2,…, rk comme fils est un arbre. Une arête est ajoutée entre r et chaque ri.

Propriétés d'un arbre

• Pour un arbre T à n sommets, il y a équivalence entre les propriétés suivantes :
  • T est un arbre
  • T est connexe, et la suppression d'une arête quelconque le rend non connexe.
  • T est acyclique à n - 1 arêtes.
  • T est acyclique, et l'ajout d'une arête quelconque le rend cyclique.

Chemins, ancêtres, descendants

• Les ancêtres d'un nœud sont les nœuds sur le chemin unique entre ce nœud et la racine.
• Le nœud d est un descendant de a si et seulement si a est un ancêtre de d.
• La longueur d'un chemin est le nombre d'arêtes qu'il contient.

Généalogie

• La racine est un ancêtre de tous les nœuds.
• Chaque nœud est un descendant de la racine.
• Les nœuds ayant le même parent sont appelés enfants.
• Un nœud n et tous ses descendants forment un sous-arbre.

Feuilles et nœuds intérieurs

• Une feuille est un nœud sans enfants.
• Un nœud intérieur est un nœud avec au moins un enfant.
• Chaque nœud de l'arbre est soit une feuille, soit un nœud intérieur.

Mesures sur les arbres

• La taille d'un arbre T (notée taille(T)) est le nombre de nœuds.
• Le nombre de feuilles est noté nf(T).
• La hauteur d'un nœud n (notée h(n)) est la longueur du chemin depuis la racine jusqu'à n.
• La hauteur d'un arbre T (notée h(T)) est la plus grande hauteur parmi les nœuds de l'arbre.
• La hauteur moyenne d'un arbre T (notée HM(T)) est la moyenne des hauteurs de tous ses nœuds.
• La hauteur moyenne externe d'un arbre T (notée HME(T)) est la moyenne des longueurs de tous les chemins depuis la racine qui se terminent par une feuille.

Arbres binaires

• Tous les nœuds d'un arbre binaire ont 0, 1 ou 2 enfants.

• L'enfant gauche d'un nœud n est la racine du sous-arbre gauche de n.

• L'enfant droit d'un nœud n est la racine du sous-arbre droit de n.

• Le bord gauche d'un arbre est le chemin qui part de la racine et ne traverse que des fils gauche.

• Le bord droit d'un arbre est le chemin qui part de la racine et ne traverse que des fils droit.

Exemples d'arbres binaires particuliers

• Arbre binaire filiforme :
  • Un seul nœud à la hauteur 0.
  • Deux nœuds à la hauteur 1.
  • Quatre nœuds à la hauteur 2.
  • ...
  • 2^h nœuds à la hauteur h.
  • Nombre total de nœuds dans un arbre de hauteur h : 2^h+1-1.
• Arbre binaire parfait :
  • Tous les niveaux sont remplis sauf le dernier.
  • Les feuilles sont les plus à gauche possible.
• Arbre binaire localement complet :
  • Chaque nœud a 0 ou 2 enfants.

Propriétés sur les arbres

• h(T) ≤ taille(T) – 1 ; Egalité obtenue pour un arbre filiforme.
• Pour tout arbre binaire T de taille n et de hauteur h : log₂n ≤ h ≤ n - 1.
• Tout arbre binaire non vide T ayant f feuilles a une hauteur h(T) supérieure ou égale à [log₂f].
• Un arbre binaire localement complet ayant n nœuds internes a (n + 1) feuilles.

Exploration d'arbres

• Pas aussi simple que dans le cas des listes.
• Pas d'ordre naturel.
• Deux types de parcours :
  • En largeur d'abord.
  • En profondeur d'abord.

Parcours en largeur d'abord

• L'ordre d'évaluation des noeuds est donné par les différents niveaux des noeuds (Niveau 1, Niveau 2,...).

Type de données

• Une structure de données chaînée est mise en œuvre pour représenter un nœud d'arbre.

Parcours en profondeur d'abord

• L'ordre d'évaluation des nœuds dépend de la méthode de parcours (préfixe, infixe, post fixe).

Visite de chaque noeud

• Les différents types de parcours (préfixe, infixe, post fixe) dépendent de l'ordre de traitement des nœuds.

Algorithmes pour les parcours d'arbre binaire

• Algorithmes pour l'implémentation des différents parcours d'arbre (préfixe, infixe, post fixe). L'idée générale consiste à visiter un nœud, puis ses sous-arbres gauche et droit, suivant un ordre basé sur la position du nœud.