¿Cuál es el uso práctico de los árboles de búsqueda binarios?

Estas son algunas de las aplicaciones de los árboles de búsqueda binarios:

BST se puede usar para la codificación Huffman que se usa para algoritmos de compresión de medios como .jpeg, .mp3.

BST se puede usar para implementar la cola de prioridad que a su vez se usa para administrar el ancho de banda en el enrutador de red.

BST se puede utilizar para implementar la partición de espacio binario que se requiere en los gráficos de computadora. Esto utiliza Binary Search. Particionamiento del espacio binario – Wikipedia

CouchDB, como la mayoría de las otras bases de datos, utiliza árboles de búsqueda binarios. Aquí hay un artículo que describe cómo lo usa. Puede que le resulte interesante.

Referencia:

http://www.stackoverflow.com

http://www.wikipedia.com

imagen del árbol de búsqueda binaria:

1.Cuando aplica el recorrido transversal en el árbol de búsqueda binario, obtiene una lista ordenada en orden ascendente. El costo transversal del pedido será O (n).

¿Cuál es el uso práctico de los árboles de búsqueda binarios?

Como era de esperar, son para buscar.

En particular, son para cuando desea buscar una y otra vez el mismo tipo de cosas, al igual que las búsquedas binarias en matrices. Si su BST está equilibrado, tanto buscar en un BST como en una matriz le dará una búsqueda O (log n).

Entonces, ¿por qué usarías un BST en lugar de una matriz?

Si algunos de sus datos van a cambiar, insertar valores, eliminar valores o intentar mover cosas en una matriz es bastante doloroso. Se produce una gran cantidad de copias cuando tiene una gran cantidad de valores. (O (n) copiando para agregar un valor en una ubicación arbitraria para una matriz; O (log n) tiempo promedio para un BST, pero O (n) en el peor de los casos).

Tanto las búsquedas BST como las binarias en las matrices le permitirán encontrar valores cercanos a lo que desea si el valor que desea no está allí. Si no le importa, puede considerar el almacenamiento hash (una tabla hash, un conjunto hash o lo que sea compatible con su idioma). La recuperación de la tabla hash es O (1), y la inserción se amortiza O (1). Puede responder “¿Está 50 en mi conjunto de valores?” Realmente rápido, pero no hay forma de decir “¿Cuál es el valor más cercano a 50?” Sin pasar por cada elemento y mirar (O (n)).

La búsqueda binaria básicamente lo ayuda a reducir el espacio de búsqueda a la mitad. Tome un ejemplo para encontrar sqrt de un número dado. La mejor forma de fuerza es comenzar desde 1 y seguir comprobando i * i. Pero si lo analiza, puede realizar una búsqueda binaria aquí y puede reducir el espacio de búsqueda a la mitad. Por lo tanto, calcula mid y comprueba mid * mid. Si es igual al número dado, entonces encontraste el sqrt. Si es menor que el número dado, verifique desde mi + 1 hasta el final, de lo contrario, comience a mediados de 1. Puede optimizarlo aún más asignándolo con el número / 2.

BST se utiliza en muchas aplicaciones de búsqueda en las que los datos ingresan constantemente y salen, como los mapas y los objetos establecidos en muchas bibliotecas de idiomas. Un bst se puede utilizar para implementar un algoritmo de clasificación simple. Esto también se puede servir como cola prioritaria.

No estoy seguro de lo que quieres decir con “práctico”. Son muy prácticos para hacer búsquedas binarias :-). Siempre que se mantengan equilibrados, admiten una búsqueda e inserción eficientes. También admiten cosas como min, max, predecesor y sucesor de manera eficiente.

Las dos mejores formas de encontrar cosas (no al azar) es hacer coincidir exactamente lo que necesita o encontrar algo cercano a lo que necesita.

Las tablas hash son excelentes para la primera pero no para la segunda. También son bastante baratos de implementar.

Los árboles de búsqueda (incluidos los binarios) son buenos para coincidencias exactas y cercanas, pero su implementación es más costosa.

Los árboles de búsqueda binarios son una excelente manera de comenzar a comprender cómo las cosas pueden coincidir estrechamente en los datos que le interesan.