Aller au contenu

TNSI : Arbres Binaires (AB)⚓︎

Définitions⚓︎

Def

Un Arbre Binaire (AB) est un arbre dont chaque noeud a au plus deux fils, généralement ordonnés:

  • le fils gauche ou enfant gauche (éventuellement vide) et
  • le fils droit ou enfant droit (éventuellement vide)

arbreTTYYT--YOOT--OPPY--PHHY--HO--HNNO--N

Arbre 1 : Arbre Binaire Enraciné, étiqueté avec des Lettres

arbreNNYYN--YO1ON--O1DDY--DPPY--PTTO1--THHO1--HCCD--CO2OD--O2P--EEP--E

Arbre 2 : Arbre Binaire Enraciné, étiqueté avec des Lettres

Arbres Binaires Équilibrés⚓︎

Définition⚓︎

Arbre Binaire Équilibré, Version 1

Un Arbre Binaire est Équilibré \(\Leftrightarrow\) pour chaque noeud, les hauteurs des sous-arbres gauche (SAG) et sous-arbre droit (SAD) ne diffèrent au plus que de \(1\)

Intuitivement, un arbre binaire équilibré, ou arbre binaire à critère d'équilibre, est un arbre binaire qui maintient une certaine forme d'équilibre :

  • dans la répartition entre ses fils Gauche et Droit : comprendre entre le côté gauche et le côté droit (de chaque noeud) de l'arbre, et
  • dans la profondeur entre chacune de ses branches

!!! info ⚠ ATTENTION ⚠ Le terme équilibré peut avoir des significations variables selon les auteurs. Toujours Bien Lire la définition donnée.

Cas de Figure Arbes Binaires Équilibrés. Justifiez⚓︎

ABaba--bca--cdb--deb--e
Arbre Binaire
équilibré
ABaba--bca--cdb--deb--ehc--hic--ifd--fgd--g
Arbre Binaire
équilibré
ABaba--bca--cdb--deb--ev1c--v1ic--ifd--fgd--g
Arbre Binaire
équilibré
ABaba--bca--cdb--deb--ehc--hic--iji--jv2i--v2fd--fgd--gv1d--v1
Arbre Binaire
équilibré
ABaba--bca--cv2b--v2db--deb--ehc--hic--iv3c--v3ji--jv4i--v4ki--k fd--fgd--gv1e--v1me--mv5f--v5lf--l
Arbre Binaire
équilibré

Cas de Figure Arbes Binaires Non Équilibrés. Justifiez⚓︎

ABaba--bv1a--v1cb--cv2b--v2dc--dv3c--v3v4d--v4v5d--v5
Arbre Binaire
Non équilibré
"Arbre Peigne"
ABaba--bca--cdb--deb--efd--fgd--g
Arbre Binaire
Non équilibré
ABaba--bca--chb--hdb--dc--hic--iji--jki--kfd--fgd--g
Arbre Binaire
Non équilibré
ABaba--bca--cdb--dhb--hc--hic--ifd--fgd--gjh--jkh--kli--lmi--m
Arbre Binaire
Non équilibré
AB121--231--3v102--v1042--4v92--v952--593--9v43--v4v83--v8v14--v1v74--v764--685--8v35--v376--7v26--v2v59--v5109--101110--11v610--v6
Arbre Binaire
Non équilibré

Hauteur Logarithmique d'un Arbre Binaire Équilibré⚓︎

Pte

Un Arbre Binaire Équilibré admet une hauteur logarithmique en la taille \(n\) de l'arbre : càd que la hauteur \(h\) d'un Arbre Binaire Équililibré est proportionnelle à \(\log_2(n)\) càd que dans un arbre Binaire Équilibré, il existe une constante \(C\) telle que :

\(h\le C\times \log_2 (n)\)

Hauteur d'un Arbre Binaire Quelconque

  1. Remarquons que l'arbre binaire soit équilibré est un argument nécessaire dans cette propriété, sinon cette propriété est fausse. Pourquoi?
  2. Quelle est la hauteur \(h\) d'un arbre binaire peigne de taille \(n\) ? (en fonction de \(n\))
  3. Dans un arbre binaire quelconque de taille \(n\), combien vaut la hauteur \(h\) (en fonction de \(n\)) ...
    • dans le meilleur des cas? (i.e. la plus petite hauteur possible -à proportionnalité près-)
    • dans le pire des cas? (i.e. la plus grande hauteur possible)
  4. En déduire un encadrement, en fonction de \(n\), (à proportionnalité près pour le minimum) pour la hauteur \(h\) d'un arbre binaire quelconque:
\[minimum(n)? \le h \le maximum(n)?\]

