El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
HOME Mis cursos Finalizados
◄ Anterior
◄

Ejercicios con Árboles

Siguiente ►
►

En esta sección, vamos a poner en práctica los conceptos aprendidos sobre árboles, árboles binarios, árboles binarios de búsqueda, árboles AVL y árboles B. Los ejercicios están diseñados para reforzar tu comprensión y habilidades en la manipulación y uso de estas estructuras de datos.

Ejercicio 1: Implementación de un Árbol Binario

Descripción: Implementa una clase Nodo y una clase ArbolBinario en Python. La clase Nodo debe tener atributos para almacenar el valor del nodo y referencias a los nodos hijos izquierdo y derecho. La clase ArbolBinario debe tener métodos para insertar valores y recorrer el árbol en preorden, inorden y postorden.

Código de ejemplo:

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

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

    def insertar(self, valor):
        if self.raiz is None:
            self.raiz = Nodo(valor)
        else:
            self._insertar_recursivo(valor, self.raiz)

    def _insertar_recursivo(self, valor, nodo_actual):
        if valor < nodo_actual.valor:
            if nodo_actual.izquierdo is None:
                nodo_actual.izquierdo = Nodo(valor)
            else:
                self._insertar_recursivo(valor, nodo_actual.izquierdo)
        else:
            if nodo_actual.derecho is None:
                nodo_actual.derecho = Nodo(valor)
            else:
                self._insertar_recursivo(valor, nodo_actual.derecho)

    def preorden(self, nodo):
        if nodo:
            print(nodo.valor, end=' ')
            self.preorden(nodo.izquierdo)
            self.preorden(nodo.derecho)

    def inorden(self, nodo):
        if nodo:
            self.inorden(nodo.izquierdo)
            print(nodo.valor, end=' ')
            self.inorden(nodo.derecho)

    def postorden(self, nodo):
        if nodo:
            self.postorden(nodo.izquierdo)
            self.postorden(nodo.derecho)
            print(nodo.valor, end=' ')

# Ejemplo de uso
arbol = ArbolBinario()
valores = [10, 5, 15, 3, 7, 12, 18]
for valor in valores:
    arbol.insertar(valor)

print("Recorrido Preorden:")
arbol.preorden(arbol.raiz)
print("\nRecorrido Inorden:")
arbol.inorden(arbol.raiz)
print("\nRecorrido Postorden:")
arbol.postorden(arbol.raiz)

Explicación:

  • La clase Nodo representa un nodo en el árbol binario.
  • La clase ArbolBinario tiene métodos para insertar valores y recorrer el árbol en diferentes órdenes.
  • Los métodos de recorrido (preorden, inorden, postorden) son recursivos y visitan los nodos en el orden correspondiente.

Ejercicio 2: Árbol Binario de Búsqueda (BST)

Descripción: Implementa una clase ArbolBinarioBusqueda que herede de ArbolBinario y añade métodos para buscar y eliminar nodos.

Código de ejemplo:

class ArbolBinarioBusqueda(ArbolBinario):
    def buscar(self, valor):
        return self._buscar_recursivo(valor, self.raiz)

    def _buscar_recursivo(self, valor, nodo_actual):
        if nodo_actual is None or nodo_actual.valor == valor:
            return nodo_actual
        if valor < nodo_actual.valor:
            return self._buscar_recursivo(valor, nodo_actual.izquierdo)
        else:
            return self._buscar_recursivo(valor, nodo_actual.derecho)

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

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

    def _min_valor_nodo(self, nodo):
        actual = nodo
        while actual.izquierdo is not None:
            actual = actual.izquierdo
        return actual

# Ejemplo de uso
arbol_bst = ArbolBinarioBusqueda()
valores = [10, 5, 15, 3, 7, 12, 18]
for valor in valores:
    arbol_bst.insertar(valor)

print("Buscar 7:", arbol_bst.buscar(7))
print("Eliminar 10")
arbol_bst.eliminar(10)
print("Recorrido Inorden después de eliminar 10:")
arbol_bst.inorden(arbol_bst.raiz)

Explicación:

  • La clase ArbolBinarioBusqueda añade métodos para buscar y eliminar nodos en un árbol binario de búsqueda.
  • El método buscar encuentra un nodo con un valor específico.
  • El método eliminar elimina un nodo con un valor específico y ajusta el árbol para mantener la propiedad del BST.

Ejercicio 3: Árbol AVL

Descripción: Implementa un árbol AVL que herede de ArbolBinarioBusqueda y añade métodos para mantener el balance del árbol después de inserciones y eliminaciones.

Código de ejemplo:

class NodoAVL(Nodo):
    def __init__(self, valor):
        super().__init__(valor)
        self.altura = 1

