Abr

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

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.