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
extiendeNodo
añadiendo un atributoaltura
. - La clase
ArbolAVL
extiendeArbolBinarioBusqueda
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.
Curso de Estructuras de Datos
Módulo 1: Introducción a las Estructuras de Datos
- ¿Qué son las Estructuras de Datos?
- Importancia de las Estructuras de Datos en la Programación
- Tipos de Estructuras de Datos
Módulo 2: Listas
- Introducción a las Listas
- Listas Enlazadas
- Listas Doblemente Enlazadas
- Listas Circulares
- Ejercicios con Listas
Módulo 3: Pilas
- Introducción a las Pilas
- Operaciones Básicas con Pilas
- Implementación de Pilas
- Aplicaciones de las Pilas
- Ejercicios con Pilas
Módulo 4: Colas
- Introducción a las Colas
- Operaciones Básicas con Colas
- Colas Circulares
- Colas de Prioridad
- Ejercicios con Colas
Módulo 5: Árboles
- Introducción a los Árboles
- Árboles Binarios
- Árboles Binarios de Búsqueda
- Árboles AVL
- Árboles B
- Ejercicios con Árboles
Módulo 6: Grafos
- Introducción a los Grafos
- Representación de Grafos
- Algoritmos de Búsqueda en Grafos
- Algoritmos de Caminos Mínimos
- Aplicaciones de los Grafos
- Ejercicios con Grafos