Un árbol es una estructura de datos jerárquica que tiene varios nodos conectados por enlaces. Te invito a que sigas leyendo para conocer más acerca de ello, sus métodos y aplicaciones en la vida real.
Anteriormente conociste otras estructuras de datos. En este post, te comparto mis aprendizajes sobre los árboles en la programación. Y se usará python para dar los ejemplos.
¿Qué es un Árbol en Programación?
Imagina por un momento que estás explorando un frondoso bosque. Cada árbol que ves tiene un tronco principal del que surgen ramas, y de estas ramas nacen otras más pequeñas. Esta estructura natural es exactamente lo que inspiró a los programadores. Ellos crearon la estructura de datos de árboles en informática.
Un árbol es una estructura de datos jerárquica que consta de nodos conectados por enlaces. Al igual que un árbol real, tiene:
- Una raíz: El nodo superior del árbol.
- Nodos padres: Nodos que tienen otros nodos debajo de ellos.
- Nodos hijos: Nodos que están conectados a un nodo superior.
- Hojas: Nodos que no tienen hijos (las hojas en las puntas de las ramas de un árbol real no tienen).
- Rama: Son aquellos nodos que no son la raíz y tienen al menos un hijo.
Dato curioso: A un gráfo se le puede ver cómo un arbol no dirigido aciclico.
Un Ejemplo Práctico: El Árbol Genealógico
Piensa en tu árbol genealógico familiar. Tú podrías ser un nodo. Tus padres serían nodos padres conectados a ti. Tus hermanos serían nodos hermanos. Tus abuelos estarían en un nivel superior. Esta estructura familiar es un perfecto ejemplo de cómo funciona un árbol en programación.
Implementación de un Árbol en Python
Veamos cómo podemos implementar un árbol binario simple en Python:
class Nodo:
def __init__(self, valor):
self.valor = valor
self.izquierda = None
self.derecha = None
class ArbolBinario:
def __init__(self):
self.raiz = None
def insertar(self, valor):
if not self.raiz:
self.raiz = Nodo(valor)
else:
self._insertar_recursivo(self.raiz, valor)
def _insertar_recursivo(self, nodo, valor):
if valor < nodo.valor:
if nodo.izquierda is None:
nodo.izquierda = Nodo(valor)
else:
self._insertar_recursivo(nodo.izquierda, valor)
else:
if nodo.derecha is None:
nodo.derecha = Nodo(valor)
else:
self._insertar_recursivo(nodo.derecha, valor)
Métodos Comunes en Árboles
1. Insertar (Insert)
El método de inserción añade un nuevo nodo al árbol. Mantiene la estructura y el orden del árbol binario de búsqueda.
En un árbol binario de búsqueda (BST), la inserción tiene una complejidad de O(h). La variable h es la altura del árbol. Y el peor caso, es cuando el árbol está desequilibrado. Esto puede ser O(n), donde n es el número de nodos.
def insertar(self, valor):
if not self.raiz:
self.raiz = Nodo(valor)
else:
self._insertar_recursivo(self.raiz, valor)
def _insertar_recursivo(self, nodo, valor):
if valor < nodo.valor:
if nodo.izquierda is None:
nodo.izquierda = Nodo(valor)
else:
self._insertar_recursivo(nodo.izquierda, valor)
else:
if nodo.derecha is None:
nodo.derecha = Nodo(valor)
else:
self._insertar_recursivo(nodo.derecha, valor)
2. Buscar (Search)
El método de búsqueda recorre el árbol para encontrar un nodo con un valor específico.
La búsqueda en un árbol binario de búsqueda (BST) tiene una complejidad de O(h). La complejidad depende de h, que es la altura del árbol. En el peor caso, esto puede ser O(n).
def buscar(self, valor):
return self._buscar_recursivo(self.raiz, valor)
def _buscar_recursivo(self, nodo, valor):
if nodo is None or nodo.valor == valor:
return nodo
if valor < nodo.valor:
return self._buscar_recursivo(nodo.izquierda, valor)
return self._buscar_recursivo(nodo.derecha, valor)
3. Eliminar (Delete)
El método de eliminación remueve un nodo del árbol, manteniendo la estructura del árbol binario de búsqueda.
Al igual que la inserción, la eliminación en un árbol binario de búsqueda (BST) tiene una complejidad de O(h). h es la altura del árbol. En el peor caso, esto puede ser O(n).
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.izquierda = self._eliminar_recursivo(nodo.izquierda, valor)
elif valor > nodo.valor:
nodo.derecha = self._eliminar_recursivo(nodo.derecha, valor)
else:
if nodo.izquierda is None:
return nodo.derecha
elif nodo.derecha is None:
return nodo.izquierda
temp = self._minimo_valor_nodo(nodo.derecha)
nodo.valor = temp.valor
nodo.derecha = self._eliminar_recursivo(nodo.derecha, temp.valor)
return nodo
def _minimo_valor_nodo(self, nodo):
actual = nodo
while actual.izquierda is not None:
actual = actual.izquierda
return actual
4. Recorrer (Traverse)
Los métodos de recorrido visitan todos los nodos del árbol en un orden específico. Existen tres tipos principales de recorrido para árboles binarios: preorden, inorden y postorden.
- Inorden (Izquierda-Raíz-Derecha): Visita primero el subárbol izquierdo, luego la raíz, y finalmente el subárbol derecho.
- Preorden (Raíz-Izquierda-Derecha): Visita primero la raíz, luego el subárbol izquierdo, y finalmente el subárbol derecho.
- Postorden (Izquierda-Derecha-Raíz): Visita primero el subárbol izquierdo, luego el subárbol derecho, y finalmente la raíz.
En un árbol tienen una complejidad de O(n), porque visitan a cada nodo una vez.
Aquí se muestran los tres tipos principales de recorrido:
def inorden(self, nodo):
if nodo:
self.inorden(nodo.izquierda)
print(nodo.valor, end=' ')
self.inorden(nodo.derecha)
def preorden(self, nodo):
if nodo:
print(nodo.valor, end=' ')
self.preorden(nodo.izquierda)
self.preorden(nodo.derecha)
def postorden(self, nodo):
if nodo:
self.postorden(nodo.izquierda)
self.postorden(nodo.derecha)
print(nodo.valor, end=' ')
Árboles AVL
Los árboles AVL son un tipo especial de árbol binario de búsqueda que se mantienen automáticamente balanceados.
Su característica principal es que la diferencia de altura entre el subárbol izquierdo y derecho de cualquier nodo no puede ser mayor que 1.
Características principales:
- Se mantienen balanceados automáticamente
- Garantizan un tiempo de búsqueda, inserción y eliminación de O(log n)
- Cada nodo almacena un factor de balance (diferencia de altura entre sus subárboles)
Cuando se inserta o elimina un nodo, el árbol se rebalancea mediante rotaciones si es necesario.
Ejemplo en Python:
class NodoAVL:
def __init__(self, valor):
self.valor = valor
self.izquierda = None
self.derecha = None
self.altura = 1
class ArbolAVL:
def __init__(self):
self.raiz = None
def altura(self, nodo):
if not nodo:
return 0
return nodo.altura
def balance(self, nodo):
if not nodo:
return 0
return self.altura(nodo.izquierda) - self.altura(nodo.derecha)
def rotar_derecha(self, y):
x = y.izquierda
T2 = x.derecha
x.derecha = y
y.izquierda = T2
y.altura = max(self.altura(y.izquierda), self.altura(y.derecha)) + 1
x.altura = max(self.altura(x.izquierda), self.altura(x.derecha)) + 1
return x
def rotar_izquierda(self, x):
y = x.derecha
T2 = y.izquierda
y.izquierda = x
x.derecha = T2
x.altura = max(self.altura(x.izquierda), self.altura(x.derecha)) + 1
y.altura = max(self.altura(y.izquierda), self.altura(y.derecha)) + 1
return y
def insertar(self, raiz, valor):
if not raiz:
return NodoAVL(valor)
if valor < raiz.valor:
raiz.izquierda = self.insertar(raiz.izquierda, valor)
else:
raiz.derecha = self.insertar(raiz.derecha, valor)
raiz.altura = 1 + max(self.altura(raiz.izquierda), self.altura(raiz.derecha))
balance = self.balance(raiz)
if balance > 1 and valor < raiz.izquierda.valor:
return self.rotar_derecha(raiz)
if balance < -1 and valor > raiz.derecha.valor:
return self.rotar_izquierda(raiz)
if balance > 1 and valor > raiz.izquierda.valor:
raiz.izquierda = self.rotar_izquierda(raiz.izquierda)
return self.rotar_derecha(raiz)
if balance < -1 and valor < raiz.derecha.valor:
raiz.derecha = self.rotar_derecha(raiz.derecha)
return self.rotar_izquierda(raiz)
return raiz
def insertar_valor(self, valor):
self.raiz = self.insertar(self.raiz, valor)
# Uso del árbol AVL
arbol = ArbolAVL()
valores = [10, 20, 30, 40, 50, 25]
for valor in valores:
arbol.insertar_valor(valor)
Este código implementa las operaciones básicas de un árbol AVL. Estas operaciones incluyen la inserción y las rotaciones necesarias para mantener el árbol balanceado. Por ejemplo, cada vez que se inserta un nuevo valor, el árbol se ajusta automáticamente si es necesario.
Los árboles AVL usan los mismos métodos que un árbol nomal. La complejidad de cada método es:
- La inserción es O(log n). Y se debe a que los árboles están balanceados.
- El método de búsqueda es O(log n).
- La eliminación es O(log n).
Ventajas y desventajas
Ventajas:
- Jerarquía: Los árboles representan relaciones jerárquicas. Ejemplo, directorios de archivos o estructuras de organización.
- Búsqueda eficiente: La búsqueda en un árbol puede ser más rápida que en otras estructuras de datos.
- Ordenamiento: Los árboles binarios de búsqueda mantienen los datos ordenados.
Desventajas:
- Complejidad: La implementación y manipulación de árboles puede ser compleja.
- Espacio en memoria: Algunos árboles pueden ocupar más memoria que otras estructuras.
Aplicaciones en la vida real
Los árboles tienen diversas aplicaciones en la vida real:
- Árboles de directorios: Organizan archivos en sistemas de archivos.
- Árboles de expresiones: Representan fórmulas matemáticas.
- Árboles de decisión: Se usan en aprendizaje automático y toma de decisiones.
- Árboles genealógicos: Representan relaciones familiares.
Ejemplo utilizando arboles de directorios
- Sistema de archivos y directorios:
- Imagina que estás navegando por las carpetas en tu computadora. Cada carpeta (directorio) puede contener archivos y subcarpetas.
- El directorio raíz es el nivel superior del sistema de archivos. A partir de ahí, se ramifica en subdirectorios.
- Cada subdirectorio puede contener más archivos o subdirectorios, creando una estructura jerárquica similar a un árbol.
- Ejemplo visual:
- Supongamos que tienes una carpeta llamada “Documentos”. Dentro de ella tienes otras carpetas como “Trabajo”, “Personal” y “Proyectos”.
- La carpeta “Trabajo” contiene archivos relacionados con tu empleo.
- La carpeta “Proyectos” tiene subcarpetas para cada proyecto en el que estás trabajando. Cada subcarpeta de proyecto puede contener más archivos específicos para ese proyecto.
- Representación del árbol:
- Visualmente, esto se asemeja a un árbol. El directorio raíz es el tronco. Las subcarpetas son las ramas. Los archivos son las hojas.
- Cada carpeta (nodo) tiene un padre (la carpeta que la contiene) y puede tener varios hijos (subcarpetas o archivos).
Conclusión
Los árboles son estructuras de datos poderosas y versátiles. Se utilizan en una amplia variedad de aplicaciones. Estas van desde la organización de datos jerárquicos hasta la optimización de búsquedas. Al entender y dominar esta estructura, estarás un paso más cerca de convertirte en un programador experto.
Te invito a crear tu propia libreria de arboles con tu lenguaje favorito y compartas tu experiencia en los comentarios. No olvides seguirme en redes sociales para más contenido.
Sigueme en mis redes sociales para más contenido