Ejemplos del mundo real de estructuras arbóreas

Question

Estoy buscando algunos ejemplos de estructuras arbóreas que se utilizan en proyectos comerciales/de software 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 principales en las bases de datos son (por lo que he leído) almacenadas en la estructura BST o una variación de la BST (no dude en corregirme en esto)

Mi pregunta no está limitada Árboles de búsqueda binaria (BST) , puede incluir cualquier variación como rojo-negro, AVL, etc.

Answer 1

¿Está bien si los ejemplos son un poco genéricos, es decir, se relacionan con los gráficos y no necesariamente con los árboles? Si es así, sigue leyendo.

• No hace falta decir la mayoría de los analizadores XML/Marcado utilizan los árboles. Ver Apache Xerces por ejemplo. O el analizador Xalan XSLT. ¡Gracias mathewsdave26 por recordarme!

• PDF es un formato basado en árbol. Tiene un nodo root seguido de un nodo catalog (a menudo son los mismos) seguido de un nodo pages que tiene varios nodos secundarios page. Los productores/consumidores a menudo usan una implementación de árbol balanceado para almacenar un documento en la memoria.

• Los juegos de ajedrez en computadora crean un árbol enorme (entrenamiento) que podan durante el tiempo de ejecución usando heurística para alcanzar un movimiento óptimo.

• Flare es una biblioteca de visualización escrita en AS. Es posible que desee verificar cómo se asignan los objetos de datos. En particular, el paquete flare.analytics utiliza una estructura de gráficos, abarcando árboles, etc.

• Las redes sociales son la palabra de moda actual en la investigación de CS. No hace falta decir que las conexiones/relaciones se modelan muy naturalmente usando gráficos. A menudo, los árboles se usan para representar/identificar fenómenos más interesantes. ¿Cómo respondes preguntas como "Harry y Sally tienen amigos en común?"

• Algunos motores de física/juegos muy exitosos construyen árboles para simular con precisión el movimiento humano. Un árbol en este caso típicamente corresponderá a un conjunto de acciones; El contexto determinará qué camino se toma para generar una respuesta particular.

• El aprendizaje basado en Decision Tree realmente forma un área formidable de investigación de minería de datos. Existen numerosos métodos famosos, como embolsado, refuerzo y modificaciones de los mismos que funcionan en los árboles. Tal trabajo se usa a menudo para generar un modelo predictivo.

• Un problema común en bioinformática es buscar en enormes bases de datos para encontrar coincidencias para una cadena de consulta determinada. Las pruebas son comunes allí.

• Bastantes pocos comerciantes (de acciones) exitosos usan árboles de decisiones en sus operaciones diarias: para elegir una operación, para salir de una. Muchas veces estos no están codificados en un programa de computadora, sino anotados en algún lugar en la parte posterior de su cuaderno.

Dupe. Ver this y this.

Answer 2

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

Answer 3

B en los árboles de índice de base de datos B * significa Balanced, no Binary. El árbol se mantiene a una profundidad uniforme para garantizar tiempos de acceso uniformes.

Answer 4

Al mirar cualquiera de los productos de Datawarehousing, verá formas inteligentes de almacenar y perforar en dimensiones en forma de árbol. Obtiene una estructura de árbol para la ubicación (país, región, estado, m condado, ciudad, etc.) y la hora (Año, Mes, Día, Hora). Esas dos dimensiones son comunes en muchos dominios, pero muchos otros datos del mundo real también se prestan al árbol.

Por ejemplo, en la venta al por menor de alimentos, en la raíz del árbol puede tener alimentos, que pueden profundizar en productos lácteos, frutas & verduras, etc. Siguiendo un solo hilo que podría tener. Latas de frijoles, en el nivel superior estarás hablando en cargas de camiones, luego bajarás a paletas, cajas, tamaños de hojalata. Todos los diferentes SKU (unidades de mantenimiento de existencias) son importantes para alguien dentro de la tienda o empresa. Luego diferentes tipos de frijoles, diferentes proveedores, fabricantes: todos los ejemplos de árboles para la misma dimensión.

Todos los diferentes productos forman un árbol masivo, con diferentes formas de cortar y dividir.

Answer 5

C++ incluye una serie de colecciones (conjunto, multi_set, mapa, multi_map) que normalmente se implementan como árboles rojo-negro, una especie de árbol 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.)

Answer 6

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

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

Answer 7

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

Answer 8

En un lugar de enrutador/conmutador solía trabajar utilizamos un montón de estructuras de árbol, para la tabla de enrutamiento de software usamos un radix tree (opción bastante común para una tabla de enrutamiento de IP).

Nuestra implementación OSPF hizo uso de red-black trees, nuestra implementación BGP hizo uso de skiplists.

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

Definitivamente utilizamos heaps pensando un poco en ello, hace tiempo que trabajo allí.

Answer 9

consultas DNS .. cualquier cosa usando un mapa utiliza AVL

Answer 10

System.Collections.Generic.SortedList<T> utiliza un árbol binario de búsqueda como la implementación subyacente. Lo mismo es cierto para System.Collections.GenericSortedDictionary<T>. Cualquier código que use SortedList <T> u SortedDictionary <T> está utilizando un árbol de búsqueda binario.

Answer 11

• Escribir un simple analizador sintáctico descendente recursivo, y tienen que generar un árbol de análisis.

• estructura de lista de materiales utilizada en la fabricación (como un automóvil se compone de subconjuntos, de forma recursiva, hasta las tuercas y pernos).

• Tabla de símbolos (como se usa en un compilador).

• Gráfico de cuentas como se usa en la gestión de proyectos. Un proyecto global tiene subproyectos, a los que se pueden aplicar cargos.

• estructura organizativa de la empresa: 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.

Answer 12

• Su sistema de archivos es una estructura de árbol. Así que mira la fuente a cualquier sistema de archivos gratuito.

• Su compilador genera un AST desde su código fuente, como una etapa intermedia. Así que revisa la fuente de cualquier compilador gratuito.

Answer 13

se utiliza una estructura de árbol para modelar un sistema de clasificación de parte. Las partes se clasifican en "clases" que tienen clases principales, etc. Las clases de nivel superior dirigen las pestañas de texto en nuestra interfaz de usuario del catálogo. Las clases también se usan para aplicar reglas de fijación de precios, identificar "puntos calientes" en un vehículo donde las partes se muestran en un "configurador", etc. Modelamos el árbol en SQL utilizando los conjuntos anidados de Joe Celko y los cargamos on-demand en la memoria para mejorar actuación. Las consultas más comunes que hacemos son '¿quiénes son mis descendientes' y 'esta clase es un antepasado mío?'

muy práctico

Answer 14

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

Answer 15

Ustedes se perdieron un gran problema.

Un tipo especial de árbol binario balanceado es perfecto para los editores de texto.

Answer 16

Hay un fraude implementado en ActionScript. Fuentes:

• Treap
• TreapIterator
• TreapNode

El Treap es parte de la AS3Commons Collections framework. Se usa un tratamiento modificado para respaldar las colecciones SortedSet y SortedMap incluidas.

Answer 17

La clasificación de objetos en general se realiza muy a menudo mediante el uso de á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 representarse como una lista (anidada). Por ejemplo, es mucho más fácil mostrar un gran árbol en papel (con títulos, subtítulos, párrafos y listas anidadas) o en una pantalla de computadora que un gráfico.
• Puede señalar un elemento en el árbol utilizando una cadena de ruta simple (o una pila), por ejemplo "http/StackOverflow.com/Users/Dimitri C", algo que es mucho más difícil de hacer en un gráfico.