Ejemplos del mundo real de estructuras de árboles

https://stackoverflow.com/questions/577659

05-09-2019
|

Pregunta

Estoy buscando algunos ejemplos de estructuras de árbol que se utilizan en proyectos de software comercial/libre, modernos o antiguos.Puedo ver ejemplos en Wikipedia, pero estoy buscando ejemplos más concretos y cómo se usan.Por ejemplo, las claves primarias en las bases de datos se almacenan (por lo que he leído) en la estructura BST o una variación de BST (no dude en corregirme en esto)

Mi pregunta no se limita a los árboles de búsqueda binaria (BST), puede incluir cualquier variación, como rojo-negro, AVL, etc.

Solución

¿Está bien si los ejemplos son un poco poco genérico es decir, se refieren a los gráficos y no necesariamente a los árboles? Si es así, siga leyendo.

No es necesario decir la mayoría de los analizadores XML / Marcado utilizan los árboles. Ver Apache Xerces por ejemplo. O bien, el analizador Xalan XSLT. Gracias mathewsdave26 por recordármelo!
PDF es un formato basado en árbol. Tiene un nodo root seguido por un nodo catalog (estos son a menudo los mismos), seguido de un nodo pages que tiene varios nodos page niño. Los productores / consumidores a menudo usan una implementación árbol equilibrado para almacenar un documento en la memoria.
Informática juegos de ajedrez construir un enorme árbol (formación) que se podan en tiempo de ejecución utilizando la heurística para llegar a un movimiento óptimo.
llamarada es una librería de visualización escrito en AS. Es posible que desee comprobar cómo se asignan los objetos de datos. En particular, el paquete flare.analytics en gran medida utiliza una estructura gráfica, árboles de expansión, etc.
Las redes sociales es la palabra de moda en la investigación CS. No hace falta decir que conexiones / relaciones se modelan de manera natural mediante gráficos. A menudo, los árboles se utilizan para representar / identificar los fenómenos más interesantes. ¿Cómo responder a preguntas como "¿Tiene Harry y Sally tiene amigos (s) común?"
Algunos motores de juegos de física / muy exitosas construyen árboles para simular con precisión el movimiento humano. Un árbol en este caso normalmente se corresponderá con un conjunto de acciones; El contexto determinará qué camino se toma para hacer una respuesta particular.
Aprendizaje basado árbol de decisión en realidad forma un área formidable de la investigación de minería de datos. Existen numerosos métodos famosos como ensacado, aumentando, y modificaciones de los mismos que trabajan en los árboles. Este tipo de trabajo se utiliza a menudo para generar un modelo predictivo.
Un problema común en bioinformática es buscar en grandes bases de datos para encontrar coincidencias para una cadena de consulta dada. Tries son una ocurrencia común allí.
No pocos éxito (stock) comerciantes utilizan árboles de decisión en su día a día de comercio - para elegir un oficio, para salir de uno. Muchas veces estos no están codificadas en un programa de ordenador, pero escrito en algún lugar en la parte posterior de su portátil.

Dupe. Ver este y este .

Otros consejos

El índice de la base de datos B en B * árboles significa equilibrado, no binario. El árbol se mantiene a una profundidad uniforme para asegurar un tiempo de acceso.

Su sistema de archivos es una estructura de árbol. Así que echa un vistazo a la fuente a cualquier sistema de archivos libre.
Su compilador genera un AST de su código fuente, como una etapa intermedia. Así que echa un vistazo a la fuente a cualquier compilador gratuito.

Los índices de bases de datos normalmente se almacenan como variamts de B * árboles que, a pesar de su nombre no son árboles binarios.

Los árboles binarios se han utilizado para la eliminación de superficie oculta en juegos 3D de edad Espacio Partición y, creo que se empleó en el juego Doom.

Escribir un simple analizador sintáctico descendente recursivo, y tienen que generar un árbol de análisis.
Bill-Of-Materiales estructura utilizada en la fabricación (como un automóvil consiste en subconjuntos, de forma recursiva, hasta los tornillos y tuercas).
tabla de símbolos (como se utiliza en un compilador).
plan de cuentas que se utiliza en la gestión de proyectos. Un proyecto global tiene sub-proyectos, a los que los cargos pueden ser aplicados.
Compañía estructura organizativa:. Divisiones, departamentos, etc.
Tabla de contenidos de un documento.
Los descendientes de una persona, ancestros de una persona.
Cualquier Lisp s-expresión, incluyendo cualquier programa Lisp.

características auto-completos en software (por ejemplo. Motor de búsqueda "sugerencias", tipo IDE / símbolo de finalización, los nombres de correo electrónico y la libreta de direcciones, etc.) a menudo se implementan como Tries, que son estructuras de árbol.