Généralisation de la Définition d'un Arbre Binaire Équilibré⚓︎

En fait, il existe plusieurs critères d'équilibre pour les Arbres Binaires, certains plus restrictifs que d'autres :

Voici Deux Critères d'Équilibre Classiques

  • Un critère d'équilibre partiel qui permettra de définir les Arbres Binaires AVL = Arbres Binaires de Recherche Équilibrés comme ceci :
    • Pour chaque noeud, les hauteurs des sous-arbres gauche (SAG) et sous-arbre droit (SAD) ne diffèrent au plus que de \(1\)
  • Un critère d'équilibre total qui permettra de définir les Arbres Binaires Complets (à gauche), comme ceci :
    • tous les niveaux de l'Arbre Binaire sauf (peut-être) le dernier sont totalement remplis/complets
    • les noeuds du dernier niveau sont situés/entassés à gauche (sans aucun "trou" entre le 1er et le dernier noeud du dernier niveau)

Ces deux notions ont en commun, en tant que conséquence, de garantir une hauteur logarithmique de l'arbre binaire, càd que la hauteur \(h\) de l'arbre (binaire) est proportionnelle au \(\log_2\) de la taille \(n\) de l'arbre. Ce qui est finalement la seule chose qui importe vraiment pour optimiser (ici minimiser) la "taille" (comprendre la hauteur) de la structure de données devant contenir \(n\) objets. C'est pourquoi certains auteurs choisissent la définition suivante, plus générale, pour un arbre binaire équilibré :

Arbre Binaire Équilibré, Version 2 : plus générale

Un Arbre Binaire est Équilibré \(\Leftrightarrow\) la hauteur est logarithmique en la taille \(n\) de l'arbre \(\Leftrightarrow\) la hauteur \(h\) est proportionnelle à \(\log_2 (n)\)

Sauf mention contraire, nous choisirons toujours la Version 1 (un peu plus générale) comme définition d'un arbre binaire équilibré, et qui implique que la hauteur d'un Arbre Binaire équilibré soit logarithmique.

Arbres Binaires Complets⚓︎

Def

Un Arbre Binaire est Complet (à gauche) \(\Leftrightarrow\)

  • tous les niveaux de l'Arbre Binaire sont parfaitement remplis, sauf (peut-être) le dernier niveau
  • les noeuds du dernier niveau sont tous situés à gauche (sans aucun "trou" entre le 1er et le dernier noeud du dernier niveau)

Remarque

⚠ ATTENTION ⚠ Le terme complet peut avoir des significations variables selon les auteurs. Toujours Bien Lire la définition donnée.

Cas de Figure : Arbres Binaires Complets. Justifiez⚓︎

ABaba--bca--cdb--dv1b--v1
Arbre Binaire
Complet
(donc équilibré)
ABaba--bca--cdb--deb--e
Arbre Binaire
Complet
(donc équilibré)
ABaba--bca--cdb--deb--efc--fv1c--v1v2c--v2
Arbre Binaire
Complet
(donc équilibré)
ABaba--bca--cdb--deb--ehc--hic--ifd--fgd--g
Arbre Binaire
Complet
(donc équilibré)
ABaba--bca--cdb--deb--efc--fgc--ghd--hid--ije--jv1e--v1v2
Arbre Binaire
Complet
(donc équilibré)
ABaba--bca--cdb--deb--efc--fgc--glf--lmf--mhd--hid--ije--jke--k
Arbre Binaire
Complet
(donc équilibré)

Cas de Figure : Arbres Binaires Non Complets. Justifiez⚓︎

ABaba--bca--cv1b--v1db--dv2
Arbre Binaire
Non Complet
(mais équilibré)
ABaba--bca--cdb--dv1b--v1c--v1ec--e
Arbre Binaire
Non Complet
(mais équilibré)
ABaba--bca--cdb--deb--ec--efc--f
Arbre Binaire
Non Complet
(mais équilibré)
ABaba--bca--cdb--deb--ev1c--v1fc--fv2
Arbre Binaire
Non Complet
(mais équilibré)
ABaba--bca--cdb--deb--ev1c--v1ic--ifd--fgd--g
Arbre Binaire
Non Complet
(mais équilibré)
ABaba--bca--cdb--deb--efc--fgc--ghd--hid--iv1e--v1je--j
Arbre Binaire
Non Complet
(mais équilibré)
ABaba--bca--cdb--deb--ehc--hic--iji--jv1i--v1fd--fgd--gv2d--v2
Arbre Binaire
Non Complet
(mais équilibré)
ABaba--bca--cv2b--v2db--deb--ehc--hic--iv3c--v3ji--jv4i--v4v5i--v5 fd--fgd--gme--mv1e--v1g--v2lg--l
Arbre Binaire
Non Complet
(mais équilibré)

