Arbre binaire « bien construit »⚓︎
D'après 2021, Métropole, Candidats Libres, J2, Ex. 3
On rappelle qu'un arbre binaire est composé de nœuds, chacun des nœuds possédant éventuellement un sous-arbre à gauche et éventuellement un sous-arbre à droite.
Un nœud sans sous-arbre est appelé feuille.
La taille d'un arbre est le nombre de nœuds qu'il contient ; sa hauteur est le nombre de nœuds du plus long chemin qui joint le nœud racine à l'une des feuilles. Ainsi la hauteur d'un arbre réduit à un nœud, c'est-à-dire la racine, est 1. L'arbre vide a une hauteur de 0.
Dans un arbre binaire de recherche, chaque nœud contient une clé, ici un nombre entier, qui est :
- strictement supérieure à toutes les clés des nœuds du sous-arbre gauche ;
- strictement inférieure à toutes les clés des nœuds du sous-arbre droit.
Ainsi les clés de cet arbre sont toutes distinctes.
Un arbre binaire de recherche est dit « bien construit » s'il n'existe pas d'arbre de hauteur inférieure qui pourrait contenir tous ses nœuds.
On considère l'arbre binaire de recherche ci-dessous.
flowchart TD
A(12) --- B(10)
A --- C(15)
B --- D(5)
B --- E( )
D --- F(4)
D --- G(8)
C --- H( )
C --- I(20)
linkStyle 3 stroke-width:0px;
linkStyle 6 stroke-width:0px;
style E opacity:0;
style H opacity:0;1.a. Quelle est la taille de l'arbre ci-dessus ?
Réponse
La taille est le nombre de nœuds : ici 7.
1.b. Quelle est la hauteur de l'arbre ci-dessus ?
Réponse
La hauteur est le nombre de nœuds du plus long chemin qui joint le nœud racine à l'une des feuilles : ici 4.
2. Cet arbre binaire de recherche n'est pas « bien construit ». Proposer un arbre binaire de recherche contenant les mêmes clés et dont la hauteur est plus petite que celle de l'arbre initial.
Réponse
flowchart TD
A(10) --- B(5)
A --- C(15)
B --- D(4)
B --- E(8)
C --- F(12)
C --- G(20)3. Les classes Noeud et Arbre ci-dessous permettent de mettre en œuvre en Python la structure d'arbre binaire de recherche. La méthode insere permet d'insérer récursivement une nouvelle clé.
class Noeud:
def __init__(self, gauche, valeur, droite):
self.gauche = gauche # gauche est un ABR
self.valeur = valeur
self.droite = droite # droite est un ABR
def est_feuille(self):
return self.gauche.est_vide() and self.droite.est_vide()
class ABR:
def __init__(self):
self.racine = None
def est_vide(self):
"Renvoie le booléen indiquant si l'arbre est vide"
return self.racine is None
def insere(self, x):
"insère x dans l'arbre"
if self.est_vide():
self.racine = Noeud(ABR(), x, ABR())
elif x < self.racine.valeur:
self.racine.gauche.insere(x)
elif x > self.racine.valeur:
self.racine.droite.insere(x)
# Pas de prise en compte des doublons
Donner la représentation de l'arbre codé par les instructions ci-dessous :
a = Arbre(10)
a.insere(20)
a.insere(15)
a.insere(12)
a.insere(8)
a.insere(4)
a.insere(5)
Réponse
flowchart TD
A(10) --- B(8)
A --- C(20)
B --- D(4)
B --- E( )
D --- F( )
D --- G(5)
C --- H(15)
C --- I( )
H --- J(12)
H --- K( )
linkStyle 4 stroke-width:0px;
linkStyle 3 stroke-width:0px;
linkStyle 7 stroke-width:0px;
linkStyle 9 stroke-width:0px;
style E opacity:0;
style F opacity:0;
style I opacity:0;
style K opacity:0;4. Pour calculer la hauteur d'un arbre, on a écrit la méthode incomplète ci-dessous dans la classe Arbre. On rappelle qu'un arbre vide a une hauteur de 0.
def hauteur(self):
if self.est_vide():
return ...
return ... + max(self.racine...., ...)
Compléter cette méthode.
Réponse
def hauteur(self) -> int:
if self.est_vide():
return 0
return 1 + max(self.racine.gauche.hauteur(), self.racine.droite.hauteur())
5. Écrire la méthode taille de la classe Arbre permettant de calculer la taille d'un arbre.
Réponse
def taille(self) -> int:
if self.est_vide():
return 0
return 1 + self.racine.gauche.taille() + self.racine.droite.taille()
6. On souhaite écrire une méthode bien_construit de la classe Arbre qui renvoie la valeur True si l'arbre est « bien construit » et False sinon.
On rappelle que la taille maximale d'un arbre binaire de recherche de hauteur \(h\) est \(2^h-1\).
6.a. Quelle est la taille minimale, notée \(t_\text{min}\), d'un arbre binaire de recherche « bien construit » de hauteur \(h\) ?
Réponse
La taille minimale d'un arbre bien construit de hauteur \(h\) est \(2^{h-1}\).
6.b. Écrire la méthode bien_construit demandée.
Réponse
def bien_construit(self):
h = self.hauteur()
t = self.taille()
return 2**(h - 1) <= t <= 2**h - 1