class BST(object):
    """Classe pour les arbres binaires de recherche (Binary Search Tree)"""

    def __init__(self, value, left = None, right = None):
        """
Méthode d'initialisation d'un arbre : appelée automatiquement lors de la
création d'un objet de la classe. On y définit les trois attributs des objets
de la classe.
        """
        self.value = value
        self.left = left
        self.right = right

    def add_value(self, value):
        """
Ajout d'une valeur dans l'arbre self : on utilise un algorithme minimaliste qui
place la valeur sans se préoccuper de rééquilibrer l'arbre
        """
        while True:
            if value < self.value:
                if self.left is None:
                    self.left = BST(value)
                    break
                else:
                    self = self.left
            else:
                if self.right is None:
                    self.right = BST(value)
                    break
                else:
                    self = self.right

    def add_value_rec(self, value):
        """
Version récursive de la méthode add_value()
        """
        if value < self.value:
            if self.left is None:
                self.left = BST(value)
            else:
                self.left.add_value_rec(value)
        else:
            if self.right is None:
                self.right = BST(value)
            else:
                self.right.add_value_rec(value)

    def seach(self, needle):
        """
Recherche dans l'arbre self : la méthode retourne le sous-arbre dont la racine
contient needle, ou None si la recherche échoue
        """
        while self != None:
            if self.value == needle:
                return self
            elif needle < self.value:
                self = self.left
            else:
                self = self.right
        return None

    def search_rec(self, needle):
        """
Version récursive de la méthode search()
        """
        if self == None:
            return None
        elif self.value == needle:
            return self
        elif needle < self.value:
            return self.left.search_rec(needle)
        else:
            return self.right.search_rec(needle)

    def remove_value(self, value):
        """
Méthode d'effacement d'une valeur de l'arbre.
        """
        pass