Un arbre binaire de recherche (BST) est une structure de données d'arbre binaire dans laquelle chaque sommet a au plus deux enfants, appelés enfant gauche et enfant droit.
Dans un BST, les valeurs clés des sommets dans le sous-arbre gauche sont inférieures à la valeur clé de la racine, et les valeurs clés des nœuds dans le sous-arbre droit sont supérieures à la valeur clé de la racine. Cette propriété permet des opérations de recherche, d'insertion et de suppression efficaces, rendant les BST utiles pour implémenter des algorithmes tels que la recherche binaire et diverses structures de données comme les ensembles et les cartes.

Implémentation de BST

class TreeNode:
    def __init__(self, key):
        # Initialize a new TreeNode with a given key value
        self.key = key
        self.left = None  # Initialize left child pointer to None
        self.right = None  # Initialize right child pointer to None

class BST:
    def __init__(self):
        # Initialize an empty Binary Search Tree (BST) with no root
        self.root = None

    def insert(self, key):
        # Insert a new key into the BST
        if self.root is None:  # If the tree is empty, create a new root node
            self.root = TreeNode(key)
        else:
            self._insert_recursive(self.root, key)  # Otherwise, call recursive insertion

    def _insert_recursive(self, root, key):
        # Recursively insert the key into the appropriate position in the tree
        if key < root.key:  # If the key is less than the current node's key, go left
            if root.left is None:  # If the left child is None, insert a new node
                root.left = TreeNode(key)
            else:
                self._insert_recursive(root.left, key)  # Otherwise, continue recursion to the left
        elif key > root.key:  # If the key is greater than the current node's key, go right
            if root.right is None:  # If the right child is None, insert a new node
                root.right = TreeNode(key)
            else:
                self._insert_recursive(root.right, key)  # Otherwise, continue recursion to the right

    def delete(self, key):
        # Delete a key from the BST
        self.root = self._delete_recursive(self.root, key)  # Call recursive deletion

    def _delete_recursive(self, root, key):
        # Recursively delete the key from the tree
        if root is None:  # If the tree is empty or key not found, return None
            return root
        if key < root.key:  # If the key is less than the current node's key, go left
            root.left = self._delete_recursive(root.left, key)  # Recursively delete from the left subtree
        elif key > root.key:  # If the key is greater than the current node's key, go right
            root.right = self._delete_recursive(root.right, key)  # Recursively delete from the right subtree
        else:  # Key found, perform deletion
            if root.left is None:  # If the left child is None, return the right child
                return root.right
            elif root.right is None:  # If the right child is None, return the left child
                return root.left
            else:  # Node has both children, find successor and replace key with successor
                successor = self._find_min(root.right)
                root.key = successor.key
                root.right = self._delete_recursive(root.right, successor.key)
        return root

    def search(self, key):
        # Search for a key in the BST
        return self._search_recursive(self.root, key)  # Call recursive search

    def _search_recursive(self, root, key):
        # Recursively search for the key in the tree
        if root is None or root.key == key:  # If root is None or key found, return root
            return root
        if key < root.key:  # If the key is less than the current node's key, search left subtree
            return self._search_recursive(root.left, key)
        return self._search_recursive(root.right, key)  # Otherwise, search right subtree

Complexité temporelle des opérations de base

Remarque

Un arbre équilibré est une structure de données dans laquelle les hauteurs des sous-arbres de n'importe quel nœud diffèrent d'au plus un. Nous en discuterons plus en détail dans les sections suivantes.

1. Insertion :

   • Meilleur et Cas Moyen (O(log n)) : Dans un BST équilibré, l'insertion implique de descendre dans l'arbre à partir de la racine pour trouver la position appropriée pour le nouveau nœud. À chaque niveau, l'espace de recherche est divisé en deux, réduisant le temps de recherche de manière logarithmique par rapport au nombre de nœuds ;
   • Pire Cas (O(n)) : Si l'arbre devient déséquilibré, comme lorsque les nœuds sont insérés dans l'ordre trié, l'arbre peut dégénérer en une liste chaînée. Dans ce cas, l'opération d'insertion devient linéaire par rapport au nombre de nœuds, car chaque nouveau nœud est simplement ajouté à la fin de la liste.

2. Suppression :

   • Meilleur et Cas Moyen (O(log n)) : Similaire à l'insertion, la suppression dans un BST équilibré implique de descendre dans l'arbre pour trouver le nœud à supprimer. L'espace de recherche est divisé en deux à chaque niveau, résultant en une complexité temporelle logarithmique ;
   • Pire Cas (O(n)) : Comme pour l'insertion, si l'arbre devient déséquilibré, la suppression peut se dégrader à une complexité temporelle de O(n). Par exemple, supprimer un nœud d'un arbre déséquilibré peut nécessiter de traverser la plupart ou la totalité des nœuds.

3. Recherche :

   • Meilleur et Cas Moyen (O(log n)) : La structure du BST permet une recherche efficace en traversant récursivement l'arbre à partir de la racine. L'espace de recherche est réduit de moitié à chaque niveau, conduisant à une complexité temporelle logarithmique ;
   • Pire Cas (O(n)) : Dans le pire des cas, l'arbre est déséquilibré, ce qui entraîne un temps de recherche linéaire. Cela se produit lorsque l'arbre dégénère en une liste chaînée, et la recherche traverse la plupart ou la totalité des nœuds.