Structures de données hiérarchiques

Introduction : Structures de données hiérarchiques

• Les programmes traitent des données hiérarchiques, comme des ensembles avec leurs inclusions ou des systèmes de fichiers avec des répertoires.
• L'utilisation d'une structure arborescente améliore l'efficacité des algorithmes et permet la résolution de problèmes complexes.
• Les arbres constituent un exemple archétypique de structures de données définies par induction.
• Pour travailler avec des structures hiérarchiques, il faut disposer d'objets mathématiques permettant de les représenter, tels que les arbres.

Arbres binaires

• Un arbre est composé d'une racine et d'un certain nombre d'enfants, qui sont eux-mêmes des arbres.
• La définition inductive d'une structure de données guide l'écriture d'algorithmes et de preuves avec les arbres.
• L'ensemble des arbres binaires est formellement défini, cette définition étant plus simple que la définition générale d'arbres.

Définition 1 - Arbre binaire

• Soit ∑ un alphabet (un ensemble de symboles).

• A₂(Σ) représente l'ensemble des arbres binaires avec des étiquettes dans ∑, les objets qui sont soit l'arbre vide, soit un nœud N(x, e₀, e₁) avec x ∈ Σ et e₀, e₁ ∈ A₂(Σ).

• Les enfants d'un nœud sont e₀ et e₁.

• La définition d'arbre est auto-référente : les enfants d'un nœud sont eux-mêmes des arbres.

• Les arbres sont les objets construits en appliquant de façon répétée l'opération N à partir de l'arbre vide.

• L'ensemble A₂(Σ) contient l'arbre vide, et pour chaque paire d'arbres e₀, e₁ ∈ A₂(Σ) et chaque élément x ∈ Σ, un élément N(x, e₀, e₁).

• Ces deux opérations sont injectives et ont des images distinctes.

• A₂(Σ) est minimal pour l'inclusion : si A' ⊂ A₂(Σ) contient l'arbre vide et est clos par N, alors A' = A₂(Σ).

II.A. Rappel : principe d'induction pour les arbres binaires

• Le principe d'induction définit les propriétés et algorithmes sur les arbres.

Théorème 2 - Principe d'induction sur les arbres binaires

• Soit P une propriété dépendant d'un arbre binaire a ∈ A₂(Σ).
• Si P vérifie : P(•) et ∀x∈Σ, ∀e₀, e₁ ∈ A₂(Σ), P(e₀) ∧ P(e₁) ⇒ P(N(x, e₀, e₁)), alors ∀a ∈ A₂(Σ), P(a).
• La démonstration considère Ap = {a ∈ A₂(Σ) | P(a)}, un sous-ensemble de A₂(Σ) qui contient l'arbre vide et qui est clos par N, donc Ap = A₂(Σ).

Lemme 3 - Analyse d'un arbre

• Soit a ∈ A₂(Σ), soit a vaut l'arbre vide, soit il existe un unique triplet x ∈ Σ, e₀, e₁ ∈ A₂(Σ) tel que a = N(x, e₀, e₁).
• Avec l'alphabet Σ = {a, b}, l'arbre vide est un élément de A₂(Σ).
• Fa = N(a, •, •) et Fb = N(b, •, •) sont des feuilles, construites avec une seule application de l'opération N.
• L'opération N permet de construire de nouveaux arbres à partir des feuilles, tels que A₀ = N(a, Fa, •), A₁ = N(b, Fa, •) et A₂ = N(a, •, Fa).
• La représentation graphique d'un arbre est plus simple que de décrire sa construction.

II.B Vocabulaire des arbres

• Une feuille est un arbre de la forme N(x, •, •), avec tous les enfants vides.
• Un nœud d'un arbre est une position dans l'arbre, associé à un sous-arbre.
• La racine de l'arbre est le nœud associé à l'arbre entier.
• Un nœud interne est un nœud dont le sous-arbre associé n'est pas une feuille.
• La taille d'un arbre est le nombre de ses nœuds.
• Un chemin est une suite de nœuds, avec la racine comme premier élément et chaque élément étant un enfant du précédent.
• La profondeur d'un nœud est la longueur du chemin unique dont il est le dernier élément.
• La hauteur d'un arbre non vide est la profondeur de sa feuille la plus profonde, et la hauteur de l'arbre vide est -1.

III. Arbres d'arité quelconque

Définition 4 - Arbre

• Soit Σ un alphabet.
• A(Σ) est l'ensemble des arbres avec étiquettes dans Σ, soit un arbre vide, soit un nœud N(x, e₀, ..., ek), avec x ∈ Σ, k ∈ N, et pour i < k, ei ∈ A(Σ).
• Dans un arbre binaire, chaque nœud interne a deux enfants, mais en général, on utilise le concept d'arbre d'arité quelconque.

