# Árboles Binarios de Búsqueda (ABB) ¡Hola! Bienvenido a este material de estudio sobre los **Árboles Binarios de Búsqueda (ABB)**. Esta es una estructura de datos fundamental en la informática, diseñada para almacenar información de una manera que permite encontrar, añadir y quitar elementos de forma muy eficiente. Imagina una biblioteca donde los libros no están ordenados al azar, sino siguiendo un criterio que facilita encontrar cualquier título rápidamente. Un ABB funciona de manera similar con los datos. ## ¿Qué es un Árbol Binario de Búsqueda? Un ABB es un tipo especial de **árbol binario**. Esto significa que cada "nodo" (donde se guarda un dato) en el árbol puede tener, como máximo, dos "hijos": uno a la izquierda y otro a la derecha. > Un **nodo** es un elemento en una estructura de datos de árbol que contiene un valor y enlaces a otros nodos (sus hijos o su padre). ### La Propiedad de Ordenación Fundamental Lo que realmente distingue a un ABB y lo hace tan útil es su **propiedad de ordenación**. Esta propiedad establece reglas muy específicas sobre cómo se distribuyen los valores en el árbol: * **Menores a la izquierda:** Para cualquier nodo, todos los valores en su subárbol izquierdo (todos sus descendientes a la izquierda) deben ser **menores** que el valor del propio nodo. * **Mayores a la derecha:** Para cualquier nodo, todos los valores en su subárbol derecho (todos sus descendientes a la derecha) deben ser **mayores** que el valor del propio nodo. * **Recursividad:** Tanto el subárbol izquierdo como el subárbol derecho de un nodo son, a su vez, Árboles Binarios de Búsqueda. Did you know: La recursividad en la definición de un ABB es clave, ya que significa que las propiedades que se aplican al árbol completo también se aplican a cada uno de sus subárboles. Esta propiedad de ordenación es la que permite realizar búsquedas muy rápidas. No necesitas revisar cada nodo; en cada paso, sabes exactamente en qué dirección del árbol continuar (izquierda o derecha) para encontrar tu valor o determinar que no está presente. ## Operaciones Fundamentales en un ABB Las operaciones más importantes en un ABB son la búsqueda, la inserción y la eliminación de nodos. La eficiencia de estas operaciones es lo que hace que los ABB sean tan valiosos en la práctica. ### 1. Búsqueda de un Nodo Buscar un valor en un ABB es como jugar un juego de "mayor o menor". Empiezas en la **raíz** (el primer nodo del árbol) y comparas el valor que buscas con el valor del nodo actual. **Algoritmo de Búsqueda:** 1. **Inicio:** Empieza en el nodo raíz. 2. **Vacío o nulo:** Si el árbol está vacío o si llegas a un punto donde el nodo actual es nulo (es decir, no hay más nodos en esa dirección), el valor no se encuentra en el árbol. 3. **Encontrado:** Si el valor buscado es **igual** al valor del nodo actual, ¡lo has encontrado! 4. **Menor:** Si el valor buscado es **menor** que el valor del nodo actual, debes buscar en el **subárbol izquierdo**. 5. **Mayor:** Si el valor buscado es **mayor** que el valor del nodo actual, debes buscar en el **subárbol derecho**. **Ejemplo de Búsqueda:** Supongamos que tenemos un ABB y queremos buscar el número $25$. El árbol podría lucir algo así (solo los valores): `{30, 15, 40, 10, 20, 35, 50, 25}`. 1. Comenzamos en la raíz, que es el nodo con valor $30$. * $25 < 30$, así que nos movemos al hijo izquierdo. 2. Llegamos al nodo con valor $15$. * $25 > 15$, así que nos movemos al hijo derecho. 3. Llegamos al nodo con valor $20$. * $25 > 20$, así que nos movemos al hijo derecho. 4. Llegamos al nodo con valor $25$. * $25 = 25$, ¡hemos encontrado el valor! Este proceso demuestra cómo la propiedad de ordenación elimina la necesidad de revisar una gran parte del árbol, haciendo la búsqueda muy eficiente. ### 2. Inserción de un Nodo Para añadir un nuevo valor a un ABB, seguimos un camino muy similar al de la búsqueda, pero en lugar de detenernos cuando encontramos el va