Introducción a los Árboles
Los árboles son estructuras de datos avanzadas que organizan los datos en una jerarquía. Un árbol se compone de nodos, donde cada nodo tiene un valor y referencias a sus nodos hijos. El nodo superior se llama raíz, y los nodos sin hijos se llaman hojas. Los árboles son útiles para representar datos jerárquicos y para operaciones de búsqueda y clasificación eficientes. Áreas como la inteligencia artificial, los sistemas de archivos y las bases de datos utilizan ampliamente los árboles.
Nombre de la página: Árboles: Estructuras de Datos Avanzadas
Árboles Binarios
Un árbol binario es una estructura de datos donde cada nodo tiene como máximo dos hijos, llamados hijo izquierdo y hijo derecho. Los árboles binarios se utilizan en una variedad de aplicaciones, desde la representación de expresiones aritméticas hasta la implementación de algoritmos de búsqueda y clasificación. Aquí tienes un ejemplo básico de un árbol binario en Python:
class Nodo:
def __init__(self, valor):
self.valor = valor
self.izquierda = None
self.derecha = None
def insertar(raiz, valor):
if raiz is None:
return Nodo(valor)
if valor < raiz.valor:
raiz.izquierda = insertar(raiz.izquierda, valor)
else:
raiz.derecha = insertar(raiz.derecha, valor)
return raiz
# Ejemplo de uso
raiz = Nodo(10)
insertar(raiz, 5)
insertar(raiz, 15)
Este código crea un árbol binario y permite insertar nuevos valores en la posición adecuada siguiendo las reglas del árbol binario.
Nombre de la página: Árboles: Estructuras de Datos Avanzadas
Árboles AVL
Los árboles AVL son un tipo de árbol binario de búsqueda auto-balanceado. En un árbol AVL, la diferencia de altura entre los subárboles izquierdo y derecho de cualquier nodo no puede ser mayor que uno. Esto garantiza que las operaciones de búsqueda, inserción y eliminación se realicen en tiempo logarítmico. Aquí tienes un ejemplo básico de un árbol AVL en Python:
class NodoAVL:
def __init__(self, valor):
self.valor = valor
self.izquierda = None
self.derecha = None
self.altura = 1
def insertar_avl(raiz, valor):
if not raiz:
return NodoAVL(valor)
if valor < raiz.valor:
raiz.izquierda = insertar_avl(raiz.izquierda, valor)
else:
raiz.derecha = insertar_avl(raiz.derecha, valor)
raiz.altura = 1 + max(obtener_altura(raiz.izquierda), obtener_altura(raiz.derecha))
balance = obtener_balance(raiz)
if balance > 1 and valor < raiz.izquierda.valor:
return rotar_derecha(raiz)
if balance < -1 and valor > raiz.derecha.valor:
return rotar_izquierda(raiz)
if balance > 1 and valor > raiz.izquierda.valor:
raiz.izquierda = rotar_izquierda(raiz.izquierda)
return rotar_derecha(raiz)
if balance < -1 and valor < raiz.derecha.valor:
raiz.derecha = rotar_derecha(raiz.derecha)
return rotar_izquierda(raiz)
return raiz
# Funciones de soporte para obtener altura, balance y realizar rotaciones
def obtener_altura(nodo):
if not nodo:
return 0
return nodo.altura
def obtener_balance(nodo):
if not nodo:
return 0
return obtener_altura(nodo.izquierda) - obtener_altura(nodo.derecha)
def rotar_izquierda(z):
y = z.derecha
T2 = y.izquierda
y.izquierda = z
z.derecha = T2
z.altura = 1 + max(obtener_altura(z.izquierda), obtener_altura(z.derecha))
y.altura = 1 + max(obtener_altura(y.izquierda), obtener_altura(y.derecha))
return y
def rotar_derecha(y):
x = y.izquierda
T2 = x.derecha
x.derecha = y
y.izquierda = T2
y.altura = 1 + max(obtener_altura(y.izquierda), obtener_altura(y.derecha))
x.altura = 1 + max(obtener_altura(x.izquierda), obtener_altura(x.derecha))
return x
# Ejemplo de uso
raiz = None
valores = [10, 20, 30, 40, 50, 25]
for valor in valores:
raiz = insertar_avl(raiz, valor)
Este código muestra cómo insertar valores en un árbol AVL y mantenerlo balanceado utilizando rotaciones.
Nombre de la página: Árboles: Estructuras de Datos Avanzadas
B-trees
Los B-trees son árboles auto-balanceados que mantienen datos ordenados y permiten búsquedas, inserciones y eliminaciones en tiempo logarítmico. A diferencia de los árboles binarios y AVL, los B-trees están diseñados para trabajar bien con sistemas de almacenamiento como discos duros y bases de datos. Aquí tienes un ejemplo básico de un B-tree en Python:
class BTreeNode:
def __init__(self, t, leaf=False):
self.t = t
self.leaf = leaf
self.keys = []
self.children = []
def insertar_btree(nodo, k):
if nodo.leaf:
nodo.keys.append(k)
nodo.keys.sort()
else:
i = len(nodo.keys) - 1
while i >= 0 and k < nodo.keys[i]:
i -= 1
i += 1
if len(nodo.children[i].keys) == 2 * nodo.t - 1:
dividir_hijo(nodo, i)
if k > nodo.keys[i]:
i += 1
insertar_btree(nodo.children[i], k)
def dividir_hijo(nodo, i):
t = nodo.t
y = nodo.children[i]
z = BTreeNode(t, y.leaf)
nodo.children.insert(i + 1, z)
nodo.keys.insert(i, y.keys[t - 1])
z.keys = y.keys[t:]
y.keys = y.keys[:t - 1]
if not y.leaf:
z.children = y.children[t:]
y.children = y.children[:t]
# Ejemplo de uso
t = 3
raiz = BTreeNode(t, True)
valores = [10, 20, 5, 6, 12, 30, 7, 17]
for valor in valores:
insertar_btree(raiz, valor)
Este código ilustra cómo insertar valores en un B-tree y manejar la división de nodos cuando están llenos.
Nombre de la página: Árboles: Estructuras de Datos Avanzadas
Conclusión
Los árboles binarios, árboles AVL y B-trees son estructuras de datos avanzadas que permiten organizar y manejar datos de manera eficiente. Cada uno tiene sus propias ventajas y casos de uso específicos. Comprender estos árboles y cómo implementarlos te ayudará a escribir programas más eficientes y optimizados. Practicar con ejemplos te permitirá fortalecer tus habilidades en el manejo de estas estructuras complejas.