Qu'est-ce qu'un arbre de recherche?
Un arbre de recherche est une structure de données utilisée dans la programmation informatique pour contenir et organiser une liste de données. Chaque arbre de recherche est composé d’un ensemble ordonné de nœuds, qui peuvent être connectés à zéro ou plusieurs autres. Les nœuds individuels contiennent des données ainsi que des liens vers d’autres nœuds. Les données contenues dans les nœuds de l’arborescence sont très souvent ordonnées de manière à permettre aux algorithmes efficaces de rechercher, insérer et supprimer des nœuds avec facilité.
Les nœuds d'un arbre de recherche sont décrits avec quatre termes importants: le sommet d'un arbre, où se trouve le premier nœud, est appelé racine. Si un nœud contient des liens vers -nodes, ce nœud est appelé parent. Les nœuds situés sous le parent sont appelés enfants, et tout nœud ne comportant pas de nœud enfant est appelé feuille. un nœud racine est identifié car il n'a pas de parent et les nœuds terminaux n'auront pas d'enfants.
Un programme peut se déplacer dans une arborescence à la recherche de données en commençant par un nœud particulier, en effectuant un contrôle conditionnel, puis en passant au nœud logique suivant si les données requises ne sont pas présentes. , cette recherche peut prendre un temps variable. Si l’arborescence de la recherche est organisée au cours du processus d’ajout et de suppression de nœuds, la recherche peut être très rapide. de manière aléatoire, non triée ou autorise plusieurs parents, la recherche peut durer très longtemps.
La question de l'équilibre est un facteur qui affecte l'utilisation des arbres de recherche: un arbre équilibré est un arbre dans lequel les enfants droit et gauche du nœud racine contiennent la même profondeur de nœuds enfants ou font partie d'un nombre de nœuds unique. La profondeur d'un arbre est le nombre de nœuds allant de la feuille la plus basse à la racine. Un arbre non équilibré peut avoir tous les nœuds d'un seul côté ou tous Les nœuds sont disposés de manière linéaire, sans branches. Lorsque la profondeur d'un arbre augmente, la vitesse des algorithmes de recherche peut diminuer considérablement.
Certains types d’arbres de recherche décrits comme auto-équilibrés utilisent des opérations telles que la rotation des arbres pour maintenir l’équilibre tout en préservant l’ordre des données dans les feuilles. Les rotations d'arbres peuvent ralentir un programme lors de l'ajout et de la suppression de nœuds. Ceci est contré par la vitesse à laquelle les données peuvent être récupérées.
Bien qu'il existe de nombreux types d'arborescence de recherche, la structure de données d'arborescence la plus courante est une arborescence de recherche binaire, composée de nœuds composés chacun de zéro à deux nœuds enfants. et toutes les feuilles de l’arbre sont classées de gauche à droite en valeurs croissantes en fonction des données qu’ils détiennent. De nombreux algorithmes existent pour les arbres de recherche binaires qui peuvent rendre les données de commande très facile.
Il n’existe pas d’implémentation standard unique pour les nœuds d’arbre de recherche, qui peuvent être représentés par une grande variété de structures de données, de tableaux de tableaux pouvant être utilisés, ainsi que la multiplication de listes chaînées. L'arborescence de recherche utilise une structure de données personnalisée conçue pour faciliter la réalisation des opérations requises par le programme.Certaines bibliothèques de programmation standard incluent même leurs propres implémentations internes d'arborescences de recherche.