Arbre ternaire de Berggrens
Définition
Un arbre ternaire est une structure qui ressemble aux arbres binaires, mais au lieu de deux sous-arbres s'il est non vide, c'est trois sous-arbres : à gauche, au milieu et à droite.
Un arbre ternaire est, ou bien :
- un arbre vide, qu'on peut noter nil,
- sinon, il possède un nœud particulier, sa racine, et exactement trois sous-arbres indépendants, un à gauche, un au milieu et un à droite, qui sont des arbres ternaires.
Nouvelle modélisation
Cet exercice n'utilise pas la classe Noeud pour construire un arbre.
Cet exercice utilise un tuple ((a, b, c), gauche, milieu, droite) pour désigner un nœud
- portant l'étiquette
(a, b, c); les côtés d'un triangle rectangle, - pointant vers trois sous-arbres : à gauche, au milieu, à droite.
None désignera encore directement un arbre ternaire vide, comme toujours tant qu'on ne travaille pas avec une classe Arbre 
.
Ainsi, si arbre est un arbre ternaire non vide, on pourra réaliser un dépaquetage (unpack) pour accéder aux différentes composantes.
triplet, gauche, milieu, droite = arbre
a, b, c = triplet
L'arbre ternaire de Berggrens
Un triplet pythagoricien primitif est un triplet d'entiers \((a, b, c)\) qui sont les côtés d'un triangle rectangle avec \(a^2 + b^2 = c^2\), et tels que \(a\) et \(b\) sont premiers entre eux (\(1\) est le seul diviseur commun à \(a\) et \(b\)).
Pour un triplet pythagoricien \((a, b, c)\), on définit trois nouveaux triplets de la manière suivante :
- le triplet \((a_0, b_0, c_0)\) tel que :
- \(a_0 = +a-2b+2c\),
- \(b_0 = +2a-b+2c\),
- \(c_0 = +2a-2b+3c\)
- le triplet \((a_1, b_1, c_1)\) tel que :
- \(a_1 = +a+2b+2c\),
- \(b_1 = +2a+b+2c\),
- \(c_1 = +2a+2b+3c\)
- le triplet \((a_2, b_2, c_2)\) tel que :
- \(a_2 = -a+2b+2c\),
- \(b_2 = -2a+b+2c\),
- \(c_2 = -2a+2b+3c\)
On admet qu'on obtient trois nouveaux triplets pythagoriciens primitifs.
En partant de \((3, 4, 5)\), on obtient l'arbre ternaire de Berggrens qui est infini. Il regroupe tous les triplets pythagoriciens primitifs. C'est un excellent outil pour résoudre certains problèmes où on cherche des distances entières dans un réseau à mailles carrées.
En tronquant l'arbre de Berggrens à la hauteur 3, on obtient (sans dessiner les nil):
graph TB
R("(3, 4, 5)")
R --> R0("(5, 12, 13)")
R0 --> R00("(7, 24, 25)")
R0 --> R01("(55, 48, 73)")
R0 --> R02("(45, 28, 53)")
R --> R1("(21, 20, 29)")
R1 --> R10("(39, 80, 89)")
R1 --> R11("(119, 120, 169)")
R1 --> R12("(77, 36, 85)")
R --> R2("(15, 8, 17)")
R2 --> R20("(33, 56, 65)")
R2 --> R21("(65, 72, 97)")
R2 --> R22("(35, 12, 37)")On obtient cet arbre avec le code suivant :
def berggrens(a, b, c, h):
if h == 0:
return None
else:
a_0 = +a - 2*b + 2*c
b_0 = +2*a - b + 2*c
c_0 = +2*a - 2*b + 3*c
a_1 = +a + 2*b + 2*c
b_1 = +2*a + b + 2*c
c_1 = +2*a + 2*b + 3*c
a_2 = -a + 2*b + 2*c
b_2 = -2*a + b + 2*c
c_2 = -2*a + 2*b + 3*c
return ((a, b, c),
berggrens(a_0, b_0, c_0, h - 1),
berggrens(a_1, b_1, c_1, h - 1),
berggrens(a_2, b_2, c_2, h - 1),
)
Ainsi que l'appel >>> berggrens(a=3, b=4, c=5, h=3)
Tronquer au périmètre 130
Au lieu de tronquer à la hauteur 3, on pourrait tronquer au périmètre 130 et obtenir (sans dessiner certains nil):
graph TB
R("(3, 4, 5)")
R --> R0("(5, 12, 13)")
R0 --> R00("(7, 24, 25)")
R00 --> R000("(9, 40, 41)")
R00 --> R001(" ")
R00 --> R002(" ")
R0 --> R01(" ")
R0 --> R02("(45, 28, 53)")
R --> R1("(21, 20, 29)")
R --> R2("(15, 8, 17)")
R2 --> R20(" ")
R2 --> R21(" ")
R2 --> R22("(35, 12, 37)")Il y a 8 (vrais) nœuds dans cette troncature. (nil n'est pas un vrai nœud).
Exercice
-
Modifier la fonction
berggrens- qui prend désormais en paramètres
a,b,cun triplet pythagoricien etpun entier - et qui renvoie un arbre de Berggrens tronqué de tous les triplet qui ont un périmètre inférieur ou égal à
p. 
Une docstring sera attendue à cette fonction ! Elle devra commencer par Renvoie
- qui prend désormais en paramètres
-
Coder une fonction
taillequi prend unarbreternaire en paramètre et qui renvoie son nombre de nœuds.
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)