Uso práctico de M-Way Tree

Question

He comenzado a estudiar estructuras de datos nuevamente. Encontré muy pocos usos prácticos de esto. Uno de ellos era sobre el sistema de archivos en el disco. ¿Alguien puede darme más ejemplo de usos prácticos del árbol M-Way?

Answer 1

Los árboles M-Way aparecen en muchas arenas. Aquí hay una pequeña muestra:

1. Árboles B: estos son árboles de búsqueda como un árbol de búsqueda binario con un gran factor de ramificación. Están diseñados de tal manera que cada nodo pueda caber justo dentro de la memoria que se puede leer desde un disco duro en una pasada. Tienen las mismas garantías asintóticas de BST regulares, pero están diseñados para minimizar el número de nodos buscados para encontrar un elemento particular. En consecuencia, muchos sistemas de bases de datos gigantes usan árboles B u otras estructuras relacionadas para almacenar tablas grandes en discos. De esa manera, el número de lecturas de disco costosas se minimiza y la eficiencia general es mucho mayor.
2. Ocrees. Octrees y sus primos bidimensionales Quadtrees son estructuras de datos para puntos de almacenamiento en un espacio tridimensional. Se usan ampliamente en videojuegos para detección de colisión rápida y cálculos de representación en tiempo real, y seríamos mucho peores impares si no fuera por ellos.
3. Enlace/corte de árboles. Estos árboles especializados se utilizan en problemas de flujo de red para calcular eficientemente las coincidencias o encontrar flujos máximos mucho más rápido que los enfoques convencionales, lo que tiene una gran aplicabilidad en la investigación de operaciones.
4. Bosques de set disjunto. Estos árboles múltiples se utilizan en algoritmos de árbol mínimo para calcular para calcular la conectividad cegadoramente rápido, optimizando el tiempo de ejecución a alrededor del límite teórico.
5. Intentos. Estos árboles se utilizan para codificar los datos de la cadena y permitir una búsqueda, almacenamiento y mantenimiento extremadamente rápidas de conjuntos de cadenas. También se usan en algunos manifestantes de expresión regulares.
6. Van Emde Boas Trees: una implementación rápida de rayos de colas prioritarias de enteros que está respaldado por un bosque de árboles con enorme factor de ramificación.
7. Sufijo árboles. Estas joyas del mundo de procesamiento de texto permiten búsquedas rápidas de cadenas. También generalmente tienen un factor de ramificación mucho mayor que dos.
8. Árboles pq. Estos árboles para las permutaciones de codificación permiten pruebas de planaridad en tiempo lineal, que tiene aplicaciones en el diseño del circuito y el dibujo de gráficos.

¡Uf! Eso es muchos árboles. ¡Espero que esto ayude!

Answer 2

Por M-Way, ¿te refieres a un árbol generalizado? Si es así, casi cualquier jerarquía de 'padre soltero'.