Introducción

Un Árbol Binario de Búsqueda (ABB) es una estructura de datos en forma de árbol binario que tiene la propiedad de que, para cada nodo, todos los nodos en su subárbol izquierdo tienen valores menores y todos los nodos en su subárbol derecho tienen valores mayores. Esta propiedad permite realizar operaciones de búsqueda, inserción y eliminación de manera eficiente.

Propiedades de los Árboles Binarios de Búsqueda

Nodo Raíz: El nodo superior del árbol.
Nodo Hijo: Un nodo que es descendiente directo de otro nodo.
Nodo Padre: Un nodo que tiene uno o más nodos hijos.
Subárbol Izquierdo: Todos los nodos con valores menores que el nodo padre.
Subárbol Derecho: Todos los nodos con valores mayores que el nodo padre.
Hojas: Nodos que no tienen hijos.

Operaciones Básicas

Búsqueda

Para buscar un valor en un ABB, se compara el valor con el nodo actual y se decide si se debe mover al subárbol izquierdo o derecho, repitiendo el proceso hasta encontrar el valor o llegar a un nodo hoja.

class Nodo:
    def __init__(self, valor):
        self.valor = valor
        self.izquierdo = None
        self.derecho = None

def buscar(nodo, valor):
    if nodo is None or nodo.valor == valor:
        return nodo
    if valor < nodo.valor:
        return buscar(nodo.izquierdo, valor)
    else:
        return buscar(nodo.derecho, valor)

# Ejemplo de uso
raiz = Nodo(10)
raiz.izquierdo = Nodo(5)
raiz.derecho = Nodo(15)

resultado = buscar(raiz, 15)
print(resultado.valor if resultado else "No encontrado")

Inserción

Para insertar un valor en un ABB, se compara el valor con el nodo actual y se decide si se debe mover al subárbol izquierdo o derecho, repitiendo el proceso hasta encontrar una posición vacía donde insertar el nuevo nodo.

def insertar(nodo, valor):
    if nodo is None:
        return Nodo(valor)
    if valor < nodo.valor:
        nodo.izquierdo = insertar(nodo.izquierdo, valor)
    else:
        nodo.derecho = insertar(nodo.derecho, valor)
    return nodo

# Ejemplo de uso
raiz = Nodo(10)
insertar(raiz, 5)
insertar(raiz, 15)

Eliminación

Eliminar un nodo en un ABB puede ser más complejo, ya que hay tres casos a considerar:

El nodo a eliminar es una hoja.
El nodo a eliminar tiene un solo hijo.
El nodo a eliminar tiene dos hijos.

def eliminar(nodo, valor):
    if nodo is None:
        return nodo
    if valor < nodo.valor:
        nodo.izquierdo = eliminar(nodo.izquierdo, valor)
    elif valor > nodo.valor:
        nodo.derecho = eliminar(nodo.derecho, valor)
    else:
        if nodo.izquierdo is None:
            return nodo.derecho
        elif nodo.derecho is None:
            return nodo.izquierdo
        temp = encontrar_minimo(nodo.derecho)
        nodo.valor = temp.valor
        nodo.derecho = eliminar(nodo.derecho, temp.valor)
    return nodo

def encontrar_minimo(nodo):
    actual = nodo
    while actual.izquierdo is not None:
        actual = actual.izquierdo
    return actual

# Ejemplo de uso
raiz = Nodo(10)
insertar(raiz, 5)
insertar(raiz, 15)
eliminar(raiz, 10)

Ejercicios Prácticos

Ejercicio 1: Implementar un ABB

Implementa un Árbol Binario de Búsqueda y realiza las operaciones de inserción, búsqueda y eliminación.

class Nodo:
    def __init__(self, valor):
        self.valor = valor
        self.izquierdo = None
        self.derecho = None

class ABB:
    def __init__(self):
        self.raiz = None

    def insertar(self, valor):
        self.raiz = insertar(self.raiz, valor)

    def buscar(self, valor):
        return buscar(self.raiz, valor)

    def eliminar(self, valor):
        self.raiz = eliminar(self.raiz, valor)

# Ejemplo de uso
arbol = ABB()
arbol.insertar(10)
arbol.insertar(5)
arbol.insertar(15)
print(arbol.buscar(15).valor if arbol.buscar(15) else "No encontrado")
arbol.eliminar(10)
print(arbol.buscar(10).valor if arbol.buscar(10) else "No encontrado")

Ejercicio 2: Altura del ABB

Implementa una función para calcular la altura de un ABB.

def altura(nodo):
    if nodo is None:
        return 0
    else:
        altura_izquierda = altura(nodo.izquierdo)
        altura_derecha = altura(nodo.derecho)
        return max(altura_izquierda, altura_derecha) + 1

# Ejemplo de uso
raiz = Nodo(10)
insertar(raiz, 5)
insertar(raiz, 15)
print(altura(raiz))  # Salida: 2

Conclusión

En esta sección, hemos aprendido sobre los Árboles Binarios de Búsqueda, sus propiedades y operaciones básicas como búsqueda, inserción y eliminación. También hemos implementado estas operaciones en Python y realizado algunos ejercicios prácticos para reforzar los conceptos aprendidos. En el siguiente módulo, exploraremos los Árboles AVL, una variante de los ABB que se auto-balancea para mantener una altura mínima y mejorar la eficiencia de las operaciones.

Árboles Binarios de Búsqueda

Introducción

Propiedades de los Árboles Binarios de Búsqueda

Operaciones Básicas

Búsqueda

Inserción

Eliminación

Ejercicios Prácticos

Ejercicio 1: Implementar un ABB

Ejercicio 2: Altura del ABB

Conclusión

Curso de Estructuras de Datos

Módulo 1: Introducción a las Estructuras de Datos

Módulo 2: Listas

Módulo 3: Pilas

Módulo 4: Colas

Módulo 5: Árboles

Módulo 6: Grafos

Módulo 7: Conclusiones y Recursos Adicionales