Quelles sont les applications des arbres binaires?
Je me demande ce que les applications particulières des arbres binaires sont. Pourriez-vous nous donner des exemples concrets?
Vous devez vous connecter pour publier un commentaire.
Je me demande ce que les applications particulières des arbres binaires sont. Pourriez-vous nous donner des exemples concrets?
Vous devez vous connecter pour publier un commentaire.
De querelle au sujet de la performance de binaires arbres est dénuée de sens, ils ne sont pas une structure de données, mais une famille de structures de données, avec toutes les différentes caractéristiques de performance. S'il est vrai que déséquilibrée des arbres binaires faire bien pire que auto-équilibrage des arbres binaires pour la recherche, il y a beaucoup d'arbres binaires de (comme les essais) pour qui "d'équilibrage" n'a pas de sens.
Applications des arbres binaires
map
etset
objets dans de nombreuses langues bibliothèques.La raison que les arbres binaires sont utilisés plus souvent que n-aire arbres pour la recherche est que la n-ary arbres sont plus complexes, mais fournissent généralement pas de réel avantage en termes de vitesse.
Dans un (équilibré) arbre binaire avec
m
nœuds, passant d'un niveau à l'autre exige une comparaison, et il y alog_2(m)
niveaux, pour un total delog_2(m)
comparaisons.En revanche, un n-aire arbre exigera
log_2(n)
comparaisons (à l'aide d'une recherche binaire) pour passer au niveau suivant. Puisqu'il y alog_n(m)
niveaux au total, la recherche nécessiteralog_2(n)*log_n(m)
=log_2(m)
comparaisons total. Donc, bien que n-aire arbres sont plus complexes, ils ne donnent pas d'avantage en termes de total de comparaisons nécessaires.(Cependant, la n-aire, les arbres sont toujours utiles dans la niche des situations. Les exemples qui viennent immédiatement à l'esprit sont quad-arbres et d'autres espace-partitionnement des arbres, où de catégorisation de l'espace à l'aide de seulement deux nœuds par le niveau de faire de la logique inutilement complexe; et B-arbres utilisé dans de nombreuses bases de données, où le facteur limitant n'est pas la façon dont de nombreuses comparaisons sont effectuées à chaque niveau, mais le nombre de nœuds peut être chargé à partir du disque dur à la fois)
Quand la plupart des gens parlent des arbres binaires, ils sont plus souvent que de ne pas penser binaire de recherche arbres, donc je vais couvrir que la première.
Un non-équilibrée binaires un arbre de recherche est en fait utile pour un peu plus d'éduquer les étudiants sur des structures de données. C'est parce que, à moins que les données sont à venir dans dans un relativement ordre aléatoire, l'arbre peut facilement dégénérer en son pire des cas la forme, qui est une liste liée, depuis de simples arbres binaires sont pas équilibrée.
Une bonne affaire au point: une fois, j'ai eu à résoudre certains logiciels qui a chargé ses données dans un arbre binaire pour la manipulation et de la recherche. Il a écrit les données dans triés forme:
de sorte que, lorsque le lire, il a terminé avec l'arbre suivant:
qui est la forme dégénérée. Si vous allez à la recherche de Frank dans cet arbre, vous aurez à chercher tous les six nœuds avant de le trouver.
Arbres binaires deviennent vraiment utiles pour la recherche lorsque vous équilibrer. Cela consiste à faire tourner sous-arbres par le biais de leur nœud racine, de sorte que la différence de hauteur entre les deux sous-arbres est inférieure ou égale à 1. L'ajout de ces noms ci-dessus un à un dans l'équilibre de l'arbre serait vous donner la séquence suivante:
Vous pouvez réellement voir l'ensemble des sous-arbres de la rotation vers la gauche (dans les étapes 3 et 6) que les entrées sont ajoutées et cela vous donne un arbre binaire équilibré dans lequel le pire des cas, la recherche est
O(log N)
plutôt que de laO(N
) que la forme dégénérée donne. À aucun moment le plus NUL (=
) diffèrent de la plus faible, en plus d'un niveau. Et, en finale de l'arbre ci-dessus, vous pouvez trouver Frank en regardant uniquement trois nœuds (Chloe
,Edwina
et, enfin,Frank
).Bien sûr, ils peuvent devenir encore plus utile lorsque vous effectuez l'équilibre multi-way arbres plutôt que binaire tress. Cela signifie que chaque nœud possède plus d'un élément (techniquement, ils détiennent N et N+1 pointeurs, un arbre binaire étant un cas particulier de la 1-way multi-chemin de l'arbre avec 1 point et 2 pointeurs).
Avec un arbre, vous vous retrouvez avec:
Il est généralement utilisé dans le maintien de touches pour un index d'articles. J'ai écrit des logiciels de bases de données optimisé pour le hardware sur lequel un nœud est exactement la taille d'un bloc de disque (par exemple, 512 octets) et vous mettez autant de touches que vous pouvez en un seul nœud. Le pointeurs dans ce cas, étaient en fait des numéros d'enregistrement dans une longueur fixe-enregistrement direct-accès au fichier distinct du fichier d'index (sorte de numéro d'enregistrement
X
peut être trouvé simplement en cherchant àX * record_length
).Par exemple, si les pointeurs sont de 4 octets et la taille de la clé est de 10, le nombre de clés dans un 512 octets nœud est de 36. C'est de 36 touches (360 octets) et 37 pointeurs (148 octets) pour un total de 508 octets 4 octets gaspillée par nœud.
L'utilisation de multi-manière dont les touches introduit de la complexité des deux phases de la recherche (multi-moyen de recherche pour trouver le bon nœud combinée avec une petite séquentiel (ou linéaire binaire de recherche) pour trouver la bonne clé dans le nœud), mais l'avantage de faire moins d'I/O disque fait plus de place pour cela.
Je ne vois aucune raison de le faire pour une structure en mémoire, que vous seriez mieux coller avec un arbre binaire équilibré et de garder votre code simple.
Également garder à l'esprit que les avantages de
O(log N)
surO(N)
n'apparaissent pas vraiment lors de vos jeux de données sont de petite taille. Si vous êtes en utilisant un multi-chemin de l'arbre de stocker les quinze personnes dans votre carnet d'adresse, c'est sans doute exagéré. Les avantages de venir quand vous voulez enregistrer quelque chose, comme à chaque commande à partir de vos centaines de milliers de clients au cours des dix dernières années.Le point de l'ensemble de big-O notation pour indiquer ce qui se passe car la
N
approche de l'infini. Certaines personnes peuvent être en désaccord, mais c'est même d'accord pour l'utilisation de tri à bulles si vous êtes sûr que les ensembles de données permettra de rester en dessous d'une certaine taille, tant que rien d'autre n'est disponible 🙂Comme à d'autres usages pour les arbres binaires, il existe un grand nombre, telles que:
Compte tenu de la façon dont beaucoup d'explications, j'ai généré pour l'arbre de recherche, je suis réticent à entrer dans beaucoup de détails sur les autres, mais qui devrait être suffisant pour les recherches, si vous le désirez.
L'organisation de Le code Morse est un arbre binaire.
Un arbre binaire est un arbre de structure de données dans laquelle chaque nœud a au plus deux nœuds enfants, généralement distinguées "de gauche" et "droite". Nœuds avec des enfants de parents, de noeuds, noeuds enfants et peut contenir des références à leurs parents. À l'extérieur de l'arbre, il y a souvent une référence à la "racine" de nœud (l'ancêtre de tous les nœuds), si elle existe. N'importe quel nœud dans la structure de données peut être atteint en commençant au nœud racine et à plusieurs reprises des références suivantes à gauche ou à droite de l'enfant. Dans un arbre binaire un degré de chaque nœud est de maximum deux.
Arbres binaires sont utiles, car comme vous pouvez le voir dans le tableau, si vous voulez trouver n'importe quel nœud de l'arbre, vous n'avez qu'à regarder un maximum de 6 fois. Si vous voulais de recherche pour le nœud 24, par exemple, vous pouvez commencer à la racine.
Cette recherche est illustré ci-dessous:
Vous pouvez voir que vous pouvez exclure la moitié des nœuds de l'arbre tout entier sur la première passe. et la moitié de la sous-arbre gauche sur la deuxième. Cela rend très efficace des recherches. Si cela a été fait sur 4 milliards éléments, vous n'avez qu'à rechercher un maximum de 32 heures. Par conséquent, plus les éléments contenus dans l'arbre, le plus efficace de votre recherche peut être.
Suppressions peuvent devenir complexes. Si le nœud a 0 ou 1 enfant, alors que c'est simplement une question de déménagement de quelques conseils afin d'exclure le seul à être supprimé. Cependant, vous ne pouvez pas facilement supprimer un nœud avec 2 enfants. Nous avons donc prendre un raccourci. Imaginons que nous voulions supprimer le nœud 19.
Depuis essayant de déterminer où pour déplacer la gauche et la droite pointeurs n'est pas facile, nous en trouver un à substituer. Nous allons à la gauche du sous-arbre, et aller jusqu'à un droit que nous pouvons aller. Ce qui nous donne le plus de la valeur du nœud que nous voulons supprimer.
Maintenant nous copier tous 18 du contenu, sauf pour la gauche et la droite pointeurs, et de supprimer l'original 18 nœud.
Pour créer ces images, j'ai mis en place un arbre AVL, un auto-équilibrage de l'arbre, de sorte qu'à n'importe quel point dans le temps, l'arbre a au plus un niveau de différence entre les nœuds feuilles (nœuds sans enfants). Ce qui maintient l'arbre de devenir asymétrique et maintient le maximum
O(log n)
temps de recherche, avec le coût d'un peu plus de temps requis pour les insertions et les suppressions.Voici un exemple montrant comment mon arbre AVL a gardé lui-même comme compacte et équilibrée que possible.
Dans un tableau trié, les recherches encore
O(log(n))
, tout comme un arbre, mais au hasard d'insertion et de suppression permettrait de prendre en O(n) au lieu de l'arbreO(log(n))
. Certains conteneurs STL utilisation de ces caractéristiques de performance à leur avantage afin d'insertion et de retrait des temps de prendre un maximum deO(log n)
, ce qui est très rapide. Certains de ces conteneurs sontmap
,multimap
,set
, etmultiset
.Exemple de code pour un arbre AVL peut être trouvé à http://ideone.com/MheW8
L'application principale est arbres binaires. Ces sont une structure de données dans laquelle la recherche, d'insertion et de suppression sont toutes très rapide (environ
log(n)
opérations)Un exemple intéressant d'un arbre binaire qui n'a pas été mentionné, c'est que d'une manière récursive évalué l'expression mathématique. Il est pratiquement inutile d'un point de vue pratique, mais il est un moyen intéressant de penser à de telles expressions.
Fondamentalement, chaque nœud de l'arbre a une valeur qui est inhérents à lui-même ou est évaluée par récursivement par exploitation sur les valeurs de ses enfants.
Par exemple, l'expression
(1+3)*2
peut être exprimé comme:Pour évaluer l'expression, nous demandons la valeur du parent. Ce nœud à son tour, reçoit ses valeurs auprès de ses enfants, un opérateur plus et un nœud qui contient tout simplement '2'. L'opérateur plus à son tour, reçoit ses valeurs auprès d'enfants avec les valeurs " 1 " et " 3 " et ajoute, de retour de 4 à la multiplication nœud qui renvoie 8.
Cette utilisation d'un arbre binaire est semblable à la notation polonaise inversée dans un sens, dans l'ordre dans lequel les opérations sont effectuées est identique. Aussi une chose à noter est qu'il ne doit pas nécessairement être un arbre binaire, c'est juste que les plus couramment utilisés sont des opérateurs binaires. À son niveau le plus fondamental, l'arbre binaire ici est en fait très simple, purement langage de programmation fonctionnel.
L'un de l'application la plus commune est de stocker efficacement des données dans triés en vue de l'accès et de la recherche stockées éléments rapidement. Par exemple,
std::map
oustd::set
en C++ de la Bibliothèque Standard.Arbre binaire en tant que structure de données est utile pour les différentes implémentations de l'expression d'analyseurs et d'expression des problèmes.
Il peut également être utilisé pour résoudre certains des problèmes de base de données, par exemple, de l'indexation.
Généralement, arbre binaire est un concept général d'arbre en particulier à base de structure de données et de différents types d'arbres binaires peuvent être construits avec des propriétés différentes.
Applications de l'arbre Binaire:
Je ne pense pas qu'il y est l'usage pour les "pure" des arbres binaires. (sauf à des fins éducatives)
Équilibrée des arbres binaires, tels que Arbres rouge-Noir ou AVL arbres sont beaucoup plus utiles, parce qu'ils garantissent O(logn) opérations. Normal des arbres binaires, peut-être une liste (ou presque liste) et ne sont pas vraiment utiles dans les applications qui utilisent beaucoup de données.
Équilibrée, les arbres sont souvent utilisés pour la mise en œuvre de cartes ou de jeux.
Ils peuvent également être utilisés pour le tri en O(nlogn), même quand il existe de meilleures façons de le faire.
Aussi pour la recherche, l'insertion, la suppression de Les tables de hachage peut être utilisé, qui ont généralement de meilleures performances que les arbres binaires (symétrique ou non).
Une application où (équilibré) arbres binaires serait utile serait si la recherche, l'insertion, la suppression et le tri serait nécessaire. Tel pourrait être mise en place (ou presque, en ignorant la pile de l'espace nécessaire pour la récursivité), un prêt build équilibré de l'arbre. Il serait encore O(nlogn), mais avec un plus petit facteur constant et pas d'espace supplémentaire nécessaire (sauf pour le nouveau tableau, en supposant que les données dans un tableau). Les tables de hachage sur l'autre main peut ne pas être triées (au moins pas directement).
Peut-être qu'ils sont également utiles dans certains algorithmes sophistiqués pour faire quelque chose, mais tbh rien ne me vient à l'esprit. Si je trouve plus je vais modifier mon post.
D'autres arbres comme le f.e. B+arbres sont largement utilisés dans les bases de données
En C++, STL, et de nombreuses autres bibliothèques standard dans d'autres langages, comme Java et C#. Arbres binaires sont utilisés pour mettre en œuvre et à la carte.
L'un des plus importants de l'application des arbres binaires sont équilibré binaires de recherche arbres comme:
Ces arbres ont la propriété que la différence de hauteur du sous-arbre gauche et le sous-arbre droit est maintenu de petites par de faire des opérations comme les rotations à chaque fois qu'un nœud est inséré ou supprimé.
Pour cette raison, la hauteur totale de l'arbre reste de l'ordre de n log et les opérations telles que la recherche, l'insertion et la suppression des nœuds sont effectuées en O(log n) fois. La STL du C++ implémente également ces arbres sous la forme de jeux et des cartes.
Ils peuvent être utilisés comme un moyen rapide pour trier les données. Insérer des données dans un arbre de recherche binaire en O(log(n)). Puis traversée de l'arbre afin de les trier.
vos programmes de syntaxe, de même que pour beaucoup d'autres choses telles que les langues naturelles ne peut être analysée à l'aide d'arbres binaires (mais pas nécessairement).
Implémentations de
java.util.Set
Sur le matériel moderne, un arbre binaire est presque toujours sous-optimale en raison du mauvais cache et de l'espace de comportement. Cela vaut également pour les (semi -) équilibré variantes. Si vous en trouvez, c'est là où les performances ne compte pas (ou est dominé par la fonction de comparaison), ou, plus probablement, pour l'histoire ou de l'ignorance des raisons.
Un compilateur qui utilise un arbre binaire pour une représentation d'un AST, peut utiliser des algorithmes connus pour
l'analyse de l'arbre comme postorder,afinde.Le programmeur n'a pas besoin de venir avec son propre algorithme.
Parce qu'un arbre binaire pour un fichier source est plus élevé que le n-aire arbre,c'est la construction prend plus de temps.
Profiter de cette production:
selstmnt := "si" "(" expression ")" stmnt "ELSE" stmnt
Dans un arbre binaire, il aura 3 vues de nœuds, mais la n-aire arbre aura 1 niveau(de chids)
C'est pourquoi Unix OS-s sont lents.