Génération d'arbres binaires de recherche
Génération
Notre objectif est de fabriquer (générer) toutes les formes d'arbres binaires de recherche. Il y en a une infinité... Il faut limiter notre étude. On peut filtrer par taille, certes, mais les étiquettes peuvent être quelconques. Si on considère un lot de \(n\) étiquettes distinctes dans un ABR, on obtiendra toujours le même parcours infixe : la liste triée des étiquettes, il est donc pertinent de ne considérer que le rang des étiquettes et savoir où les placer.
Autrement dit, pour trouver toutes les formes possibles d'ABR à \(n\) nœuds, on peut se contenter de trouver tous les ABR dont les étiquettes sont les entiers de \(1\) à \(n\).
Modélisation
Dans cet exercice, on modélisera les arbres binaires de recherche avec des tuples, de la façon suivante :
- l'ABR vide sera modélisé par
(), le tuple vide. - un ABR non vide sera modélisé par
(gauche, label, droite), un tuple à trois éléments représentant respectivement le sous-arbre à gauche, l'étiquette et le sous-arbre à droite. L'étiquette sera un entier, et les sous-arbres représentés avec des tuples de manière récursive.
Premiers cas
Il n'y a qu'un seul ABR à \(0\) nœud : l'ABR vide.
ABR_0 = [()]
Il n'y a qu'un seul ABR à \(1\) nœud étiqueté \(1\): l'ABR avec juste le nœud \(1\) inséré.
ABR_1 = [((), 1, ())]
Il y a deux ABR à \(2\) nœuds étiquetés \(1\) et \(2\):
- un ABR avec \(1\) comme racine, et donc \(2\) à droite.
- un ABR avec \(2\) comme racine, et donc \(1\) à gauche.
ABR_2 = [
((), 1, ((), 2, ())),
(((), 1, ()), 2, ())
]
Il y a 5 ABR avec trois nœuds étiquetés de \(1\) à \(3\).
- Avec \(1\) comme racine, les deux autres nœuds \(2\) et \(3\) sont à droite, et il y a deux façons de les placer. D'abord le \(2\), ou d'abord le \(3\).
- Avec \(2\) comme racine, il n'y a qu'une seule possibilité : le \(1\) à gauche et le \(3\) à droite.
- Avec \(3\) comme racine, les deux autres nœuds \(1\) et \(2\) sont à gauche, et il y a deux façons de les placer. D'abord le \(1\), ou d'abord le \(2\).
Les 5 ABR étiquetés de 1 à 3
graph TB
A(1)
A --> A0( )
A --> A1(2)
A1 --> A10( )
A1 --> A11(3)
A11 --> A110( )
A11 --> A111( )
B(1)
B --> B0( )
B --> B1(3)
B1 --> B10(2)
B1 --> B11( )
B10 --> B100( )
B10 --> B101( )
H( ) --- C(2)
C --> C0(1)
C --> C1(3)
C0 --> C00( )
C0 --> C01( )
C1 --> C10( )
C1 --> C11( )
D(3)
D --> D0(1)
D --> D1( )
D0 --> D00( )
D0 --> D01(2)
D01 --> D010( )
D01 --> D011( )
E(3)
E --> E0(2)
E --> E1( )
E0 --> E00(1)
E0 --> E01( )
E00 --> E000( )
E00 --> E001( )
linkStyle 12 stroke-width:0px;
style H opacity:0;Exercice
Le dictionnaire dico_abr qui, à une taille n donnée, associe la liste des ABR étiquetés de 1 à n commence par l'entrée 0: [()] : la liste qui n'a qu'un seul élément, l'ABR vide.
Compléter le script avec la fonction génère_abr qui prend n un entier et qui modifie le dictionnaire dico_abr avec toutes les clés entiers naturels k inférieurs ou égaux à n et dont la valeur associée est la liste (peu importe l'ordre) des ABR de taille k étiquetés de 1 à k modélisés avec le tuple.
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)