Arbres Binaires Parfaits⚓︎

Def

Un Arbre Binaire est parfait lorsque tous ses niveaux sont parfaitement remplis (absolument aucun noeux manquant)

ABa
Arbre
Binaire
Parfait
ABaba--bca--c
Arbre
Binaire
Parfait
ABaba--bca--cdb--deb--egc--ghc--h
Arbre Binaire
Parfait
AB121--231--342--452--563--673--784--894--9105--10115--11126--12136--13147--14157--15
Arbre Binaire
Parfait
AB121--231--342--452--563--673--784--894--9105--10115--11126--12136--13147--14157--15168--16178--17189--18199--192010--202110--212211--222311--232412--242512--252613--262713--272814--282914--293015--303115--31
Arbre Binaire
Parfait

Implémentations des Arbres Binaires⚓︎

Plusieurs implémentations sont possibles : tuples, listes et dictionnaires Python, ou bien POO

Implémentation par Tuples Python⚓︎

  • Un Arbre Binaire peut être implémenté par une imbrication de plusieurs triplets (s, t1, t2) où l'on a :
  • Chaque noeud de l'arbre Binaire est représenté par tuple t = (s, t1, t2) représente un noeud pour lequel :
    • s est l'étiquette du noeud
    • t1 est un tuple représentant le SAG Sous-Arbre Gauche (éventuellement vide)
    • t2 est un tuple représentant le SAD Sous-Arbre Droit (éventuellement vide)
t = ('F', ('R',('I', (), ()), ()), ('A', ('S', (), ()), ('E', (), ())))
# ou bien, plus simplement, en remplaçant :
# ('I', (), ()) par 'I'   et
# ('S', (), ()) par 'S'   et
# ('E', (), ()) par 'E'
t = ('F', ('R','I', ()), ('A', 'S', 'E'))
$$\Leftarrow$$
ABFFRRF--RAAF--AIIR--ISSR--SA--SEEA--Ev1
Arbre 1

Arbre Binaire Vide
Noter que cette implémentation des AB revient à noter l'arbre Binaire vide :

()              # comme le tuple vide, plutôt que comme...
((), (), ())    # un triplet de tuples vides...

Implémentation par Listes Python⚓︎

Le même type d'implémentation peut se faire avec des listes Python : cela revient à remplacer toutes les () par des [] L'habitude veut que l'on préfère réserver les listes Python pour des collections d'objets de même type. Mais c'est néanmoins parfaitement possible.

Implémentation par Dictionnaires Python⚓︎

Un Arbre Binaire peut être implémenté par un dictionnaire {s0: [fg0, fd0], s1: [fg1, fd1], ...} où l'on a :

  • s0, s1, ... sont les étiquettes des noeuds
  • fg0, fg1, ... sont les clés des fils gauches (éventuellement vides : '')
  • fd0, fd1, ... sont les clés des fils droits (éventuellement vides : '')
ab = {
  'F' : ['R', 'A'],
  'R' : ['I', ''],
  'I' : ['', ''],
  'A' : ['S', 'E'],
  'S' : ['', ''],
  'E' : ['', '']
}
$\Leftarrow$
ABFFRRF--RAAF--AIIR--ISSR--SA--SEEA--Ev1
Arbre 1

Implémentation POO avec une Classe Noeud⚓︎

class Noeud:
  """Un Noeud d'un Arbre Binaire"""
  def __init__(self, valeur, gauche=None, droit=None):
    self.valeur = valeur
    self.gauche = gauche
    self.droit = droit
$\Leftarrow$
ABFFRRF--RAAF--AIIR--ISSR--SA--SEEA--Ev1
Arbre 1

Un objet de cette classe contient trois attributs:

  • un attribut gauche pour modéliser le sous-arbre gauche
  • un attribut valeur pour modéliser l'étiquette du noeud
  • un attribut droit pour modéliser le sous-arbre droit

Pour construire un arbre, il suffit d'instancier la classe Noeud autant de fois qu'il y a de noeuds dans l'arbre :

>>> ab = Noeud("F", 
      Noeud('R', Noeud('I'), None),
      Noeud('A', Noeud('S'), Noeud('E'))
    )
  • L'arbre Binaire vide est modélisé par None, qui n'est donc pas, en particulier, une instance de la classe Noeud
  • Si le noeud n est une feuille, Alors :
    • n.gauche = None donc vide
    • n.droit = None donc vide

Implémentation POO avec une Classe AB⚓︎

Voici un début d'implémentation d'une classe AB modélisant un Arbre Binaire en POO :

