Árboles binarios y recorridos

De qué trata este capítulo

Un árbol binario es la primera estructura ramificada del libro — nodos, cada uno con hasta dos hijos — y lo primero que haces con cualquier árbol es recorrerlo: visitar cada nodo en algún orden. Existen exactamente cuatro órdenes que vale la pena conocer, y lo sorprendente es lo poco que los separa. Tres son en profundidad y se diferencian por una sola línea — cuándo visitas el nodo respecto a sus hijos — y el cuarto es por niveles y reutiliza la queue que vimos antes en el libro. Este capítulo construye los cuatro, muestra por qué el recorrido in-order es especial para los árboles de búsqueda, y prepara los siguientes nueve capítulos, todos sobre árboles.

Un poco de historia

Los árboles son una de las estructuras más viejas de la computación, y sus órdenes de recorrido se formalizaron temprano — el Art of Computer Programming de Donald Knuth le dio a los nombres in-order, pre-order y post-order su significado estándar. Dos de ellos tienen un linaje más profundo. En los años veinte el lógico polaco Jan Łukasiewicz inventó una notación sin paréntesis para la lógica, escribiendo el operador antes de sus operandos — que es exactamente el recorrido pre-order de un árbol de expresión, y todavía se le llama notación polaca. Su inversa, el operador después de los operandos — post-order — se convirtió en la Notación Polaca Inversa, el método de entrada de las calculadoras HP y el modelo de ejecución de lenguajes basados en pila como Forth y PostScript. Así que dos de los cuatro recorridos de este capítulo son la forma en que las máquinas han evaluado aritmética durante un siglo: la forma del árbol y el orden de visita son la misma idea vista desde ángulos distintos.

La intuición

Imagina un nodo con un subárbol izquierdo y uno derecho. Un recorrido en profundidad siempre hace tres cosas — atender el subárbol izquierdo, atender el derecho, y visitar el nodo mismo — la única pregunta es en qué orden. Visita el nodo entre los subárboles y tienes in-order; antes de ellos, pre-order; después, post-order. Esa es toda la diferencia entre los tres: se mueve una línea.

Cuál orden quieres es una pregunta sobre cuándo necesitas el nodo respecto a sus hijos. El in-order, sobre un árbol binario de búsqueda, sale ordenado — porque todo lo que está en el subárbol izquierdo es menor y todo lo del derecho es mayor, así que visitar izquierda-luego-nodo-luego-derecha entrega valores ascendentes. El pre-order te da primero la raíz, que es justo lo que necesitas para copiar o serializar un árbol (no puedes reconstruir un subárbol antes de conocer su raíz). El post-order te da primero los hijos, que es lo que necesitas para borrar un árbol (liberar los subárboles antes que el padre) o evaluar un árbol de expresión (calcular los operandos antes de aplicar el operador). El recorrido por niveles es el raro del grupo — va a lo ancho, de arriba hacia abajo, y necesita una queue en lugar de recursión, porque "lo más cercano primero" es una disciplina FIFO, no de pila.

Complejidad: cómo escala

Todo recorrido es $O(n)$ en tiempo — cada uno de los n nodos se visita exactamente una vez, y el trabajo por nodo es constante. El espacio es $O(h)$, donde h es la altura del árbol: los recorridos en profundidad mantienen una pila de recursión (o explícita) tan profunda como el camino actual, y el recorrido por niveles mantiene una queue tan ancha como el nivel más ancho. Para un árbol balanceado $h = O(\log n)$, pero para uno degenerado — un árbol que en realidad es una lista ligada — $h = O(n)$, que es donde la recursión puede provocar un overflow de pila. La gráfica compara el in-order recursivo contra el iterativo sobre árboles balanceados:

Ambos son lineales, como se esperaba; la versión recursiva es aquí como 1.2× más lenta, el costo del overhead de las llamadas a función que la pila explícita se ahorra.

En qué es bueno y en qué no

Recorrer no es opcional — es la forma en que tocas el contenido de un árbol, así que "en qué es bueno" en realidad es "cuál orden le queda a tu tarea". El in-order es el caballo de batalla de los árboles de búsqueda porque te entrega datos ordenados gratis. El pre-order y el post-order son los órdenes de copiar y de borrar/evaluar. El recorrido por niveles es cómo encuentras el nodo más superficial que cumple alguna condición, o cómo procesas un árbol por generaciones. Saber cuál es cuál convierte un montón de problemas de árboles en una decisión de una línea.

Lo que hay que cuidar es la profundidad de recursión. Los recorridos en profundidad son naturalmente recursivos y preciosamente cortos, pero usan pila proporcional a la altura del árbol, así que un árbol profundo o desbalanceado puede reventar el límite de recursión — el mismo peligro del capítulo de recursión. La versión iterativa con pila explícita lo esquiva, y los siguientes capítulos (árboles balanceados) atacan la causa raíz manteniendo la altura en O(log n).

Los datos, o las entradas

