Se usan ampliamente para índices en bases de datos. Al menos derivados de BST como B-Trees: el árbol de búsqueda equilibrada (B-Tree) en bases de datos SQL
Cada vez que algo como una tabla hash se vuelve poco práctico (generalmente debido a requisitos de espacio o dificultades para diseñar algoritmos hash para claves) un BST se convierte en la siguiente mejor alternativa. La ordenación de listas / matrices no es la más efectiva, especialmente cuando los elementos se agregan / eliminan constantemente.
También muchas búsquedas de palabras (por ejemplo, en cosas como correctores ortográficos) un BST se presta bien para encontrar valores “casi” correctos.
- ¿Cómo se puede calcular el número de inversiones entre dos matrices en O (N log N)?
- Funciones hash: ¿Cuál es una explicación intuitiva de los diversos algoritmos SHA? ¿Cuáles son las mejoras clave entre cada familia?
- ¿Qué estructura de datos sería mejor para encontrar el número de estudiantes dentro de un rango de altura dado de manera escalable?
- Cómo encontrar el número máximo de árboles de expansión mínima en un gráfico
- ¿Cuáles son las ventajas de los algoritmos de aprendizaje de refuerzo como LinUCB sobre otros algoritmos de predicción de CTR en línea como la regresión logística en línea?
Otros ejemplos (BSTs puros o estructuras de árbol derivadas) incluyen:
- Partición de espacio binario: se usa ampliamente en juegos en 3D para determinar qué objetos representar cuando están en el cono de vista.
- Intentos binarios – ordenando iptables en enrutadores
- Montones: colas prioritarias de alta eficiencia, por ejemplo, colas de calidad de servicio en enrutadores.
- Árboles de codificación de Huffman: muchos algoritmos de compresión los utilizan. Incluso compresiones sin pérdida como JPG
- El código del compilador para las instrucciones de cambio tiende a revertir a BST si los casos para encender no son contiguos.
Hay muchos ejemplos de este tipo, probablemente demasiados para enumerar. Incluso llega al punto en que las bibliotecas estándar las usan dentro de sus implementaciones. Por ejemplo, todas las formas de tablas y conjuntos hash ordenados usan un BST (std :: map y std :: set de C ++ definitivamente lo hacen, al igual que muchos otros como java.util.Set de JVM).
Los árboles (en general, no solo binarios) se utilizan en todo el espectáculo. Solo piense en las estructuras de ruta en un disco (probablemente el uso más ubicuo de una estructura de árbol). De hecho, todos estos son Nary-Trees, es decir, un “padre” con múltiples “hijos”, a veces esto se conoce como una jerarquía.
