Árboles de búsqueda
Los árboles de búsqueda almacenan claves ordenadas en una estructura jerárquica de modo que la búsqueda, inserción y eliminación siguen una ruta de la raíz a la hoja; las variantes autoequilibradas mantienen esa ruta corta para garantizar operaciones en tiempo logarítmico.
Definition
Un árbol de búsqueda es una estructura de datos con forma de árbol que mantiene las claves en orden ascendente de acuerdo con una invariante de ordenación por nodo, lo que permite una búsqueda, inserción, eliminación y consultas basadas en el orden eficientes; un árbol de búsqueda equilibrado restringe adicionalmente su forma para que la altura se mantenga logarítmica en el número de claves.
Scope
Este tema abarca las estructuras de diccionario ordenadas basadas en árboles: el árbol de búsqueda binario y su invariante de ordenación, los esquemas de autoequilibrio que limitan la altura (AVL, rojo-negro y otros), y los árboles equilibrados de múltiples vías como los árboles B diseñados para almacenamiento externo. Aborda las operaciones que estas estructuras soportan más allá de la simple búsqueda —predecesor, sucesor, consultas de rango y recorrido ordenado— y las contrasta con las tablas hash, que no preservan el orden.
Core questions
- ¿Cómo la invariante de ordenación del árbol de búsqueda binario convierte la búsqueda en un recorrido de la raíz a la hoja?
- ¿Por qué un árbol desequilibrado puede degradarse a tiempo lineal, y cómo lo previene el equilibrio?
- ¿Qué rotaciones o reglas estructurales mantienen equilibrados los árboles AVL y rojo-negro?
- ¿Por qué los árboles B son adecuados para el almacenamiento en disco y bases de datos en lugar de los árboles binarios?
- ¿Cuándo las operaciones que preservan el orden justifican el costo adicional sobre una tabla hash?
Key concepts
- invariante del árbol de búsqueda binario
- rotaciones de árbol
- árboles AVL
- árboles rojo-negro
- árboles B
- altura y equilibrio del árbol
- recorrido en orden
- consultas de rango y sucesor
Key theories
- El equilibrio de altura garantiza operaciones logarítmicas
- Al mantener una invariante de equilibrio mediante rotaciones o reglas estructurales, los árboles autoequilibrados mantienen una altura O(log n), garantizando una búsqueda, inserción y eliminación en el peor de los casos de O(log n) independientemente del orden de entrada.
- Árboles multi-vía para memoria externa
- Los árboles B almacenan muchas claves por nodo para coincidir con los tamaños de los bloques de disco, minimizando el número de accesos lentos a la memoria externa; esto los convierte en la estructura estándar para bases de datos y sistemas de archivos.
Clinical relevance
Los árboles de búsqueda son fundamentales para los sistemas que necesitan acceso ordenado: los árboles rojo-negro implementan mapas y conjuntos ordenados en las bibliotecas estándar, los árboles B y sus variantes son la estructura de índice dominante en las bases de datos relacionales y los sistemas de archivos, y los árboles equilibrados soportan consultas de rango, programación de intervalos y estructuras de búsqueda geométrica.
History
Los árboles AVL, los primeros árboles de búsqueda binarios autoequilibrados, fueron introducidos por Adelson-Velsky y Landis en 1962. Bayer y McCreight introdujeron los árboles B en 1972 para grandes índices ordenados, y los árboles rojo-negro fueron desarrollados por Guibas y Sedgewick en 1978 como un esquema de equilibrio práctico, convirtiéndose en la base de muchas implementaciones de bibliotecas estándar.
Key figures
- Georgy Adelson-Velsky
- Evgenii Landis
- Rudolf Bayer
- Robert Sedgewick
- Robert Tarjan
Related topics
Seminal works
- bayer1972
- cormen2009
Frequently asked questions
- ¿Por qué no usar siempre una tabla hash en lugar de un árbol de búsqueda?
- Las tablas hash ofrecen búsquedas promedio más rápidas pero no ordenación. Los árboles de búsqueda mantienen las claves ordenadas, lo que permite consultas de rango, iteración ordenada y búsquedas de predecesor/sucesor en O(log n), lo que las tablas hash no pueden hacer de manera eficiente. La elección depende de si el orden es importante.
- ¿Por qué las bases de datos usan árboles B en lugar de árboles de búsqueda binarios?
- Los árboles B agrupan muchas claves en cada nodo para que coincidan con el tamaño de un bloque de disco, por lo que una búsqueda toca muchos menos bloques de memoria externa lentos que un árbol binario con el mismo número de claves. Esto minimiza la E/S, que domina el rendimiento en bases de datos y sistemas de archivos.