Vidéo: Le principe du Tri par tas. Partie 1 2024
Un type particulier de structure arborescente est le tas binaire, qui place chacun des éléments du nœud dans un ordre spécial. Les arborescences de recherche vous permettent de rechercher rapidement des données. Obtenir des éléments de données, les placer dans un ordre trié dans un arbre, puis rechercher dans cet arbre est l'un des moyens les plus rapides de trouver des informations.
Dans un tas binaire, le noeud racine contient toujours la plus petite valeur. Lorsque vous regardez les branches, vous voyez que les branches de niveau supérieur ont toujours une valeur plus petite que les branches et les feuilles de niveau inférieur. L'effet est de garder l'arbre équilibré et dans un ordre prévisible afin que la recherche devient extrêmement efficace. Le coût est en gardant l'arbre équilibré.
Parmi toutes les tâches effectuées par les applications, la recherche est la plus longue et la plus demandée. Même si l'ajout de données (et le tri ultérieur) nécessite un certain temps, l'avantage de créer et de maintenir un ensemble de données provient de son utilisation pour effectuer un travail utile, ce qui signifie qu'il doit rechercher des informations importantes. Par conséquent, vous pouvez parfois vous en sortir avec une fonctionnalité CRUD moins efficace et même une routine de tri moins qu'optimale, mais les recherches doivent être aussi efficaces que possible. Le seul problème est qu'aucune recherche n'effectue toutes les tâches avec une efficacité absolue, vous devez donc peser vos options en fonction de ce que vous attendez de faire dans le cadre des routines de recherche.
Deux des méthodes de recherche les plus efficaces impliquent l'utilisation de l'arbre de recherche binaire (BST) et du tas binaire. Les deux techniques de recherche s'appuient sur une structure arborescente pour contenir les clés utilisées pour accéder aux éléments de données. Cependant, l'arrangement des deux méthodes est différent, ce qui explique pourquoi l'un a des avantages sur l'autre lorsqu'il exécute certaines tâches. Cette figure montre l'arrangement pour un BST.
Notez comment les touches suivent un ordre dans lequel des nombres plus petits apparaissent à gauche et des nombres plus grands apparaissent à droite. Le nœud racine contient une valeur qui se trouve au milieu de la plage de touches, ce qui donne au BST une approche équilibrée facile à comprendre pour stocker les clés. Comparez cet arrangement au tas binaire montré ici.
Chaque niveau contient des valeurs inférieures au niveau précédent et la racine contient la valeur de clé maximale pour l'arborescence. De plus, dans ce cas particulier, les valeurs les plus basses apparaissent à gauche et les plus grandes à droite (bien que cet ordre ne soit pas strictement appliqué). La figure représente en fait un tas max binaire. Vous pouvez également créer un tas binaire min dans lequel la racine contient la valeur de clé la plus basse et chaque niveau génère des valeurs plus élevées, les valeurs les plus élevées apparaissant dans les feuilles.
Comme indiqué précédemment, BST présente certains avantages par rapport au tas binaire lorsqu'il est utilisé pour effectuer une recherche. La liste suivante fournit quelques-uns des points forts de ces avantages:
- La recherche d'un élément nécessite un temps O (log n), par rapport au temps O (n) pour un tas binaire.
- L'impression des éléments dans l'ordre ne nécessite que l'heure O (log n), contrairement à l'heure O (n log n) pour un tas binaire.
- Trouver le plancher et le plafond nécessite un temps O (log n).
- La localisation du Kth plus petit / plus grand élément nécessite l'heure O (log n) lorsque l'arbre est correctement configuré.
L'importance de ces temps dépend de votre application. BST a tendance à mieux fonctionner dans les situations où vous passez plus de temps à chercher et moins de temps à construire l'arbre. Un tas binaire a tendance à mieux fonctionner dans les situations dynamiques dans lesquelles les clés changent régulièrement. Le tas binaire offre également des avantages, comme décrit dans la liste suivante:
- La création des structures requises nécessite moins de ressources car les tas binaires reposent sur des tableaux, ce qui les rend également plus conviviaux.
- La construction d'un tas binaire nécessite un temps O (n), contrairement à BST, qui nécessite un temps O (n log n).
- L'utilisation de pointeurs pour implémenter l'arborescence n'est pas nécessaire.
- S'appuyer sur des variations de tas binaires (par exemple, le tas de Fibonacci) offre des avantages tels que l'augmentation et la diminution des temps clés de O (1) temps.
