Árboles

📐 Fundamento

Propiedades:

• Un árbol con $n$ nodos tiene $n - 1$ aristas.
• Hay un único camino entre dos nodos cualquiera.
• En un árbol binario perfecto de altura $h$, hay $2^{h+1} - 1$ nodos. Inversa: $h \approx \log_2 n$.

📐 Fundamento

Cada nodo tiene a lo sumo dos hijos: izquierdo y derecho.

class Nodo:
    def __init__(self, dato, izq=None, der=None):
        self.dato = dato
        self.izq = izq
        self.der = der

# Construir un árbol manual
arbol = Nodo("A",
    Nodo("B", Nodo("D"), Nodo("E")),
    Nodo("C", None, Nodo("F"))
)
#         A
#        / \
#       B   C
#      / \   \
#     D   E   F

Recorridos

Tres recorridos clásicos, todos $O(n)$:

Preorden: raíz → izquierdo → derecho.

def preorden(nodo):
    if nodo is None: return
    print(nodo.dato)
    preorden(nodo.izq)
    preorden(nodo.der)

# Para el árbol arriba: A, B, D, E, C, F

Inorden: izquierdo → raíz → derecho.

def inorden(nodo):
    if nodo is None: return
    inorden(nodo.izq)
    print(nodo.dato)
    inorden(nodo.der)

# Para el árbol arriba: D, B, E, A, C, F

Postorden: izquierdo → derecho → raíz.

def postorden(nodo):
    if nodo is None: return
    postorden(nodo.izq)
    postorden(nodo.der)
    print(nodo.dato)

# Para el árbol arriba: D, E, B, F, C, A

Cuándo cada uno:

• Preorden: copiar / serializar el árbol. JSON-ish.
• Inorden: en BST, devuelve los elementos ordenados.
• Postorden: liberar memoria del árbol (los hijos primero), evaluar expresiones.

BFS / por niveles: con cola.

from collections import deque

def por_niveles(raiz):
    if raiz is None: return
    cola = deque([raiz])
    while cola:
        nodo = cola.popleft()
        print(nodo.dato)
        if nodo.izq: cola.append(nodo.izq)
        if nodo.der: cola.append(nodo.der)

# Para el árbol arriba: A, B, C, D, E, F

📐 Fundamento

Un BST es un árbol binario con la invariante:

Para cada nodo: todos los valores en el subárbol izquierdo son menores; todos en el derecho son mayores.

        50
       /  \
      30   70
     / \   / \
    20 40 60 80

Búsqueda eficiente: comparás con la raíz, vas a izq o der según corresponda. Cada paso descarta la mitad del árbol.

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

    def insertar(self, x):
        self.raiz = self._insertar(self.raiz, x)

    def _insertar(self, nodo, x):
        if nodo is None:
            return Nodo(x)
        if x < nodo.dato:
            nodo.izq = self._insertar(nodo.izq, x)
        elif x > nodo.dato:
            nodo.der = self._insertar(nodo.der, x)
        # x == nodo.dato: ignorar duplicados
        return nodo

    def buscar(self, x):
        return self._buscar(self.raiz, x)

    def _buscar(self, nodo, x):
        if nodo is None: return False
        if x == nodo.dato: return True
        if x < nodo.dato: return self._buscar(nodo.izq, x)
        return self._buscar(nodo.der, x)

    def __contains__(self, x):
        return self.buscar(x)

Eliminar es más feo. Tres casos:

1. Hoja: eliminar directo.
2. Un solo hijo: reemplazar el nodo con su hijo.
3. Dos hijos: reemplazar con su sucesor inorden (el más chico del subárbol derecho), luego eliminar el sucesor.

def _eliminar(self, nodo, x):
    if nodo is None: return None
    if x < nodo.dato:
        nodo.izq = self._eliminar(nodo.izq, x)
    elif x > nodo.dato:
        nodo.der = self._eliminar(nodo.der, x)
    else:
        # Encontrado
        if nodo.izq is None: return nodo.der
        if nodo.der is None: return nodo.izq
        # Dos hijos: sucesor inorden
        sucesor = nodo.der
        while sucesor.izq:
            sucesor = sucesor.izq
        nodo.dato = sucesor.dato
        nodo.der = self._eliminar(nodo.der, sucesor.dato)
    return nodo

Análisis

• Mejor caso (árbol balanceado): todas las operaciones $O(\log n)$.
• Peor caso (árbol "lineal"): $O(n)$ — degenera en lista enlazada.

Ejemplo del peor caso: insertar 1, 2, 3, 4, 5, 6 en orden:

1
 \
  2
   \
    3
     \
      4
       ...

Búsqueda de "6": $O(n)$. El BST sin balanceo es frágil.

📐 Fundamento

Para evitar la degeneración, los árboles balanceados se reorganizan automáticamente para mantener altura $O(\log n)$.

AVL (Adelson-Velsky & Landis, 1962). El primero. Mantiene la diferencia de altura entre subárboles izquierdo y derecho ≤ 1. Tras cada inserción/eliminación, hace rotaciones si se desequilibra.