class ArbolAVL(ArbolBinarioBusqueda):
    def insertar(self, valor):
        self.raiz = self._insertar_recursivo(self.raiz, valor)

    def _insertar_recursivo(self, nodo, valor):
        if nodo is None:
            return NodoAVL(valor)
        if valor < nodo.valor:
            nodo.izquierdo = self._insertar_recursivo(nodo.izquierdo, valor)
        else:
            nodo.derecho = self._insertar_recursivo(nodo.derecho, valor)

        nodo.altura = 1 + max(self._obtener_altura(nodo.izquierdo), self._obtener_altura(nodo.derecho))
        balance = self._obtener_balance(nodo)

        if balance > 1 and valor < nodo.izquierdo.valor:
            return self._rotar_derecha(nodo)
        if balance < -1 and valor > nodo.derecho.valor:
            return self._rotar_izquierda(nodo)
        if balance > 1 and valor > nodo.izquierdo.valor:
            nodo.izquierdo = self._rotar_izquierda(nodo.izquierdo)
            return self._rotar_derecha(nodo)
        if balance < -1 and valor < nodo.derecho.valor:
            nodo.derecho = self._rotar_derecha(nodo.derecho)
            return self._rotar_izquierda(nodo)

        return nodo

    def _obtener_altura(self, nodo):
        if nodo is None:
            return 0
        return nodo.altura

    def _obtener_balance(self, nodo):
        if nodo is None:
            return 0
        return self._obtener_altura(nodo.izquierdo) - self._obtener_altura(nodo.derecho)

    def _rotar_derecha(self, y):
        x = y.izquierdo
        T2 = x.derecho
        x.derecho = y
        y.izquierdo = T2
        y.altura = 1 + max(self._obtener_altura(y.izquierdo), self._obtener_altura(y.derecho))
        x.altura = 1 + max(self._obtener_altura(x.izquierdo), self._obtener_altura(x.derecho))
        return x

    def _rotar_izquierda(self, x):
        y = x.derecho
        T2 = y.izquierdo
        y.izquierdo = x
        x.derecho = T2
        x.altura = 1 + max(self._obtener_altura(x.izquierdo), self._obtener_altura(x.derecho))
        y.altura = 1 + max(self._obtener_altura(y.izquierdo), self._obtener_altura(y.derecho))
        return y

# Ejemplo de uso
arbol_avl = ArbolAVL()
valores = [10, 20, 30, 40, 50, 25]
for valor in valores:
    arbol_avl.insertar(valor)

print("Recorrido Inorden del Árbol AVL:")
arbol_avl.inorden(arbol_avl.raiz)

Explicación:

  • La clase NodoAVL extiende Nodo añadiendo un atributo altura.
  • La clase ArbolAVL extiende ArbolBinarioBusqueda y añade métodos para mantener el balance del árbol usando rotaciones.
  • Los métodos _rotar_derecha y _rotar_izquierda realizan las rotaciones necesarias para mantener el balance del árbol AVL.

Ejercicio 4: Árbol B

Descripción: Implementa un árbol B básico. Un árbol B es un árbol auto-balanceado en el que cada nodo puede contener más de un valor y puede tener más de dos hijos.

Código de ejemplo:

class NodoB:
    def __init__(self, t, hoja=False):
        self.t = t
        self.hoja = hoja
        self.llaves = []
        self.hijos = []

class ArbolB:
    def __init__(self, t):
        self.raiz = NodoB(t, True)
        self.t = t

    def insertar(self, k):
        raiz = self.raiz
        if len(raiz.llaves) == (2 * self.t) - 1:
            temp = NodoB(self.t)
            self.raiz = temp
            temp.hijos.insert(0, raiz)
            self._dividir_hijo(temp, 0)
            self._insertar_no_lleno(temp, k)
        else:
            self._insertar_no_lleno(raiz, k)

    def _dividir_hijo(self, x, i):
        t = self.t
        y = x.hijos[i]
        z = NodoB(t, y.hoja)
        x.hijos.insert(i + 1, z)
        x.llaves.insert(i, y.llaves[t - 1])
        z.llaves = y.llaves[t:(2 * t) - 1]
        y.llaves = y.llaves[0:t - 1]
        if not y.hoja:
            z.hijos = y.hijos[t:(2 * t)]
            y.hijos = y.hijos[0:t]

    def _insertar_no_lleno(self, x, k):
        i = len(x.llaves) - 1
        if x.hoja:
            x.llaves.append(0)
            while i >= 0 and k < x.llaves[i]:
                x.llaves[i + 1] = x.llaves[i]
                i -= 1
            x.llaves[i + 1] = k
        else:
            while i >= 0 and k < x.llaves[i]:
                i -= 1
            i += 1
            if len(x.hijos[i].llaves) == (2 * self.t) - 1:
                self._dividir_hijo(x, i)
                if k > x.llaves[i]:
                    i += 1
            self._insertar_no_lleno(x.hijos[i], k)

    def imprimir(self, x, l=0):
        print("Nivel", l, ":", x.llaves)
        l += 1
        if len(x.hijos) > 0:
            for i in x.hijos:
                self.imprimir(i, l)

# Ejemplo de uso
arbol_b = ArbolB(3)
valores = [10, 20, 5, 6, 12, 30, 7, 17]
for valor in valores:
    arbol_b.insertar(valor)

print("Árbol B:")
arbol_b.imprimir(arbol_b.raiz)

Explicación:

  • La clase NodoB representa un nodo en el árbol B.
  • La clase ArbolB tiene métodos para insertar valores y dividir nodos cuando están llenos.
  • El método imprimir muestra el contenido del árbol B.

Conclusión

En esta sección, hemos cubierto ejercicios prácticos para implementar y manipular diferentes tipos de árboles, incluyendo árboles binarios, árboles binarios de búsqueda, árboles AVL y árboles B. Estos ejercicios te ayudarán a consolidar tus conocimientos y habilidades en el uso de estas estructuras de datos fundamentales.

Asegúrate de practicar estos ejercicios y experimentar con diferentes valores y operaciones para obtener una comprensión más profunda de cómo funcionan los árboles y cómo se pueden utilizar en la programación.

◄ Anterior
◄
Siguiente ►
►
El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
© Copyright 2024. Todos los derechos reservados