Las verificaciones de correctitud construyen árboles de búsqueda con valores aleatorios y confirman que el in-order es igual a sorted. El face-off recorre árboles balanceados de tamaños crecientes. La animación usa un único árbol de búsqueda fijo de siete nodos para que veas cómo un solo recorrido in-order produce la secuencia ordenada, nodo por nodo.

Constrúyelo, una función a la vez

In-order — visita el nodo entre sus subárboles, lo que da orden ascendente en un BST:

def inorder(node, visit):
    """Left, node, right. For a binary SEARCH tree this yields the values in sorted
    order — the single most useful traversal, and the reason BSTs keep data ordered."""
    if node is None:
        return
    inorder(node.left, visit)
    visit(node.value)
    inorder(node.right, visit)

Pre-order — visita el nodo antes de sus subárboles, para copiar y serializar:

def preorder(node, visit):
    """Node, left, right. Visits a parent before its children — the order you use to
    copy or serialize a tree, because you need the root before its subtrees."""
    if node is None:
        return
    visit(node.value)
    preorder(node.left, visit)
    preorder(node.right, visit)

Post-order — visita el nodo después de sus subárboles, para borrar y evaluar:

def postorder(node, visit):
    """Left, right, node. Visits children before the parent — the order to delete a
    tree (free the subtrees first) or evaluate an expression tree (compute the
    operands before the operator)."""
    if node is None:
        return
    postorder(node.left, visit)
    postorder(node.right, visit)
    visit(node.value)

El recorrido por niveles es el que va a lo ancho, y el único que necesita una queue en lugar de recursión:

def levelorder(root, visit):
    """Breadth-first: level by level, top to bottom, left to right — using a QUEUE.
    It's the one traversal that isn't naturally recursive; it's the tree version of
    breadth-first search, and it needs the FIFO queue from earlier in the book."""
    from collections import deque
    if root is None:
        return
    q = deque([root])
    while q:
        node = q.popleft()
        visit(node.value)
        if node.left:
            q.append(node.left)
        if node.right:
            q.append(node.right)

Y aquí está el mismo recorrido in-order sin recursión, usando una pila explícita — la transformación de recursión a pila que vimos antes, aplicada a un árbol:

def inorder_iter(root, visit):
    """In-order without recursion, using an EXPLICIT stack. This is the recursion-to-
    stack transformation from the recursion chapter applied to a tree: push lefts,
    visit, go right. It's what the recursive call stack was doing, made visible — and
    your escape hatch when a tree is too deep for Python's recursion limit."""
    stack, node = [], root
    while stack or node:
        while node:               # walk as far left as possible, remembering the path
            stack.append(node)
            node = node.left
        node = stack.pop()        # backtrack to the deepest unvisited node
        visit(node.value)
        node = node.right         # then explore its right subtree

Míralo funcionar

Aquí tienes un recorrido in-order de un árbol de búsqueda de siete nodos. En naranja está el nodo que se visita en este momento; los nodos verdes ya se visitaron; los oscuros siguen esperando. Avanza paso a paso y observa el orden de visita: se clava por el lado izquierdo hasta el valor más chico, 1, y luego se mueve hacia la derecha y hacia arriba — 3, 4, luego la raíz 5, luego el subárbol derecho 7, 8, 9. La salida se va acumulando en el pie de la animación, y sale perfectamente ordenada, que es la razón entera por la que el in-order importa en los árboles de búsqueda: el árbol guarda los datos en una forma que deja el orden ascendente a un recorrido de distancia:

El código completo

Ambas versiones en un mismo lugar — cambia entre ellas. La pestaña desde cero tiene los cuatro recorridos más el in-order iterativo. La pestaña de librería es el único equivalente honesto: sorted, que es a lo que el in-order de un árbol de búsqueda debe ser igual. No hay una función de "recorre este árbol" en la librería estándar porque un recorrido es una técnica, no un contenedor — lo escribes tú, en cualquiera de estas cuatro formas que necesite tu tarea.

"""Binary tree traversals — the four ways to visit every node of a tree, and the
first thing you learn to do with one. A binary tree is nodes, each with up to two
children (left and right); a traversal is an order for touching all of them.

Three of the four are depth-first and fall out of recursion — they differ only in
WHEN you visit the node relative to its children. The fourth is breadth-first and
needs the queue from the linear-structures tier. Which order you want depends on the
job: in-order for sorted output, pre-order to copy, post-order to delete, level-order
to explore nearest-first.
"""


class Node:
    __slots__ = ("value", "left", "right")

    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right


# region: inorder
def inorder(node, visit):
    """Left, node, right. For a binary SEARCH tree this yields the values in sorted
    order — the single most useful traversal, and the reason BSTs keep data ordered."""
    if node is None:
        return
    inorder(node.left, visit)
    visit(node.value)
    inorder(node.right, visit)
# endregion


