Utilisation pratique de l'arbre m-way

Question

J'ai commencé à étudier à nouveau les structures de données. J'ai trouvé très peu d'utilisations pratiques de cette. L'un de ceux qui étaient sur le système de fichiers sur le disque. Quelqu'un peut-il me donner exemple plus d'utilisations pratiques de l'arbre m-way.

Answer 1

arbres M-chemin viennent dans beaucoup de domaines. Voici un petit échantillon:

1. B-arbres: ce sont des arbres de recherche comme un arbre de recherche binaire avec un énorme facteur de ramification. Ils sont conçus de manière telle que chaque nœud peut tenir juste à l'intérieur de la mémoire qui peut être lu à partir d'un disque dur en un seul passage. Ils ont tous les mêmes garanties de asymptotiques BSTS régulières, mais sont conçus pour minimiser le nombre de noeuds recherché pour trouver un élément particulier. Par conséquent, de nombreux systèmes de bases de données géantes utilisent B arbres ou d'autres structures connexes pour stocker de grandes tables sur les disques. De cette façon, le nombre de disque coûteux lit comme suit est minimisé et l'efficacité globale est beaucoup plus grande.
2. octrees. Octree et leurs cousins ??à deux dimensions quadtrees sont des structures de données pour stocker des points dans l'espace tridimensionnel. Ils sont largement utilisés dans les jeux vidéo pour les calculs de rendu de détection de collision rapide et en temps réel, et nous serions bien pire étrange sinon pour eux.
3. arbres Link / coupe. Ces arbres spécialisés sont utilisés dans les problèmes de flux de réseau pour appariements calculer efficacement ou trouver des flux maximal beaucoup plus rapidement que les approches conventionnelles, ce qui a d'énormes application dans la recherche opérationnelle.
4. forêts disjoints-set. Ces arbres multivoies sont utilisés dans les algorithmes d'arbres minimum couvrant à la connectivité ultra rapide calcul, l'optimisation de l'exécution pour contourner la limite théorique.
5. Essaye. Ces arbres sont utilisés pour coder les données de chaîne et permettent extrêmement rapide recherche, le stockage et l'entretien des ensembles de cordes. Ils sont également utilisés dans certains marcheurs d'expression régulière.
6. Van Emde Boas Trees- un éclair de mise en œuvre rapide des files d'attente prioritaires d'entiers qui est soutenue par une forêt d'arbres avec facteur de ramification énorme.
7. arbres Suffixe. Ces bijoux du monde de traitement de texte permettent de recherches de chaîne rapide. Ils ont aussi généralement un facteur de ramification beaucoup supérieur à deux.
8. PQ-arbres. Ces arbres pour le codage permutations permettent de tester de planéité en temps linéaire, qui a des applications dans la mise en circuit et le dessin graphique.

Ouf! Cela fait beaucoup d'arbres. Espérons que cela aide!

Answer 2

Par m-way, voulez-vous dire un arbre généralisé? Si oui, à peu près une hiérarchie « parent unique ».