Árbol binario de búsqueda
Binary search tree
- Fecha
- c. 1960 · fiabilidad media
- Lugar
- Londres, Inglaterra, Reino Unido
- Autoría
- P. F. Windley, Andrew D. Booth, Andrew Colin y Thomas N. Hibbard (descubierto de forma independiente por varios investigadores hacia 1960)
- Ámbito
- Saber y símbolos
Qué es
Varios investigadores llegaron de forma independiente hacia 1960 a la misma estructura de datos: un árbol en el que cada nodo tiene como mucho dos hijos y el valor de cada uno determina si va a la izquierda o a la derecha, lo que permite buscar, insertar y borrar elementos ordenados de forma mucho más eficiente que en una lista. Conway Berners-Lee y David Wheeler lo aplicaron ese mismo año al almacenamiento de datos en cinta magnética.
El crédito está repartido entre varios investigadores que llegaron a la misma idea casi a la vez, tanto en el Reino Unido como en Estados Unidos.
A qué dio paso
- Árboles autobalanceados (AVL, 1962)
- Bases de datos e índices modernos
Se apoya en
- Búsqueda binaria en listas ordenadas