Les arbres binaires ont-ils un objectif spécifique dans le stockage de données hiérarchiques? Quelle est leur utilisation canonique?

12

Je comprends la structure des arbres binaires et comment les traverser. Cependant, j'ai du mal à réaliser leurs utilisations réelles, leurs buts dans les programmes et la programmation. Quand je pense à des exemples «réels» de données hiérarchiques, ils ont presque certainement plus de 2 enfants. Par exemple, dans un arbre généalogique, une mère peut souvent avoir plus de deux enfants.

Les «arbres binaires» ne sont-ils vraiment utiles que pour stocker des données liées linéairement en raison des temps de traitement plus rapides sur les tableaux et les listes? Alternativement, servent-ils un objectif spécifique dans le stockage des données hiérarchiques? Si oui, quels sont les exemples d'application des arbres binaires. Quelles données sont telles qu'un nœud a au plus 2 enfants?

data-structures binary-tree sw123456
la source
Je pense que l'utilisation principale d'un arbre binaire est de commander des données. https://en.wikipedia.org/wiki/Binary_search_tree
Mandrill

Réponses:

25

Non, les arbres binaires ne sont pas destinés à stocker des données hiérarchiques dans le sens auquel vous pensez. Le principal cas d'utilisation des arbres n-aires, où nest un nombre fixe, est la capacité de recherche rapide , et non une hiérarchie sémantique.

Rappelez-vous l'ancien jeu où une personne pense à un nombre compris entre 1 et 100, et l'autre doit le deviner en aussi peu de suppositions que possible, et si vous vous trompez, la personne qui pense au nombre doit vous dire si vous êtes trop haut ou trop bas? Cela devient ennuyeux après un certain temps parce que vous comprenez rapidement que vous devriez toujours commencer à 50, puis aller à 25 ou 75, et continuer à diviser la plage à rechercher en deux à chaque nouvelle supposition après cela, et finalement vous pouvez deviner n'importe quel nombre en au plus 7 suppositions, c'est garanti.

Cela peut ne pas être un jeu amusant, mais cette propriété rend les arbres binaires (et autres n-aires) utiles: vous pouvez les utiliser pour rechercher un très grand ensemble de données en très peu de temps.

Mason Wheeler
la source
Excellente réponse merci beaucoup. Ainsi, les arbres binaires ne sont vraiment qu'une autre structure pour stocker des données comme vous le feriez dans un tableau ou une liste, mais avec l'avantage supplémentaire de capacités de recherche rapide?
sw123456
1
@ sw123456: C'est vrai. Comme pour toute ingénierie, il est livré avec des compromis, (utilise plus de mémoire - et plus fragmenté - qu'un tableau avec le même nombre d'éléments, O (n) accès à l'élément #n de l'ensemble de données plutôt que O (1) accès, etc.), mais la recherche rapide est certainement le principal avantage des arbres binaires.
Mason Wheeler
@ sw123456 Heureux d'avoir pu l'expliquer :)
Mason Wheeler
3
L'accès aux éléments est O (log (n)) lorsque l'arbre est équilibré. O (n) sera le pire des cas lorsqu'il sera dégénéré (la plupart des nœuds avec une seule parenthèse).
Mandrill
@ sw123456 Le routage réseau utilise une légère modification d'un arbre binaire appelé Trie (créé pour plus d'efficacité pour le domaine problématique). Il stocke en fait des informations de hiérarchie lorsque les routeurs parcourent l'arborescence bit par bit lors de la recherche d'une adresse IP pour trouver où il doit transmettre le paquet. Les adresses IP sont également par nature hiérarchiques, donc en traversant une IP pour trouver la correspondance de préfixe la plus longue, le routeur traverse la hiérarchie IP, les IP de sous-réseau, etc. Ce n'est pas évident sémantiquement, mais la relation est là. Les routeurs utilisent cette structure pour l'efficacité de la recherche, comme l'a répondu Mason.
Chris Cirefice
3

Toute structure arborescente, où un nœud peut avoir un nombre illimité d'enfants, peut être implémentée à l'aide d'un arbre binaire.

Pour chaque nœud de votre arborescence, remplacez-le par un nœud avec un pointeur droit et gauche. Le pointeur gauche va au premier des enfants du nœud. Le nœud droit va au frère suivant du nœud. Tous les enfants d'un nœud donné sont dans une liste chaînée jointe par leur pointeur droit, le début de la liste pointé par le pointeur gauche de leur parent.

Votre arbre n-aire compliqué est devenu un arbre binaire simple.

Je suis sûr que c'est dans Knuth, Vol. 1 quelque part.

Justsalt
la source
Il s'agit d'une implémentation vraiment intéressante. Ai-je raison de penser que parce que chaque nœud enfant était le début d'une liste chaînée, l'arborescence ne serait plus O (log) n) si équilibré ou O (n) sinon, car le fait de visiter chaque nœud commencerait une recherche linéaire? Cette implémentation entraînerait des temps de recherche beaucoup plus lents? Mais à la hausse, les temps de recherche seraient plus rapides que ceux d'une structure linéaire standard? Ai-je bien compris cela?
sw123456
@ sw123456, Si l'arbre d'origine était équilibré, l'arbre binaire résultant ne le serait certainement pas. Je crois que tout le reste dépendra du ventilateur hors de l'arbre, du nombre d'enfants d'un nœud donné. Une recherche linéaire ne se produirait que pour trouver lequel des enfants d'un nœud donné suivre. Mais je ne suis pas sûr que vous puissiez éviter cela dans toute autre implémentation d'un arbre n-aire.
Justsalt
2

Les arbres binaires pourquoi les utiliser?

En programmation, vous travaillez beaucoup avec des collections de données de même type.

Les deux méthodes de base de stockage de ces données sont: les listes liées et les tableaux.

Ils ont tous deux des avantages et des inconvénients: dans une liste chaînée, il est facile d'ajouter des éléments à n'importe quelle position ou de supprimer des éléments. Mais l'accès à un élément spécifique est plus difficile, car vous devez parcourir la liste jusqu'à ce que vous soyez à l'élément souhaité.

  • Il ne recherche pas efficacement, mais l'insertion et la suppression sont faciles.

Avec un tableau, l'accès à un élément spécifique est facile, mais il est plus difficile d'insérer ou de supprimer un élément car l'insertion signifie: étendre le tableau d'un, déplacer tous les éléments avant la position d'insertion 1 vers la droite et insérer l'élément.

  • Il recherche efficacement (s'il est trié) mais l'insertion et la suppression sont difficiles.

Ainsi, la liste liée et le tableau ont tous deux des inconvénients.

Les arbres binaires sont conçus pour résoudre à la fois les problèmes du tableau et de la liste liée:

  1. Insertion et suppression faciles
  2. Recherche facile

Les arbres binaires sont donc faits pour quand vous avez beaucoup de données qui changent régulièrement.

Pieter B
la source