Construction d'arbre binaire de recherche
La notion d'arbre binaire de recherche ne concerne que les arbres binaires dont les étiquettes sont comparables, par exemples toutes numériques, ou toutes des chaines de caractères.
Définition avec doublons à droite
Un arbre binaire de recherche est tel que, pour tout nœud, on a
- son étiquette est strictement supérieure à toute valeur du sous-arbre à gauche,
- son étiquette est inférieure ou égale à toute valeur du sous-arbre à droite.
Exemples d'ABR
graph TB
A("8")
B("3")
C("15")
D("2")
E((" "))
F("12")
G("23")
H((" "))
I((" "))
J((" "))
K((" "))
L((" "))
M((" "))
A --> B
A --> C
B --> D
B --> E
C --> F
C --> G
D --> H
D --> I
F --> J
F --> K
G --> L
G --> Mgraph TB
A("8")
B("3")
C("15")
D("2")
E((" "))
F("8")
G("23")
H((" "))
I((" "))
J((" "))
K((" "))
L((" "))
M((" "))
A --> B
A --> C
B --> D
B --> E
C --> F
C --> G
D --> H
D --> I
F --> J
F --> K
G --> L
G --> MPropriété récursive
Un arbre binaire de recherche est tel que
- ou bien c'est un arbre binaire vide,
- ou bien les trois points sont vérifiés.
- Sa racine porte une étiquette strictement supérieure ou égale à toute valeur du sous-arbre à gauche.
- Sa racine porte une étiquette inférieure ou égale à toute valeur du sous-arbre à droite.
- Les deux sous-arbres sont eux-même des arbres binaires de recherche.
Construction à partir d'un arbre binaire vide
Il est possible de construire l'ABR du premier exemple ci-dessus en partant d'un arbre binaire vide et en insérant successivement, et dans l'ordre, les nœuds suivants : [8, 3, 15, 2, 12, 23]. (Ce n'est pas la seule possibilité).
Exercice
Coder une fonction liste_vers_abr qui prend en paramètre valeurs une liste d'étiquettes et qui renvoie un arbre binaire de recherche représenté à l'aide de la classe Noeud construit avec l'ajout successif et dans l'ordre des valeurs.
L'arbre renvoyé doit être défini comme dans la section précédente, à l'aide de la classe Noeud. Il n'y a pas de classe ABR dans cet exercice.
La méthode __eq__ de la classe Noeud est disponible, de sorte que vous pourrez faire des tests d'égalité entre arbres.
Méthode __eq__ de la classe Noeud
class Noeud:
def __init__(self, valeur, gauche=None, droite=None):
self.valeur = valeur
self.gauche = gauche
self.droite = droite
def __eq__(self, ab):
"""Test d'égalité récursif entre arbres binaires
self est non vide, ab est peut-être vide
"""
if ab is None:
return False
else:
return (
(self.valeur == ab.valeur)
and (self.gauche == ab.gauche)
and (self.droite == ab.droite)
)
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)