Red-Black trees. Cada nodo es rojo o negro, con reglas que garantizan altura $\leq 2 \log_2(n+1)$. Más relajado que AVL pero más rápido en inserciones. Lo usan std::map (C++), TreeMap (Java), kernel de Linux.

Rotaciones — la operación clave:

       y                          x
      / \                        / \
     x   C    rotación der      A   y
    / \      ←-------------         / \
   A   B                            B   C

Una rotación reorganiza tres nodos preservando el orden BST y reduciendo la altura.

No los implementamos a fondo aquí. El código de un AVL o Red-Black es largo (200+ líneas). El concepto que sí debés sacar:

En la práctica, siempre usá una estructura balanceada (de la biblioteca estándar) en lugar de implementar tu propio BST. Las bibliotecas tienen décadas de optimizaciones y casos esquina cubiertos.

En Python:

• No hay BST en stdlib.
• sortedcontainers.SortedList (paquete externo) usa skip lists, comportamiento similar.
• bintrees (paquete externo) tiene AVL y Red-Black.
• Para casos donde un BST sería natural, muchas veces un dict + lista alcanza.

En otros lenguajes:

• C++: std::map, std::set (red-black).
• Java: TreeMap, TreeSet.
• Rust: BTreeMap, BTreeSet (B-tree, similar pero distinto).

📐 Fundamento

Un heap es un árbol binario completo (lleno por niveles) con la propiedad:

• Min-heap: cada nodo es ≤ que sus hijos. La raíz es el mínimo.
• Max-heap: cada nodo es ≥ que sus hijos. La raíz es el máximo.

No es un BST — los hijos pueden estar en cualquier orden entre sí.

Implementación: array. Un heap se representa como array donde:

• Padre de i: (i - 1) // 2.
• Hijo izquierdo: 2*i + 1.
• Hijo derecho: 2*i + 2.

índice:   0  1  2  3  4  5
valor:   [1, 3, 2, 5, 4, 9]

         1                 (i=0)
        / \
       3   2               (i=1, i=2)
      / \ /
     5  4 9                (i=3, i=4, i=5)

Es min-heap: 1 < 3, 2; 3 < 5, 4; 2 < 9.

Operaciones:

• peek (mín): raíz, $O(1)$.
• push: insertar al final, "burbujear" hacia arriba. $O(\log n)$.
• pop: sacar la raíz, mover el último a la raíz, "hundir" hacia abajo. $O(\log n)$.

Python ya tiene heapq (min-heap):

import heapq

h = []
heapq.heappush(h, 5)
heapq.heappush(h, 1)
heapq.heappush(h, 3)
heapq.heappush(h, 8)

print(h)               # [1, 5, 3, 8]  (orden de heap, no ordenado)
print(heapq.heappop(h))  # 1
print(heapq.heappop(h))  # 3

heapq opera sobre listas. Es eficiente, parte de stdlib.

Aplicaciones

Cola de prioridad. El uso clásico. Tareas con prioridad → la más prioritaria sale primero.

Heapsort. Ordenamiento $O(n \log n)$:

def heapsort(lista):
    h = lista[:]
    heapq.heapify(h)         # convierte a heap en O(n)
    return [heapq.heappop(h) for _ in range(len(h))]

Top K elementos.

def top_k(lista, k):
    return heapq.nlargest(k, lista)

# heapq.nsmallest, nlargest existen y son eficientes

Algoritmo de Dijkstra (rutas más cortas) usa min-heap.

📐 Fundamento

Un trie (pronunciado "tray") es un árbol especializado en strings. Cada arista es una letra, cada camino desde la raíz es un prefijo.

       (raíz)
       /  |  \
      c   p   ...
      |   |
      a   u
      |   |
      r   p
      |   |
      o   u
          |
          s
          |
          a

"caro" y "pupusa" están en el trie. Comparten la raíz pero divergen.

Operaciones $O(L)$ donde $L$ es la longitud de la palabra. Eso es independiente de cuántas palabras haya guardadas.

Aplicaciones:

• Autocompletado (Google search bar).
• Diccionarios y correctores ortográficos.
• Routing IP (longest prefix match).
• Frecuencia de palabras en textos.

class Trie:
    def __init__(self):
        self.hijos = {}
        self.fin = False

    def insertar(self, palabra):
        nodo = self
        for c in palabra:
            if c not in nodo.hijos:
                nodo.hijos[c] = Trie()
            nodo = nodo.hijos[c]
        nodo.fin = True

    def buscar(self, palabra):
        nodo = self
        for c in palabra:
            if c not in nodo.hijos:
                return False
            nodo = nodo.hijos[c]
        return nodo.fin

    def empieza_con(self, prefijo):
        nodo = self
        for c in prefijo:
            if c not in nodo.hijos:
                return False
            nodo = nodo.hijos[c]
        return True


t = Trie()
t.insertar("pupusa")
t.insertar("pupuseria")
print(t.buscar("pupusa"))         # True
print(t.empieza_con("pup"))       # True
print(t.buscar("pup"))             # False