# region: preorder
def preorder(node, visit):
    """Node, left, right. Visits a parent before its children — the order you use to
    copy or serialize a tree, because you need the root before its subtrees."""
    if node is None:
        return
    visit(node.value)
    preorder(node.left, visit)
    preorder(node.right, visit)
# endregion


# region: postorder
def postorder(node, visit):
    """Left, right, node. Visits children before the parent — the order to delete a
    tree (free the subtrees first) or evaluate an expression tree (compute the
    operands before the operator)."""
    if node is None:
        return
    postorder(node.left, visit)
    postorder(node.right, visit)
    visit(node.value)
# endregion


# region: levelorder
def levelorder(root, visit):
    """Breadth-first: level by level, top to bottom, left to right — using a QUEUE.
    It's the one traversal that isn't naturally recursive; it's the tree version of
    breadth-first search, and it needs the FIFO queue from earlier in the book."""
    from collections import deque
    if root is None:
        return
    q = deque([root])
    while q:
        node = q.popleft()
        visit(node.value)
        if node.left:
            q.append(node.left)
        if node.right:
            q.append(node.right)
# endregion


# region: inorder_iter
def inorder_iter(root, visit):
    """In-order without recursion, using an EXPLICIT stack. This is the recursion-to-
    stack transformation from the recursion chapter applied to a tree: push lefts,
    visit, go right. It's what the recursive call stack was doing, made visible — and
    your escape hatch when a tree is too deep for Python's recursion limit."""
    stack, node = [], root
    while stack or node:
        while node:               # walk as far left as possible, remembering the path
            stack.append(node)
            node = node.left
        node = stack.pop()        # backtrack to the deepest unvisited node
        visit(node.value)
        node = node.right         # then explore its right subtree
# endregion

"""There's no "traverse a tree" function in the standard library — a traversal is a
technique, not a container, so the honest counterparts are references:

  - For a binary SEARCH tree, in-order traversal must equal `sorted(values)` — that's
    the property that makes in-order special, and the reference we check against.
  - The recursive and iterative (explicit-stack) traversals must agree with each
    other — that's the recursion-to-stack transformation, and its own reference.

So the face-off is recursive vs iterative in-order (do they match, and what does the
recursion cost?), with `sorted` confirming that in-order of a BST is sorted order.
"""


# region: sorted_reference
def inorder_reference(values):
    """The reference for in-order of a binary SEARCH tree: it is exactly the sorted
    values. If your in-order traversal doesn't equal this, the tree isn't a valid BST
    (or the traversal is wrong)."""
    return sorted(values)
# endregion

Desde cero vs librería

Aquí no hay librería con la cual competir — la librería estándar no recorre árboles por ti — así que la comparación con sentido es recursivo contra iterativo en el in-order, más la verificación de que el in-order de un árbol de búsqueda es igual a sorted. El recorrido recursivo corrió como 1.2× más lento que la versión con pila explícita en 160000 nodos, otra vez el overhead de las llamadas a función, pero el código recursivo es tanto más claro que lo elegirías siempre que sepas que el árbol es poco profundo — lo cual, una vez que tengamos árboles balanceados, es siempre. El resultado más de fondo es el que mostró la animación: el recorrido in-order convierte un árbol binario de búsqueda en salida ordenada en O(n), gratis, y esa es la propiedad que hace que valga la pena construir la estructura del siguiente capítulo.

Dónde te lo vas a encontrar de verdad

Recorres árboles todo el tiempo, normalmente a través de algo construido encima. Todo compilador camina el árbol sintáctico de tu código — pre-order para armar tablas de símbolos, post-order para generar o evaluar. Serializar JSON o XML es un recorrido pre-order; un listado recursivo de directorios es un recorrido del árbol del sistema de archivos; renderizar el DOM camina el árbol del documento. os.walk, json.dump, y toda operación de "visita todos los nodos" en un framework de UI es uno de estos cuatro órdenes. Y el in-order en específico es cómo los mapas y conjuntos ordenados (construidos sobre árboles de búsqueda) iteran sus llaves en orden — el tema de todo el resto de este nivel.

Puntos clave

Un árbol binario son nodos con hasta dos hijos, y los cuatro recorridos son los cuatro órdenes para visitarlos: in-order (ordenado, para un BST), pre-order (copiar), post-order (borrar/evaluar), y por niveles (a lo ancho, con una queue). Los tres órdenes en profundidad son un solo algoritmo con la visita movida antes, entre, o después de la recursión; los cuatro son $O(n)$ en tiempo y $O(h)$ en espacio. La recursión es limpia pero está acotada por la profundidad, que es una razón más para querer los árboles balanceados que vienen.

El resultado estrella es que el in-order sobre un árbol de búsqueda entrega orden ascendente — que es una promesa sobre una estructura que todavía no construimos. El siguiente capítulo la construye: el árbol binario de búsqueda, donde la regla de orden (menores a la izquierda, mayores a la derecha) hace que buscar, insertar y borrar sigan todos un solo camino hacia abajo, y el recorrido in-order lee todo el contenido en orden.