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