III.A. Induction pour les arbres généraux

• Comme les arbres binaires, les arbres d'arité quelconque ont un principe d'induction pour définir des fonctions et démontrer des propriétés.

Théorème 5 - Principe d'induction sur les arbres

• Soit P une propriété dépendant d'un arbre a ∈ A(Σ).
• Si P vérifie : P(•) et ∀x∈Σ, ∀k∈N*, ∀e₀, ..., ek−1 ∈ A(Σ), ∀0 ≤ i < k P(ei) ⇒ P(N(x, e₀, ..., ek−1)), alors ∀a ∈ A(Σ), P(a).
• La différence avec le principe d'induction sur les arbres binaires est que la propriété P doit être héréditaire pour des nœuds internes avec un nombre quelconque d'enfants.
• La définition de chemin, profondeur, racine, feuille et hauteur est la même que pour les arbres binaires.
• Le degré d'un nœud d'un arbre est le nombre de ses enfants.
• L'arité d'un arbre est le plus grand degré d'un de ses nœuds.

IV. Fonctions récursives sur les arbres

• Les arbres binaires ou non se prêtent particulièrement à l'écriture de fonctions récursives, et cela est garanti par le principe d'induction des arbres.

IV.A : Récursion sur les arbres binaires

type 'etiq arbre =
| ArbreVide
| Noeud of 'etiq * 'etiq arbre * 'etiq arbre;;

let feuille (etiquette: 'etiq) : 'etiq arbre_binaire =
Noeud { etiquette, ArbreVide, ArbreVide }

• Ce type a une définition inductive.
• Les fonctions calculant la taille d'un arbre binaire font une disjonction de cas afin de traiter les constructeurs :Noeud ou ArbreVide.

let rec taille a =
match a with
| ArbreVide -> 0
| Noeud (_, enf_g, enf_d) -> 1 + (taille enf_g) + (taille enf_d)

IV.B : Récursion sur les arbres d'arité quelconque

type 'etiq arbre_aq =
| ArbreAQVide
| NoeudAQ of 'etiq * ('etiq arbre) list

• L'arbre d'arité quelconque peuvent être représentés par ce type, où les enfants d'un nœud interne sont représentés par une liste. Manipuler ces arbres impliquent les fonction récursives.

(* renvoie la somme des éléments de 1 *)
let sum (1: int list): int = List.fold_left (+) 0

