Aller au contenu

TNSI : Arbres Quelconques⚓︎

Définition d'un Arbre : Arbre Enraciné vs Non Enraciné⚓︎

Arbres : Arbres enracinés vs non enracinés

  • un Arbre est constitué de noeuds / sommets et d'arêtes reliant certains de ces noeuds :
    Plus précisément : c'est un graphe connexe, acyclique (sans aucun cycle) et non orienté.

    • Chaque noeud peut être étiqueté par une information (selon les contextes : le nom du noeud, la valeur du noeud, etc..)
    • Chaque information est appelée une étiquette

  • un Arbre Enraciné (ou arborescence) est un arbre organisé de manière hiérarchique, càd dans lequel on a choisi un noeud particulier appelé la Racine. Dans toute la suite, par défaut, sauf mention contraire, tous les arbres considérés seront enracinés.

  • Un Arbre Non Enraciné est un arbre sans racine, càd dans lequel aucun noeud ne joue de rôle particulier.
    En particulier, un arbre non enraciné n'admet :

    • pas de relation hiérarchique,
    • pas de relation de descendance, etc..

  • une Forêt est la réunion de plusieurs Arbres disjoints

arbrecluster0Noeud Père de 79 et 67cluster1Noeuds fils de 687617667167761->6716565761->6576276FeuillesFeuilles762:se->Feuilles:n696969->76169->762686869->68racineNoeud'Racine'racine:sw->69:ne6726768->672797968->79671:se->Feuilles:n7373672->7365:se->Feuilles:n73:se->Feuilles:n79:se->Feuilles:n

Arbre Enraciné, étiqueté
par des nombres entiers
Gaabba--bddb--dccc--beed--effd--fgge--ghhe--hiif--ijjg--j
Arbre Non Enraciné

Exemple d'Arbre Non enraciné en Phylogénétique
La Phylogénie est la science s'intéressant à l'évolution des organismes vivants
Ici : Arbre Phylogénétique non enraciné, représentant les grands groupes d'Archée et le Phylum nanoarchaeota

Sous-Arbres⚓︎

Def

Un Sous-arbre A d'un arbre T est un arbre tel que:

  • Tous les sommets de A sont aussi des sommets de T
  • Toutes les arêtes de A sont aussi des arêtes de T

SousArbrecluster01cluster02Sous-Arbrecluster03Autre Sous-Arbre11221--2331--3441--4552--5663--6773--7884--8994--910105--1011115--1112127--1213137--1314147--1415158--1516168--16

Noeuds d'un arbre enraciné : Noeuds Externes/Feuilles vs Internes⚓︎

Def

