Les nœuds d'un arbre de recherche sont décrits avec quatre termes
importants. Le sommet d'un arbre, où le premier noeud est situé,
est appelé la racine. Si un noeud contient des liens
vers des sous nœuds, ce nœud est connu comme un parent. Les
nœuds sont sous la mère sont appelés les enfants, et un nœud qui
n'a pas de nœuds enfants est appelé une feuille . Ainsi, un
nœud racine est identifié car il n'a pas un parent, et nœuds
feuilles aura pas d'enfants.
Un programme est en mesure de se déplacer dans un arbre la recherche de données en commençant par un noeud particulier, effectuer une vérification conditionnelle puis passer à la suivante noeud logique si les données requises ne sont pas présents. En fonction de la structure de données utilisée , cette recherche peut prendre un temps variable. Si l'arbre de recherche est organisé pendant le processus d'ajout et de suppression nœuds, la recherche peut être très rapide. Quand un arbre est assemblé hasard, est non triés ou autorise les parents multiples, La recherche peut prendre un temps très long.
Un programme est en mesure de se déplacer dans un arbre la recherche de données en commençant par un noeud particulier, effectuer une vérification conditionnelle puis passer à la suivante noeud logique si les données requises ne sont pas présents. En fonction de la structure de données utilisée , cette recherche peut prendre un temps variable. Si l'arbre de recherche est organisé pendant le processus d'ajout et de suppression nœuds, la recherche peut être très rapide. Quand un arbre est assemblé hasard, est non triés ou autorise les parents multiples, La recherche peut prendre un temps très long.
Un facteur qui affecte l'utilisation des arbres de recherche est la
question de l'équilibre. Un arbre équilibré est celui dans lequel le
droit et les enfants gauche du nœud racine contiennent soit la même
profondeur de nœuds enfants ou sont dans un compte à un nœud les uns
des autres. La profondeur de un arbre est le nombre de nœuds à partir de la feuille la plus basse d'un arbre de la racine.
Un arbre déséquilibré pourrait avoir tous les nœuds d'un seul côté ou
avoir toute les nœuds disposés de façon linéaire sans branches.
Lorsque la profondeur d'un arbre augmente, le vitesse
d'algorithmes de recherche peut diminuer considérablement.
Il y a certains types d'arbres de recherche qui sont décrits comme
auto-équilibrage. Ces arbres utilisent des opérations telles que la
rotation de l'arbre à aider maintenir l'équilibre tout la
préservation de l'ordre des données dans les feuilles. Bien que
l'exécution rotations d'arbres pourraient ralentir un programme lors de
l'ajout et la suppression de nœuds, cela est contré par la vitesse à
laquelle les données peuvent être récupérées.
Bien qu'il existe de nombreux types d'arbres de recherche, structure de données d'arbre le plus commun est une recherche binaire
arbre. Ce type de données est constitué de nœuds qui ont chacun
zéro à deux nœuds enfants. Il n'y a qu'un seul nœud racine, et
toutes les feuilles de l'arbre sont classés de gauche à droite
ascendant valeurs selon les données qu'ils détiennent. les
algorithmes de nombreux existent pour les arbres binaires de
recherche que peut faire commander des données très facile.
Il n'y a pas de mise en œuvre de norme unique pour les nœuds recherche
d'arbres. Les nœuds peuvent être représentés par une grande variété
de structures de données. Les tableaux de tableaux peuvent être
utilisés, comme pourrait multiplier les listes chaînées.
Souvent, un arbre de recherche utilise une structure de données
personnalisé qui est conçu pour aider à l'accomplissement des opérations
nécessaires demandées par le programme. même inclure leurs
propres implémentations internes des arbres de recherche. Certains de
bibliothèques de programmation standard
