Insertion dans un BST

Un arbre binaire de recherche (BST), c'est comme un arbre généalogique organisé par taille. Chaque personne a au maximum deux enfants : un a gauche (plus petit) et un a droite (plus grand).

Le principe est simple : quand tu veux ranger une nouvelle valeur, tu pars de la racine et tu descends. Si la valeur est plus petite que le noeud ou tu te trouves, tu vas a gauche. Si elle est plus grande ou egale, tu vas a droite. Tu continues jusqu'a trouver une place vide.

Pour représenter ca en Python, on utilise une classe Node avec trois attributs : valeur, gauche et droite (qui sont None par défaut).

Par exemple, si tu inseres 5, puis 3, puis 7 :

racine = None
racine = insérer(racine, 5)
racine = insérer(racine, 3)
racine = insérer(racine, 7)
# racine.valeur vaut 5
# racine.gauche.valeur vaut 3
# racine.droite.valeur vaut 7

Écris une classe Node et une fonction insérer(racine, valeur) qui place la valeur au bon endroit dans l'arbre. Si racine est None, retourne un nouveau Node.

Tests (2/4)

Racine nulle

racine = insérer(None, 5)
assert racine.valeur == 5

Insertion gauche/droite

racine = None
for v in [5, 3, 7]:
    racine = insérer(racine, v)
assert racine.gauche.valeur == 3
assert racine.droite.valeur == 7

+ 0 tests cachés

Indices (3 disponibles)

Solution officielle

class Node:
    def __init__(self, valeur):
        self.valeur = valeur
        self.gauche = None
        self.droite = None

def inserer(racine, valeur):
    if racine is None:
        return Node(valeur)
    if valeur < racine.valeur:
        racine.gauche = insérer(racine.gauche, valeur)
    else:
        racine.droite = insérer(racine.droite, valeur)
    return racine

← Recherche binaire récursive Recherche dans un BST →

solution.py

Bravo!

Insertion dans un BST

Tests (2/4)

Indices (3 disponibles)

Solution officielle