class AB:
  """Un AB = Arbre Binaire"""
  def __init__(self, valeur, gauche=None, droit=None):
    self.valeur = valeur
    self.gauche = gauche
    self.droit = droit

  def set_gauche(self, gauche=None):
    self.gauche = gauche

  def get_gauche(self):
    return self.gauche

  def set_droit(self, droit=None):
    self.droit = droit

  def get_droit(self):
    return self.droit

  def set_valeur(self, valeur):
    self.valeur = valeur

  def get_valeur(self):
    return self.valeur
$$\Leftarrow$$
ABFFRRF--RAAF--AIIR--ISSR--SA--SEEA--Ev1
Arbre 1

Un objet de cette classe contient trois attributs:

  • un attribut gauche pour modéliser le sous-arbre gauche
  • un attribut valeur pour modéliser l'étiquette du noeud
  • un attribut droit pour modéliser le sous-arbre droit

Créer un Arbre Binaire avec uniquement une racine 'F' :

>>> ab = AB('F')

Pour ajouter/supprimer des noeuds dans l'arbre, il faudrait créer les méthodes adaptées. Cf le TD Arbres Binaires.

Arbre Binaire Vide Remarquer qu'un Arbre Binaire Vide est ici implémenté par None, donc en particulier n'est PAS une instance de la classe AB.

Parcours d'Arbres Binaires⚓︎

Def

Un Parcours d'Arbre définit un ordre dans lequel on parcoure (la totalité de) ses noeuds

Parcours en Largeur⚓︎

Parcours en Largeur

Dans un Parcours en Largeur :

  • l'arbre est parcouru niveau par niveau :
    • niveau 0: la racine, puis
    • niveau 1: les fils de la racine, puis
    • niveau 2: les petits-fils de la racine,
    • etc...
    • jusqu'au dernier niveau: les feuilles
  • Chaque étage est quant à lui parcouru de gauche à droite

Parcours en Profondeur⚓︎

(+ Exercice) Parcours en Profondeur

Dans un Parcours en Profondeur : Pour chaque noeud, l'un des deux sous-arbres est d'abord parcouru entièrement, avant de commencer à explorer le deuxième sous-arbre.

On distingue \(3\) types de parcours en profondeur selon l'ordre relatif dans lequel est explorée la Racine par rapport au fils Gauche et au fils Droit:

Parcours Préfixe⚓︎

Parcours Préfixe, ou Parcours Préordre

Le Parcours Préfixe ou Parcours Préordre est caractérisé par Racine -> Gauche -> Droit
Chaque noeud est visité avant que ses fils le soient.
On part de la racine, puis on visite le fils gauche, puis le fils droit.
Parcours Préfixe Arbre 1: T-Y-P-O-H-N

ABTTYYT--YOOT--OPPY--PHHY--HO--HNNO--N

Arbre 1

Ex

Déterminer le parcours préfixe de l'Arbre 2 ci-dessous: ______________________________

N-Y-D-C-O-P-E-O-T-H

ABNNYYN--YO1ON--O1DDY--DPPY--PTTO1--THHO1--HCCD--CO2OD--O2EEP--Ev1P--v1

Arbre 2

Parcours Infixe⚓︎

Parcours Infixe ou Parcours en ordre

Le Parcours Infixe ou Parcours en ordre est caractérisé par Gauche -> Racine -> Droit
Chaque noeud est visité après son fils gauche mais avant son fils droit.
Parcours Infixe Arbre 1: P-Y-T-H-O-N

ABTTYYT--YOOT--OPPY--PHHY--HO--HNNO--N

Arbre 1

Ex

Déterminer le parcours infixe de l'Arbre 2 ci-dessous : ______________________________

C-D-O-Y-E-P-N-T-O-H

ABNNYYN--YO1ON--O1DDY--DPPY--PTTO1--THHO1--HCCD--CO2OD--O2EEP--Ev1P--v1

Arbre 2

Parcours Postfixe ou Parcours Postordre⚓︎

Parcours Postfixe ou Parcours Postordre

Le Parcours Postfixe ou Parcours Postordre est caractérisé par Gauche -> Droit -> Racine
Chaque noeud est visité après que ses fils Gauche et Droit aient été visités.
Parcours Postfixe Arbre 1: P-Y-H-N-O-T

ABTTYYT--YOOT--OPPY--PHHY--HO--HNNO--N

Arbre 1

Ex

Déterminer le parcours postfixe de l'Arbre 2 ci-dessous : ______________________________

C-O-D-E-P-Y-T-H-O-N

ABNNYYN--YO1ON--O1DDY--DPPY--PTTO1--THHO1--HCCD--CO2OD--O2EEP--Ev1P--v1

Arbre 2