Dans un arbre (enraciné):

  • Chaque noeud a exactement un seul noeud père, à l'exception de la racine qui n'a pas de père
  • Chaque noeud (père) peut avoir un nombre quelconque de (noeuds) fils (de \(0\) à l'\(\infty\))
  • Les noeuds qui n'ont pas de fils sont appelés les feuilles ou noeuds externes.
  • Les autres noeuds sont des noeuds internes (noeud interne = tout noeud qui n'est pas une feuille, càd tout noeud ayant des fils)
  • Des noeuds ayant le même père sont dits noeuds frères
  • Des noeuds reliés par une arête sont des noeuds adjacents.

Gcluster01Noeuds Frèrescluster02Feuillescluster03Noeuds Internescluster04Père de k, de l, et de mcluster05Les 3 Fils de irraar--abbr--bcca--cdda--deea--effb--fiic--ijjc--jooe--oppe--pkki--klli--lmmi--mqqk--quum--uttm--tssq--s

Noeuds Internes vs Noeuds Externes/Feuilles.
Noeud Père et Noeuds Fils.
Noeuds Frères

Arité d'un Noeud. Arbre N-aire. Arbre Binaire⚓︎

Def

  • l'Arité (quelquefois le degré) d'un noeud est son nombre de fils.
  • Un arbre \(N\)-aire ou arbre d'arité \(N\), est un arbre dont tous les noeuds ont une arité au plus égale à \(N\) \(\Leftrightarrow\) un arbre dont chaque noeud a au plus \(N\) fils
  • Un arbre Binaire est un arbre 2-aire, càd dont chaque noeud admet au plus \(2\) fils (ou enfants): classiquement appelés Fils Gauche et Fils Droit (ou enfant gauche et enfant droit)

Gcluster00arité 4cluster01arité 2cluster02arité 3cluster03arité 0aabba--bcca--cdda--deea--effb--fggb--ghhe--hiie--ijje--j

Arbre 4-aire

Exp

G11221--2331--3442--4552--5v33--v3883--8665--6775--7998--9v48--v4v1v2v5v6

Arbre Binaire (2-aire)

G11221--2331--3441--4552--5

Arbre 3-aire

G11221--2332--3772--7992--9443--4553--5663--6887--8

Arbre 3-aire

G11221--2331--3441--4552--5663--6773--7883--8993--910107--1011117--1112127--12

Arbre 4-aire

On pourrait penser naïvement qu'un arbre N-aire est une généralisation d'un arbre Binaire, en fait il n'en est rien (c'est ce qui explique, du moins partiellement, l'intérêt particulier porté aux Arbres Binaires par la suite)

Pte

Tout arbre \(N\)-aire peut être transformé/implémenté en arbre Binaire

Gaabba->ba->bcca->cdda->deea->effb->f    b->fb->c ggb->gf->gc->d d->e hhe->h    e->hiie->ijje->jh->ii->j
Arbre 4-aire
$$\Leftrightarrow$$
Gaabba->bv1a->v1ffb->fccb->cv2f->v2v3f->v3ggf->gv4c->v4ddc->dv5d->v5eed->ehhe->hv6e->v6v7h->v7iih->iv8i->v8jji->j
Arbre Binaire équivalent

Implémentation d'un Arbre N-aire en Arbre Binaire Lorsque \(N\) n'est pas fixe, ou tout simplement pour éviter les pertes de place, les arbres \(N\)-aires sont implémentés par des arbres Binaires : Chaque sommet comporte un pointeur vers son premier fils et vers son premier frère. Autrement dit :

  • le fils aîné d'un noeud n-aire père est implémenté par le fils gauche d'un noeud binaire père
  • le frère cadet d'un noeud n-aire est implémenté par le fils droit d'un noeud binaire père

Ex

Transformer/Implémenter les arbres \(3\)-aires et \(4\)-aires de l'exemple précédent en arbres Binaires.

Arêtes. Chemins⚓︎

Def

Une Arête est un trait modélisant une relation entre deux sommets dits contigüs, ou adjacents.

Def

  • Un Chemin (de \(s\) à \(v\)) est une succession de plusieurs arêtes consécutives (reliant \(s\) à \(v\))
  • La longueur d'un chemin est le nombre d'arêtes sur ce chemin
Grraar--aCheminbbr--bcca--cArêtedda--deea--effb--fgge--gArêtehhe--h
Chemin de la racine r vers h
Longueur 3
Grraar--aCheminbbr--bcca--cArêtedda--deea--effb--fgge--ghhe--hArête
Chemin de b à g
Longueur 4

Pte

Un arbre est connexe, donc il existe toujours au moins un chemin entre deux sommets \(s\) et \(v\) quelconques Un arbre est acyclique, donc il existe au plus (donc exactement) un chemin entre deux sommets \(s\) et \(v\) quelconques

Pte

Il existe exactement un chemin depuis la racine vers chacun des noeuds

Taille d'un Arbre⚓︎

Def

La taille d'un arbre est le nombre de noeuds qu'il contient. On la note \(n\) en général

Ga b a--b
Taille n = 2
Ga b a--bc a--c
Taille n = 3
Ga b a--bc a--cd c--d
Taille n = 4
Ga b a--bc a--cg c--gh c--h
Taille n = 5
Ga b a--bc a--cd b--de b--ef b--fg c--gh c--hj f--j
Taille n = 9
Ga b a--bc a--cd b--de b--ef b--fg c--gh c--hi d--ij e--jk e--kl g--lm j--m
Taille n = 13

Profondeur d'un Noeud. Niveau \(p\)⚓︎

Def

La profondeur d'un noeud est la longueur (=nb d'arêtes) du plus court chemin vers la racine. La profondeur de la racine vaut donc \(0\)

Gr     a     r--ab     r--bp0Profondeur 0r--p0        c     a--cd     a--de     a--ef     b--fp1Profondeur 1b--p1        g     e--gh     e--hp2Profondeur 2f--p2        p3Profondeur 3h--p3        p0--p1p1--p2p2--p3

Def

Le niveau \(p\) d'un arbre est la réunion de tous les noeuds ayant la même profondeur \(p\)

Gcluster00Niveau 0cluster01Niveau 1cluster02Niveau 2cluster03Niveau 3r     b     r--ba     r--af     b--fe     a--ed     a--dc     a--ch     e--hg     e--g

Hauteur d'un Arbre⚓︎

Def

La hauteur d'un arbre est la profondeur du noeud le plus profond.
On la note \(h\) en général.

  • la hauteur de l'arbre vide vaut \(-1\) par convention
  • la hauteur de l'arbre réduit à la racine vaut \(0\)

Pte

La hauteur d'un arbre est le nombre d'arêtes du plus long chemin de la racine vers une feuille

Ga b a--b
Hauteur h = 1
Ga b a--bc a--c
Hauteur h = 1
Ga b a--bc a--cd c--d
Hauteur h = 2
Ga b a--bc a--cg c--gh c--h
Hauteur h = 2
Ga b a--bc a--cd b--de b--ef b--fg c--gh c--hj f--j
Hauteur h = 3
Ga b a--bc a--cd b--de b--ef b--fg c--gh c--hi d--ij e--jk e--kl g--lm j--m
Hauteur h = 4

⚠ ATTENTION ⚠

Certains auteurs définissent différemment, comme suit, la hauteur d'un arbre :

  • la hauteur de l'arbre vide \(0\)
  • la hauteur de l'arbre réduit à une racine vaut \(1\)
  • Plus généralement, la hauteur est alors le nombre de noeuds du plus long chemin de la racine à une feuille ce qui revient à compter le nombre de sommets du chemin le plus long entre la racine et une feuille (au lieu de compter les arêtes) Bien vérifier la définition choisie dans l'énoncé...