# El árbol binario de búsqueda - Sitio: Ikusmira — enciclopedia en castellano de ciencias sociales y humanidades - URL canónica: https://ikusmira.org/p/el-arbol-binario-de-busqueda/ - Categoría: Informática - Publicado: 2026-09-04 - Autoría: Eneko Sarasola (redacción de Ikusmira) - Política editorial (autoría, revisión, correcciones, financiación): https://ikusmira.org/politica-editorial/ El **árbol binario de búsqueda** es una estructura de datos en la que cada elemento tiene como mucho dos hijos, todo lo que cuelga a su izquierda es menor que él y todo lo que cuelga a su derecha es mayor. Esa única regla hace que buscar un valor sea como buscar en un diccionario: se compara con la raíz, se baja a la izquierda o a la derecha según el resultado, y se repite, descartando en cada paso la mitad del árbol que no puede contenerlo. Si el árbol está bien repartido, encontrar cualquiera de un millón de elementos cuesta unas veinte comparaciones. Si está mal repartido, puede costar un millón. Toda la historia de esta estructura, desde 1960 hasta hoy, es la historia de cómo mantenerlo bien repartido. La figura de esta página construye el árbol delante del lector. Al insertar quince números al azar, cada uno baja desde la raíz hasta encontrar su sitio, y el resultado es un árbol frondoso de cuatro o cinco niveles. Al vaciarlo e insertar los números del 1 al 15 *en orden*, cada nuevo número es mayor que todos los anteriores, cae siempre a la derecha, y el árbol se convierte en una hilera inclinada de quince niveles: una lista disfrazada, en la que buscar el 15 cuesta quince comparaciones en lugar de cuatro. Son las mismas quince claves; lo único que ha cambiado es el orden de llegada. La figura anota la altura del árbol junto a la mínima posible, y la diferencia entre ambas es la medida del problema. El caso degenerado no es un artificio de laboratorio. Los datos que llegan a un programa suelen venir ordenados o casi: registros por fecha, nombres de un fichero alfabético, números de serie consecutivos. Peter Windley describió la estructura en 1960 y Thomas Hibbard analizó en 1962 lo que ocurre con claves en orden aleatorio: la altura esperada es de unas 1,39 veces el logaritmo en base 2 del número de claves, poco más que la mínima, así que con datos realmente barajados el árbol se comporta bien solo. Pero el promedio no protege del caso concreto, y el caso concreto malo es el más común en la práctica. Donald Knuth dedica a esto buena parte de la sección sobre árboles del tercer volumen de *The Art of Computer Programming*, y la conclusión es que un árbol de búsqueda sin más es una estructura para datos que uno sabe que llegan desordenados. La solución llegó también en 1962, desde Moscú. Georgy Adelson-Velsky y Evgenii Landis propusieron mantener, en cada nodo, la diferencia de altura entre su subárbol izquierdo y el derecho, y no permitir nunca que pase de uno. Cuando una inserción rompe esa condición, se arregla con una *rotación*: un reajuste local de tres nodos que conserva el orden y baja al lado alto un nivel. La figura lo hace al activar el botón AVL, y el resultado es que los números del 1 al 15 en orden producen exactamente el mismo árbol perfecto que producirían insertados en el orden ideal, con el 8 en la raíz y cuatro niveles. El precio son las rotaciones, que la figura cuenta, y algo de memoria por nodo para guardar las alturas. La garantía es que la altura nunca supera 1,44 veces el logaritmo del número de claves, sea cual sea el orden de llegada. Los árboles AVL fueron el primero de una familia. Rudolf Bayer propuso en 1972 los árboles rojo-negro, que relajan la condición de equilibrio a cambio de menos rotaciones y son los que usan las bibliotecas estándar de C++ y Java para sus mapas ordenados; el mismo Bayer inventó ese año, con Edward McCreight, los árboles B, que ponen muchas claves en cada nodo para minimizar accesos a disco y sostienen los índices de casi todas las bases de datos. Daniel Sleator y Robert Tarjan propusieron en 1985 los árboles biselados, que no guardan nada sobre el equilibrio y en cambio mueven a la raíz cada clave que se busca, de modo que las claves frecuentes quedan arriba; no garantizan nada sobre una búsqueda concreta pero sí sobre cualquier secuencia larga de ellas, y son un ejemplo temprano del análisis amortizado. Lo que hace útil al árbol de búsqueda frente a la tabla hash, que encuentra cualquier clave en tiempo constante, es que el árbol conserva el orden. Recorrerlo de izquierda a derecha produce las claves ordenadas; encontrar la clave más pequeña mayor que un valor dado, o todas las que están en un intervalo, cuesta lo mismo que una búsqueda; y el peor caso, con equilibrio, está garantizado y no solo prometido en promedio. Por eso los dos conviven: la tabla hash para preguntar «¿está?» y el árbol para preguntar «¿qué hay entre esto y aquello?». La figura enseña el precio de esa capacidad, que es el trabajo de mantener el árbol en forma, y también lo pequeño que es ese precio cuando se paga en cada inserción en lugar de dejar que la deuda crezca. ## Fuentes - Peter F. Windley — *Trees, Forests and Rearranging*, The Computer Journal 3(2) (1960) - Thomas N. Hibbard — *Some Combinatorial Properties of Certain Trees with Applications to Searching and Sorting*, Journal of the ACM 9(1) (1962) - Georgy M. Adelson-Velsky y Evgenii M. Landis — *Un algoritmo para la organización de la información (en ruso)*, Doklady Akademii Nauk SSSR 146 (1962) - Rudolf Bayer — *Symmetric Binary B-Trees: Data Structure and Maintenance Algorithms*, Acta Informatica 1(4) (1972) - Daniel D. Sleator y Robert E. Tarjan — *Self-Adjusting Binary Search Trees*, Journal of the ACM 32(3) (1985) - Donald E. Knuth — *The Art of Computer Programming, vol. 3: Sorting and Searching, sección 6.2*, Addison-Wesley, Reading (Massachusetts) (1973) --- Cómo citar: Sarasola, Josemari (2026). «El árbol binario de búsqueda». Ikusmira. https://ikusmira.org/p/el-arbol-binario-de-busqueda/ Índice del sitio para modelos: https://ikusmira.org/llms.txt