Entiendo cómo se implementan los árboles de búsqueda binarios, pero no estoy seguro de cuáles son las ventajas de usarlo sobre las tablas hash que la mayoría de los lenguajes de programación han incorporado a sus bibliotecas estándar.Ejemplos concretos del uso de árboles de búsqueda binarios?
¿Podría alguien dar ejemplos de problemas del mundo real que se pueden resolver con árboles de búsqueda binarios?
Hay algunas ventajas teóricas de árboles binarios de búsqueda más tablas hash:
que almacenan sus elementos en orden ordenado. Esto significa que si desea almacenar el contenedor de manera que pueda visitar fácilmente los valores en orden ordenado, una BST es probablemente una mejor opción que una tabla hash. Por ejemplo, si desea almacenar una colección de estudiantes y luego imprimirlos en orden alfabético, una BST es una opción sustancialmente mejor que una tabla de hash.
Son compatibles con las consultas de rango. Como las BST se almacenan en orden, es fácil responder preguntas de la forma "¿qué valores hay en el rango [x, y]?" en un árbol de búsqueda binaria. Para hacer esto, haz una búsqueda en el árbol para ver el elemento más pequeño mayor que x y el elemento más grande más pequeño que y, luego itera sobre los elementos del árbol entre ellos. Ambas consultas se ejecutan en tiempo O (lg n) en un árbol equilibrado, por lo que el tiempo de ejecución total para esta operación es O (lg n + k), donde k es el número de elementos que coinciden con la consulta.
Son compatibles con las consultas del vecino más cercano. Las tablas hash están diseñadas específicamente para que incluso ligeramente diferentes produzcan códigos hash muy diferentes. Esto le da a los valores hash la dispersión que necesitan para evitar agrupar demasiados elementos en un solo punto. Sin embargo, también significa que debe realizar un escaneo lineal sobre la tabla hash para encontrar elementos que puedan estar "cerca" de lo que está buscando. Con una BST, puede encontrar eficientemente el predecesor y el sucesor de cualquier valor que desee, incluso si no está en el árbol.
Pueden tener mejores peores garantías. La mayoría de las implementaciones de tablas hash tienen algún tipo de caso degenerado en el que una operación puede degradarse a O (n) en el peor de los casos. Una tabla hash de sondeo lineal o una lata de tabla hash encadenada, con un conjunto incorrecto de elementos, requieren O (n) tiempo por búsqueda o requieren O (n) tiempo en una repetición. La inserción en algunos tipos de BST balanceadas, como árboles rojos/negros, árboles AVL o árboles AA, siempre es el caso más desfavorable O (lg n).
Si usted está dispuesto a generalizar BSTs a más elaboradas estructuras de árbol, entonces hay muchas aplicaciones en las que un árbol se puede utilizar para resolver problemas mucho más eficiente que en una tabla hash. He aquí algunos ejemplos:
kd-trees le permiten almacenar datos multidimensionales, mientras que el apoyo a las consultas de rangos rápidos en el espacio multidimensional, así como eficientes Búsquedas de vecino más cercano. Puede usarlos para clasificación (algoritmos de aprendizaje lento) o geometría computacional.
árboles/Terminar vínculo se pueden utilizar para resolver problemas de flujo máximo mucho más eficiente que la mayoría de los algoritmos convencionales permitirían. Los buenos algoritmos push/relabel usan esto para acelerar sus implementaciones.
bosques disjuntos-set se pueden utilizar para mantener las particiones de los elementos como asintóticamente eficiente posible (amortizan α (n) por actualización, donde α (n) es la función inversa Ackermann). Se usan en muchos algoritmos rápidos de árbol de expansión mínima, así como algunos algoritmos de máxima coincidencia.
Las pilas binarias se pueden utilizar para implementar colas de prioridad de manera eficiente. Los árboles más complejos se pueden usar para construir montones binomiales y montones de Fibonacci, que son de gran importancia en la informática teórica.
Los árboles de decisión se pueden utilizar en el aprendizaje automático para clasificación, y como un modelo en la informática teórica para demostrar límites en los tiempos de ejecución de varios algoritmos.
Los árboles de búsqueda ternaria son una alternativa a los intentos que se basan en una BST ligeramente modificada. Permiten una búsqueda e inserción muy rápida de los elementos y los conjuntos de datos dispersos son bastante concisos.
B-trees son utilizados por muchos sistemas de bases de datos para buscar de manera eficiente elementos donde el acceso al disco es un factor limitante.
árboles binarios espacio de partición son una generalización de KD-árboles que pueden ser utilizados para mostrar rápidamente gráficos por ordenador (que se utilizan para optimizar la prestación en el juego original de Doom) y hacer colisión detección.
BK-árboles le permiten determinar rápidamente todas las palabras que se encuentran dentro de una cierta distancia de edición de alguna otra palabra, y más en general para encontrar todos los puntos en un espacio métrico dentro de una cierta distancia de otro punto.
Los árboles de fusión son una alternativa a las tablas hash para las claves de enteros que tienen soporte extremadamente rápido para búsquedas, inserciones y eliminaciones.
árboles van Emde Boas otra alternativa a hash de tablas para las teclas de número entero que apoyan las operaciones de búsqueda, inserción, deleción, sucesor y predecesor en O (lg lg n) de tiempo por elemento. Algunos sistemas de bases de datos usan árboles vEB para optimizar el rendimiento.
No estoy seguro de cómo en el tema de esta respuesta es, pero debe darle una idea de cómo las estructuras maravillosas y BSTS potentes y más generales de los árboles pueden ser.
Un ejemplo de donde se requiere un árbol binario es particiones espaciales binarios en gráficos por ordenador
http://en.wikipedia.org/wiki/Binary_space_partitioning
Se necesita un árbol binario porque el algoritmo requiere la preservación de las relaciones entre los nodos en el árbol binario . Hay muchos otros algoritmos donde la estructura del árbol es importante, por lo que una tabla hash no es una estructura apropiada.
Otra buena razón para usar un árbol binario en lugar de una tabla hash es cuando no puede generar fácilmente un hash eficiente para sus elementos de datos, pero puede generar una función de comparación.
A menudo, para el almacenamiento y recuperación simple de datos, una tabla hash es más óptima, pero más compleja de implementar.
Uno de los más ignorados es que muchos sistemas de archivos utilizan árboles binarios para administrar listados de directorios. Raramente usan un árbol binario simple, pero algunas variaciones como un árbol B. Esto se debe a que la cuestión del almacenamiento en disco del árbol es bastante importante para los detalles de la implementación. La razón por la que usan este tipo de estructura es por la eficiencia y la velocidad. Esto les permite hacer cosas como admitir miles de archivos en un directorio. Las comparaciones para los tiempos de creación y eliminación de archivos destacan las eficiencias para este aspecto del sistema de archivos.
Los árboles binarios también se usan en muchos juegos que representan objetos 3D. Nuevamente, la razón es velocidad. De hecho, la velocidad es tan importante que algunos motores de juegos, como el motor Quake, tienen el árbol binario pregenerado y preoptimizado como parte del proceso de compilación del mapa.
Una cosa a tener en cuenta es que el árbol de búsqueda binaria es eficiente en el espacio. Por ejemplo, tiene 10 enteros para almacenar y tiene una función de hash que se correlaciona de 0 a 99, luego necesita una matriz de 100 enteros. Si utilizó búsqueda binaria Árbol, entonces sería asignar sólo la cantidad de memoria como es requerido por 10 elementos
Esto probablemente debería ser un comentario, pero BST auto equilibrado (s) (log (n)) se utilizan ampliamente en lugar de BST. Las BST simples tienen el peor tiempo de inserción/remoción de O (N).
posible duplicado de [¿Cuáles son las aplicaciones de los árboles binarios?] (Http://stackoverflow.com/questions/2130416/what-are-the-applications-of-binary-trees) – nawfal