Binary search tree
Árbol binario de búsqueda
- Date
- c. 1960 · confidence medium
- Place
- London, England, United Kingdom
- Credited to
- P. F. Windley, Andrew D. Booth, Andrew Colin and Thomas N. Hibbard (independently discovered by several researchers around 1960)
- Field
- Knowledge & symbols
What it is
Several researchers independently arrived around 1960 at the same data structure: a tree where each node has at most two children and each value determines whether it goes left or right, allowing ordered elements to be searched, inserted and deleted far more efficiently than in a list. Conway Berners-Lee and David Wheeler applied it that same year to storing data on magnetic tape.
Credit is shared among several researchers who arrived at the same idea almost simultaneously, both in the United Kingdom and the United States.
What it led to
- Self-balancing trees (AVL, 1962)
- Modern databases and indexes
Built on
- Binary search on sorted lists