Árboles Binarios de Búsqueda (ABB): Binary Search Tree

Introducción

Un árbol binario de búsqueda (ABB) es un tipo especial de árbol binario ampliamente utilizado en informática. La principal característica que define un ABB es que cada nodo sigue una regla de orden:

• Todos los elementos en el subárbol izquierdo son menores que la clave del nodo.
• Todos los elementos en el subárbol derecho son mayores que la clave del nodo.

Esta estructura permite realizar operaciones como búsqueda, inserción y eliminación de manera eficiente.

Este es un árbol de búsqueda binario dado que la clave del subárbol izquierdo es más pequeña que el nodo raíz, siempre el nodo de la izquierda es más pequeño que el propio nodo, y el de la derecha es más grande que el propio valor del nodo.

Un árbol de búsqueda puede almacenar elementos que cumplan una relación de orden. Debe haber una forma de ordenar los elementos. Ejemplos: almacenar enteros, cadenas de caracteres por orden lexicográfico, almacenar objetos siempre que se identifiquen por alguna clave que si sea ordenable (libros usando isbn, personas usando código de empleado).

---

Propiedades del Árbol Binario de Búsqueda

1. Raíz y subárboles:
   • Cada ABB tiene una raíz (el nodo principal).
   • Los subárboles izquierdo y derecho también deben ser ABB.
2. Relación de orden:
   • Los valores en el subárbol izquierdo son menores que la raíz.
   • Los valores en el subárbol derecho son mayores que la raíz.
3. Elementos comparables:
   • Los datos almacenados deben ser comparables (por ejemplo, números, cadenas lexicográficas o claves de objetos).
4. Aplicaciones:
   • Bases de datos (usando claves ordenables como ISBN, DNI, etc.).
   • Estructuras recursivas en algoritmos.

---

Operaciones Básicas

1. Búsqueda

La búsqueda en un ABB utiliza la propiedad de orden para reducir el espacio de búsqueda. Si la clave buscada no coincide con la raíz, se decide recursivamente si buscar en el subárbol izquierdo o derecho.

Algoritmo:

1. Si el árbol está vacío, devolver null (no encontrado).
2. Si la clave buscada coincide con la raíz, devolver la raíz.
3. Si la clave es menor que la raíz, buscar en el subárbol izquierdo.
4. Si la clave es mayor, buscar en el subárbol derecho.

Pseudo-código:

buscar(arbol, clave):
    si arbol es null:
        devolver null
    si arbol.raiz == clave:
        devolver arbol.raiz
    si clave < arbol.raiz:
        devolver buscar(arbol.izquierdo, clave)
    si clave > arbol.raiz:
        devolver buscar(arbol.derecho, clave)

2. Inserción

La inserción en un ABB también utiliza la propiedad de orden para ubicar el lugar correcto para el nuevo nodo.

Reglas:

1. Si el árbol está vacío, el nuevo elemento se convierte en la raíz.
2. Si la clave es menor que la raíz, insertar recursivamente en el subárbol izquierdo.
3. Si la clave es mayor, insertar recursivamente en el subárbol derecho.
4. Considerar si se permiten duplicados. Si no, generar un error al intentar insertar un valor existente.

Pseudo-código:

insertar(arbol, clave):
    si arbol es null:
        devolver Nodo(clave)
    si clave < arbol.raiz:
        arbol.izquierdo = insertar(arbol.izquierdo, clave)
    si clave > arbol.raiz:
        arbol.derecho = insertar(arbol.derecho, clave)
    devolver arbol

Ejemplo Gráfico:

1. Insertar 8 en un árbol vacío:

   • Raíz = 8.

2. Insertar 10:

   • Comparar con la raíz (8). Como 10 > 8, insertar en el subárbol derecho.

3. Insertar 4:

   • Comparar con la raíz (8). Como 4 < 8, insertar en el subárbol izquierdo.

4. Insertar 6

   • Comparar ocn la raiz. Como 6 < 8, nos vamos al subárbol izquierdo. Como 6 > 4 insertamos en la derecha el nodo

   

3. Eliminación

La eliminación es más compleja porque puede requerir reorganizar el árbol para mantener la propiedad de orden. Existen tres casos principales:

1. Nodo sin hijos: Simplemente eliminar el nodo y hacer que la referencia del padre apunte a null

1. Nodo con un hijo: Reemplazar el nodo con su único hijo. Hacer que el padre del nodo a eliminar apunte al hijo del nodo a eliminar

1. Nodo con dos hijos: Reemplazar el nodo con su sucesor inorden (el más pequeño del subárbol derecho) o su predecesor inorden (el más grande del subárbol izquierdo).

A continuación se muestran las dos formas en las que se pueden hacer:

El menor del subárbol derecho es el 41, 41 se convierte en la raíz, se borra el otro 41

En el segundo ejemplo el mayor del árbol derecho es el 16, la raíz es 16 y se borra el nodo 16.

---

Implementación en Lenguajes de Programación

Lenguajes orientados a objetos (Java, Python)

• Se recomienda usar clases para representar nodos y el árbol completo.
• Los subárboles pueden representarse como atributos de la clase nodo.
• Para insertar o buscar, se pueden utilizar métodos recursivos dentro de la clase.

---

Consideraciones Finales

1. Eficiencia:
   • En el mejor caso (ABB balanceado), las operaciones tienen complejidad O(log n).
   • En el peor caso (ABB degenerado en una lista), la complejidad es O(n).