Définition - Que signifie l'arbre de recherche binaire à auto-équilibrage?
Un arbre de recherche binaire à auto-équilibrage est un type de structure de données qui s'auto-ajuste pour fournir des niveaux cohérents d'accès aux nœuds. Dans un arbre de recherche binaire à auto-équilibrage, les connexions du nœud supérieur aux nœuds supplémentaires sont triées et réajustées de sorte que l'arbre soit pair, et les lignes de trajectoire de recherche pour chaque nœud d'extrémité sont égales en termes de longueur.
Un arbre de recherche binaire à équilibrage automatique est également appelé arbre équilibré ou arbre de recherche binaire à hauteur équilibrée.
Definir Tech explique l'arbre de recherche binaire à auto-équilibrage
Un arbre de recherche binaire en général fournit une structure de données avec un nœud en haut, et un ou deux nœuds qui y sont connectés à chaque niveau suivant. Les arborescences de recherche binaires prennent en charge trois opérations: les opérateurs peuvent insérer des composants, supprimer des composants ou rechercher un certain nombre ou un autre contenu de nœud. L'avantage des arbres de recherche binaires est que le système peut trier pour ignorer la moitié de l'arbre à chaque niveau, ce qui conduit à des charges de travail de recherche plus efficaces.
L'aspect positif d'un arbre de recherche binaire auto-équilibré est que l'accès aux nœuds est égal - par exemple, au lieu d'avoir à parcourir cinq étapes d'un côté de l'arbre, ou trois étapes de l'autre côté de l'arbre, à cause du soi -structure de nœud ajustée, la recherche n'irait qu'un certain nombre d'étapes (n) vers un nœud d'extrémité donné. Ceci est réalisé en supprimant les connexions de nœuds individuels et en les remplaçant par des connexions binaires pour raccourcir des membres particuliers de l'arbre.
L'inconvénient d'une recherche binaire auto-équilibrée trois est qu'elle ne fonctionne que si les connexions de nœuds sont «indépendantes du niveau» - en d'autres termes, si un nœud individuel peut être réajusté à un niveau antérieur afin de raccourcir la branche d'arbre . Par exemple, si un arbre de recherche binaire auto-équilibré est composé d'un nombre donné en haut, et de deux nombres suivants de chaque côté, et qu'il y a une chaîne de trois nombres supplémentaires avec des connexions à un seul nœud, l'ajustement de l'arbre mettrait le cinquième nœud avec le troisième nœud au lieu du quatrième nœud, de sorte que le troisième nœud a deux nœuds de connexion au lieu d'un. Cependant, si la structure de données doit identifier le contenu d'un nœud particulier comme étant lié dans une relation parent / enfant spécifique, l'ajustement de ces nœuds pour s'adapter à l'uniformité de la structure arborescente ne fonctionnera pas.