En cuanto a cualquiera de los productos de datawarehousing verá formas inteligentes de almacenamiento y la perforación de dimensiones en forma de árbol. Se obtiene una estructura de árbol para la ubicación (país, región, estado, m condado, ciudad, etc.) y el tiempo (año, mes, día, hora). Esas dos dimensiones son comunes en muchos campos, pero mucho otros datos del mundo real también se presta para el árbol.

Por ejemplo, en el comercio minorista de alimentos, en la raíz del árbol que podría tener las tiendas de comestibles, que pueden profundizar en los productos lácteos, frutas y verduras, etc. Después de un solo hilo que podría tener. Latas de frijoles, en el nivel superior estarán hablando en camiones cargados, entonces vendrán a palets, cajas, tamaños de estaño. Todos los diferentes SKU (unidades de mantenimiento de stock) son importantes para alguien dentro de la tienda o empresa. A continuación, los diferentes tipos de frijoles, diferentes proveedores, fabricantes -. Todos los ejemplos de árboles de la misma dimensión

Todos los diferentes productos que forman un enorme árbol, con diferentes formas de corte y dicinng.

C ++ incluye una serie de colecciones (set, multi_set, mapa, multi_map) que normalmente se implementan como árboles rojo-negro, una especie de árbol de equilibrado.

(estándar de C ++ no requiere explícitamente esta aplicación, pero esto es el diseño más simple que cumple con los requisitos de complejidad.)

En un lugar de enrutador/conmutador en el que solía trabajar, usamos un montón de estructuras de árbol, para la tabla de enrutamiento del software usamos una árbol de raíz (opción bastante común para una tabla de enrutamiento IP).

Nuestra implementación OSPF hizo uso de árboles rojo-negros, nuestra implementación de BGP hizo uso de listas de omisión.

Técnicamente, las skiplists no son estructuras de árbol, pero en la práctica son muy similares y son realmente geniales.

Definitivamente usamos muchísimo bastante bien pensando en ello, ha pasado un tiempo desde que trabajo allí.

Las consultas DNS .. cualquier cosa usando un mapa utiliza AVL

System.Collections.Generic.SortedList un árbol de búsqueda binaria como la implementación subyacente. Lo mismo es cierto para System.Collections.GenericSortedDictionary . Cualquier código usando SortedList o SortedDictionary es el uso de un árbol binario de búsqueda.

En mi proyecto, un sistema de edición e imputación de datos de la encuesta / censo, se utiliza un árbol de decisión binaria para decidir qué variables de un registro a imputar o no imputar. El árbol de decisión binaria nos permite tomar decisiones acerca de las rutas de manera eficiente en el árbol que debemos y no debemos tomar.

Creo que este enfoque (aunque tal vez no sólo los árboles binarios) se utiliza en aplicaciones de inteligencia artificial, así

Utilizamos una estructura de árbol para modelar un sistema de clasificación de parte. Las piezas se clasifican en 'clases' que tienen las clases padre y así sucesivamente. Las clases de nivel superior en coche el texto de las pestañas en el catálogo de interfaz de usuario. Las clases también se utilizan para aplicar reglas de precios, identificar los 'puntos calientes' en un vehículo donde las partes se muestran en un 'configurador', etc. Tenemos el modelo del árbol en SQL utilizando conjuntos anidados de Joe Celko y cargarlos a la carta en la memoria para un mejor actuación. Las consultas más comunes que hacemos son 'quiénes son mis descendientes' y 'es esta clase de un antepasado mío?'

Muy práctico

clasificación de objetos en general es muy a menudo hace usando árboles. Y muy a menudo, un gráfico sería mucho más adecuado que un árbol, sin embargo un árbol ofrece dos grandes ventajas sobre un gráfico:

Puede ser representado como una lista (anidada). Por ejemplo, es mucho más fácil de mostrar un gran árbol en el papel (con títulos, subtítulos, párrafos y listas anidadas) o en una pantalla de ordenador de un gráfico.
Puede apuntar a un elemento en el árbol utilizando una cadena de ruta sencilla (o una pila), por ejemplo "http / StackOverflow.com / Usuarios / C Dimitri", algo que es mucho más difícil de hacer en un gráfico.

Hay una Treap implementado en ActionScript. Fuentes:

El Treap es parte de la AS3Commons Colecciones marco . A Treap modificado se usa para respaldar las colecciones SortedSet y SortedMap incluidos.

Ponte como la raíz del árbol y ahora que sus padres como hijos de árbol y los padres de los padres como sus hijos del árbol y esto puede hacer que un caso de uso completo del árbol.

Así que la aplicación de algo donde la jerarquía completa de la familia que requiere puede utilizar el árbol para aplicar esa.

Licenciado bajo: CC-BY-SA con atribución

No afiliado a StackOverflow