let rec taille (a: 'etiq arbre): int = match a with
| ArbreAQVide -> 0
| NoeudAQ (_, enfants) ->
begin
let tailles_enfants: int list = List.map taille enfants in
(sum tailles_enfants) + 1
end

IV.C. Implémentation de la récursivité

• L'exécution des fonctions récursives est primordiale pour utiliser des données arborescentes.
• Une exécution montre que l'algorithme satisfait bien les équations.

V. Parcours d'arbres

• Les algorithmes traitent chaque sommet d'un arbre successivement, réalisant un parcours d'arbre.
• La nature du parcours indique l'ordre de traitement des nœuds.

V.A. Parcours en profondeur

• Dans ce type de parcours, le traitement d'un sous-arbre est achevé avant de traiter les sommets en dehors de ce sous-arbre.

Définition 6 - Parcours en profondeur

• Dans tout arbre A, et pour tout sous-arbre a de A, le parcours en profondeur parcourt les sommets de a consécutivement.

• Un arbre binaire a trois types de parcours : préfixe, postfixe et infixe.

• préfixe : on traite la racine puis chaque enfant

• postfixe : on traite les enfants puis la racine

• infixe : on traite l'enfant gauche, puis la racine, puis l'enfant droit.

• Un parcours en profondeur est une fonction récursive: chaque appel permet de traiter les enfants.

(* parcours prof. prefixe avec traitement *)
let rec parcours_profondeur_prefixe (traitement: 'a -> unit) (arbre: 'a
arbre_binaire) =
match arbre with
| ArbreVide -> ()
| Noeud (x, e_g, e_d) ->
begin
traitement x;
parcours_profondeur_prefixe traitement e_g;
parcours_profondeur_prefixe traitement e_d
end

• Les arbres d'arité quelconque ont des parcours analogues.

type 'a arbre = Vide | Noeud of 'a * 'a arbre list

let rec parcours_postfixe traitement arbre =
match arbre with
| Vide -> ()
| Noeud (valeur, sous_arbres) ->
begin
List.iter (parcours_postixe traitement) sous_arbres;
traitement valeur;
end

• Une implémentation alternative peut utiliser la structure de file de OCaml.

V.B. Parcours en largeur

• Dans ce type de parcours, les nœuds de même profondeur sont visités consécutivement.

Définition 7 - Parcours en largeur

• Les nœuds de même profondeur sont visités consécutivement en largeur.

• L'implémentation itérative classique du parcours en largeur utilise Queue en OCaml.

let parcours_largeur_iter traitement a =
let file = Queue.create() in

Queue.push a file;
    while not (Queue.is_empty file) do
      match Queue.pop file with
      | ArbreVide -> ();
      | Noeud (x, g, d) ->
          begin
            traitement x;
            Queue.push g file ;
            Queue.push d file
          end
    done

• Le parcours récursif est plus subtile.

(* parcours largeur récursif d'un arbre binaire *)

let parcours_largeur (traitement: 'a -> unit) (arb: 'a arbre_bin): unit
=
let rec parcours_foret liste_arbres liste_enfants =
match liste_arbres with
| [] ->
begin
match liste_enfants with
| [] -> ()
| liste_enfants -> parcours_foret liste_enfants []
end
| ArbreVide:: suite -> parcours_foret suite liste_enfants
| Noeud(x, g, d):: suite ->
begin
traitement x;
parcours_foret suite (liste_enfants @ [g; d])
end
in
parcours_foret [arb] [];;

• La même chose peut s'appliquer aux arbres d'arité quelconque.

type 'a arbre = Vide | Noeud of 'a * 'a arbre list

let parcours_largeur traitement arbre =
let rec parcours_foret liste_arbres liste_enfants
match liste_arbres with
| [] ->
begin
match liste_enfants with
| [] -> ()
|  -> parcours_foret liste_enfants []
end
| Vide:: suite -> parcours_foret suite liste_enfants
| Noeud (x, enfants):: suite ->
begin
traitement x;
parcours_foret suite (liste_enfants @ enfants)
end
in
parcours_foret [arbre] []

• Afin optimiser la fonction, il faut éviter la concaténation de liste.

let parcours_largeur traitement arbre =
let rec aux todo =
match todo with
| [] -> ()
| ArbreVide:: suite -> aux suite
| Noeud (x, e_g, e_d):: suite ->
begin
traitement x;
aux (todo @ [e_g; e_d])
end
in
aux [arbre]

• La fonction n'est pas très efficace dans le per des cas et monter a O(n²).

VI. Implémentation des arbres en C

VI.A. Arbres binaires en C

typedef struct arbre {
  int val;
  struct arbre* e_g;
  struct arbre* e_d;
} arbre;

• L'arbre vide a les enfants vallant NULL.

arbre* make_bin_tree(int etiq, arbre* g, arbre* d)
{
  arbre a = malloc(sizeof(arbre));
  a->val = etiq;
  a->e_g = g;
  a->e_d = d;
  return a;
}

• Libérer un arbre se fait récursivement.

void free_tree (arbre* a)
{
  if (a != NULL) {
    free_tree(a->e_g);
    free_tree(a->e_d);
    free(a);
  }
}

• Des fonctions classiques fonctionnent similairement.

int hauteur(arbre* a)
{
  if (a == NULL) return -1;
  return 1 + max(hauteur(a->e_g), hauteur(a->e_d));
}

int taille (arbre* a)
{
  if (a == NULL) return 0;
  return 1 + taille(a->e_g) + taille(a->e_d);
}

bool est_feuille (arbre* a)
{
  if (a == NULL) return false;
  return a->e_g == NULL && a->e_d == NULL;
}

bool est_strict (arbre* a)
{
  if (a == NULL) return true;
  if (a->e_g == NULL && a->e_d == NULL)
    return true;
  if (a->e_g == NULL || a->e_d == NULL)
    return false;
  return est_strict(a->e_g) && est_strict(a->e_d);
}

bool est_dans_arbre(int valeur, arbre* a)
{
  if (a == NULL)
    return false;
  if (a->valeur == valeur)
    return true;
  return est_dans_arbre(valeur, a->gauche) ||
    est_dans_arbre(valeur, a->droite);
}

VI.B. Arbres généraux en C

typedef struct arbre_general {
  int valeur;
  struct arbre_general fils;
  struct arbre_general frere;
} arbre_general;

• On ajoute un pointeur vers lé ‹‹ père ›› dans des arbres afin d'implémenter des algos itératifs plus efficaces.

typedef struct arbre_avec_pere {
  int valeur;
  struct arbre_avec_pere* gauche;
  struct arbre_avec_pere* droit;
  struct arbre_avec_pere* pere;
} arbre_avec_pere;