Árboles binarios de búsqueda

Lo que cubre este capítulo

Un árbol binario de búsqueda es un árbol binario con una sola regla que lo cambia todo: para cada nodo, todos los valores menores viven en su subárbol izquierdo y todos los mayores en el derecho. Ese único invariante convierte búsqueda, inserción y borrado en el mismo movimiento — bajar desde la raíz comparando, hasta encontrar el valor o el hueco vacío que le corresponde — y cada paso baja un nivel, así que el trabajo es la altura del árbol. Cuando el árbol está balanceado eso es O(log n), y te da un contenedor ordenado donde todo es rápido: búsqueda, inserción, borrado, mínimo, máximo, sucesor e iteración ordenada. Este capítulo lo construye, lo ve crecer y luego encara su falla fatal — aquí nada lo mantiene balanceado — que es justamente la razón de ser de los dos capítulos siguientes.

Un poco de historia

El árbol binario de búsqueda se descubrió de forma independiente varias veces alrededor de 1960 — P. F. Windley, Andrew Booth y Andrew Colin, y Thomas Hibbard describieron versiones con apenas un par de años de diferencia, porque la idea de una estructura ordenada y buscable claramente estaba en el aire una vez que las computadoras tuvieron memoria suficiente para guardar árboles de apuntadores. El artículo de Hibbard de 1962 dio el algoritmo de borrado que usa este capítulo, incluido el complicado caso de dos hijos. Y casi de inmediato la gente notó el problema: un BST construido con datos ordenados degenera en una lista ligada, así que a los pocos años empezó la búsqueda de un árbol auto-balanceado, que produjo el árbol AVL (1962) y después el árbol rojo-negro — los siguientes dos capítulos. O sea que el BST llegó al mundo ya conociendo su propia debilidad, y la historia de los árboles durante la década siguiente fue la historia de arreglarla.

La intuición

Todo lo que hace un BST se reduce a una idea: en cada nodo, una comparación te dice hacia dónde ir. ¿Buscas un valor? Compáralo con la raíz — si es menor, el valor solo puede estar en el subárbol izquierdo, así que te vas a la izquierda y te olvidas por completo del derecho; si es mayor, te vas a la derecha. Repite hasta encontrarlo o hasta salirte del árbol. Cada comparación tira un subárbol entero, así que la búsqueda es tan profunda como alto sea el árbol.

Insertar es la misma caminata, pero cuando te sales del árbol plantas el nodo nuevo justo donde te detuviste — el hueco vacío al que llegaste es exactamente donde ese valor pertenece para no romper el orden. Borrar es la misma caminata hasta encontrar el nodo, y luego una pequeña cirugía para cerrar el hueco sin romper el orden (tres casos, detallados más abajo). Y como la regla de orden se cumple en todas partes, un recorrido in-order — izquierda, nodo, derecha — visita los valores del más chico al más grande, así que el árbol te entrega la salida ordenada gratis. Esa es toda la propuesta de valor del BST frente a una hash table: un hash set contesta "¿está aquí?" más rápido, pero no puede darte el mínimo, la siguiente llave mayor, un rango ni el orden sin recorrer todo. El BST mantiene los datos ordenados.

Complejidad: cómo escala

Cada operación central — búsqueda, inserción, borrado, mínimo, máximo — cuesta $O(h)$, la altura del árbol. Todo el juego está en cuánto vale h. Si el árbol está balanceado, $h = O(\log n)$ y todo es rápido. Pero nada en el BST de este capítulo obliga a que esté balanceado, y la altura depende por completo del orden de inserción. Inserta datos aleatorios y obtienes un árbol más o menos balanceado, de profundidad $O(\log n)$. Inserta datos ordenados y cada nodo se vuelve el hijo derecho del anterior — el árbol degenera en una lista ligada, $h = O(n)$, y cada operación se arrastra. La gráfica de balance muestra esta catástrofe directamente:

Construir un árbol de 8000 nodos con datos aleatorios tomó alrededor de 11 ms; con datos ordenados tomó 3090 ms — 291 veces más lento, porque las inserciones ordenadas construyeron un árbol degenerado y cada inserción tuvo que recorrerlo completo. Mismos valores, mismo código, resultados catastróficamente distintos nada más por el orden. Ese es el problema que resuelven los árboles balanceados.

En qué es bueno y en qué no

Un BST balanceado es la estructura correcta siempre que necesites una colección ordenada con actualizaciones rápidas: un mapa o conjunto que además soporte mínimo, máximo, "la siguiente llave después de X", consultas por rango e iteración ordenada. Eso es más de lo que una hash table puede hacer — el hashing dispersa las llaves, así que no tiene orden — y es lo que convierte a los BST (en su forma balanceada) en la columna vertebral de los mapas ordenados de C++ (std::map), Java (TreeMap) y de los índices de bases de datos. Cuando tus consultas son sobre orden o rangos, y no solo sobre pertenencia, esta es la familia que quieres.

Sus debilidades son dos. Primera: para pura pertenencia, sin consultas ordenadas, el O(1) de una hash table le gana al O(log n) del BST — usa un set a menos que necesites el orden. Segunda, y fatal para el BST simple: no se mantiene balanceado por sí solo, así que entradas adversarias o simplemente ordenadas lo degradan a O(n). El BST simple de este capítulo es por lo tanto una estructura didáctica: nunca lo mandarías a producción, porque el caso de entrada ordenada es demasiado común y demasiado catastrófico. Lo que sí mandas a producción es un BST auto-balanceado, que mantiene la altura en O(log n) sin importar el orden de inserción — los siguientes dos capítulos.

Los datos, o las entradas

El enfrentamiento inserta valores aleatorios en el BST, en una lista ordenada y en un set, con tamaños crecientes, para encontrar dónde la inserción O(log n) del BST rebasa a la inserción O(n) del arreglo. La gráfica de balance inserta la misma cantidad de valores en orden aleatorio contra orden ordenado, aislando la degeneración. La animación inserta siete valores en un árbol vacío para que veas cómo va tomando forma, con cada nodo nuevo colgado al final de su camino de búsqueda.

Constrúyelo, una función a la vez

Inserción — bajar comparando y colgar el nodo nuevo donde te sales del árbol:

def insert(self, value, probe=None):
    """O(h): walk down comparing — left if smaller, right if larger — until you
    fall off the tree, then hang the new node there. Duplicates are ignored (a
    BST models a set). h is the height: log n balanced, n degenerate."""
    if self.search(value):
        if probe is not None:
            probe.append({"path": [], "new": value})
        return
    path = []
    self.root = self._insert(self.root, value, path)
    self._n += 1
    if probe is not None:
        probe.append({"path": path, "new": value})

def _insert(self, node, value, path):
    if node is None:
        return Node(value)
    path.append(node.value)
    if value < node.value:
        node.left = self._insert(node.left, value, path)
    else:
        node.right = self._insert(node.right, value, path)
    return node

Búsqueda — la misma caminata, devolviendo verdadero cuando la comparación cae en el valor:

def search(self, value):
    """O(h): the same downward walk. At each node, done if equal, else go to the
    side that could contain the value. Every comparison eliminates a whole subtree."""
    node = self.root
    while node is not None:
        if value == node.value:
            return True
        node = node.left if value < node.value else node.right
    return False

def __contains__(self, value):
    return self.search(value)

El borrado es el que tiene sutileza de verdad — tres casos, y el más difícil es un nodo con dos hijos, que se reemplaza por su sucesor in-order:

def delete(self, value):
    """O(h): three cases. A leaf just vanishes. A node with one child is replaced
    by that child. A node with two children is replaced by its in-order successor —
    the smallest value in its right subtree — which is then deleted from there. The
    successor is chosen because it preserves the BST ordering."""
    if value in self:
        self.root = self._delete(self.root, value)
        self._n -= 1

def _delete(self, node, value):
    if node is None:
        return None
    if value < node.value:
        node.left = self._delete(node.left, value)
    elif value > node.value:
        node.right = self._delete(node.right, value)
    else:
        if node.left is None:
            return node.right
        if node.right is None:
            return node.left
        succ = node.right               # find the in-order successor
        while succ.left is not None:
            succ = succ.left
        node.value = succ.value
        node.right = self._delete(node.right, succ.value)
    return node

Míralo funcionar

Aquí hay un árbol binario de búsqueda construido insertando siete valores en el orden 5, 3, 8, 1, 4, 7, 9. Verde es el nodo recién insertado; azul es el camino de búsqueda que recorrió para llegar ahí; los nodos oscuros ya están asentados. Ve paso a paso y observa cómo emerge la estructura: 5 se vuelve la raíz, 3 se va a su izquierda, 8 a la derecha, y cada valor posterior baja por las comparaciones — siguiendo el azul — hasta llegar a un hueco vacío y quedarse ahí colgado en verde. Al final, el árbol tiene exactamente la forma cuyo recorrido in-order, del capítulo anterior, lee 1, 3, 4, 5, 7, 8, 9 — ordenado:

El código completo

Las dos versiones en un solo lugar — cambia entre ellas. La pestaña desde cero es nuestro BST con inserción, búsqueda y el borrado de tres casos. La pestaña de librería trae las estructuras más cercanas de la librería estándar: una lista ordenada mantenida con bisect (ordenada pero con inserción O(n)) y un set (O(1) pero sin orden) — las dos cosas entre las que se sitúa un BST. Para un BST balanceado de verdad usarías sortedcontainers, de terceros.

"""The binary search tree — a binary tree with one rule that makes it a searchable,
ordered container: for every node, everything in its left subtree is smaller and
everything in its right subtree is larger.

That rule turns search, insert, and delete into a single idea: walk down from the
root, going left or right by comparing, until you find the value or the spot for it.
Each step drops a level, so the work is the tree's height — O(log n) when the tree is
balanced, O(n) when it isn't. In-order traversal reads the whole thing out sorted. The
catch, which the next two chapters fix, is that nothing here keeps the tree balanced.
"""


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

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


class BST:
    def __init__(self):
        self.root = None
        self._n = 0

    # region: insert
    def insert(self, value, probe=None):
        """O(h): walk down comparing — left if smaller, right if larger — until you
        fall off the tree, then hang the new node there. Duplicates are ignored (a
        BST models a set). h is the height: log n balanced, n degenerate."""
        if self.search(value):
            if probe is not None:
                probe.append({"path": [], "new": value})
            return
        path = []
        self.root = self._insert(self.root, value, path)
        self._n += 1
        if probe is not None:
            probe.append({"path": path, "new": value})

    def _insert(self, node, value, path):
        if node is None:
            return Node(value)
        path.append(node.value)
        if value < node.value:
            node.left = self._insert(node.left, value, path)
        else:
            node.right = self._insert(node.right, value, path)
        return node
    # endregion

    # region: search
    def search(self, value):
        """O(h): the same downward walk. At each node, done if equal, else go to the
        side that could contain the value. Every comparison eliminates a whole subtree."""
        node = self.root
        while node is not None:
            if value == node.value:
                return True
            node = node.left if value < node.value else node.right
        return False

    def __contains__(self, value):
        return self.search(value)
    # endregion

    # region: delete
    def delete(self, value):
        """O(h): three cases. A leaf just vanishes. A node with one child is replaced
        by that child. A node with two children is replaced by its in-order successor —
        the smallest value in its right subtree — which is then deleted from there. The
        successor is chosen because it preserves the BST ordering."""
        if value in self:
            self.root = self._delete(self.root, value)
            self._n -= 1

    def _delete(self, node, value):
        if node is None:
            return None
        if value < node.value:
            node.left = self._delete(node.left, value)
        elif value > node.value:
            node.right = self._delete(node.right, value)
        else:
            if node.left is None:
                return node.right
            if node.right is None:
                return node.left
            succ = node.right               # find the in-order successor
            while succ.left is not None:
                succ = succ.left
            node.value = succ.value
            node.right = self._delete(node.right, succ.value)
        return node
    # endregion

    def __len__(self):
        return self._n

    def inorder(self):
        out = []

        def rec(node):
            if node is not None:
                rec(node.left)
                out.append(node.value)
                rec(node.right)

        rec(self.root)
        return out

"""Python has no built-in balanced BST — the third-party `sortedcontainers.SortedList`
is what you'd actually use for ordered O(log n) operations. In the standard library the
two nearest things sit on either side of the BST's trade-off:

  - A sorted list kept with `bisect.insort` is ordered, but each insert is O(n) because
    the array shifts — the array's weakness a BST is meant to fix.
  - A `set`/`dict` gives O(1) membership but NO order — you can't get its minimum or its
    keys in sorted order in less than O(n).

The BST's pitch is "both": ordered operations AND O(log n) inserts. The face-off shows
it beating the sorted list on insert-heavy work while keeping the order the set throws
away.
"""
import bisect


# region: sorted_list
def build_sorted_list(values):
    """Keep a sorted list via bisect: O(log n) to find the spot, but O(n) to insert
    because every later element shifts. Ordered, but insert-heavy workloads suffer."""
    a = []
    for v in values:
        i = bisect.bisect_left(a, v)
        if i >= len(a) or a[i] != v:
            a.insert(i, v)                  # the O(n) shift
    return a
# endregion


# region: dict_set
def build_set(values):
    """A set: O(1) membership, but unordered. No min, no max, no sorted iteration in
    less than O(n) — the ordering a BST keeps and a hash table discards."""
    return set(values)
# endregion

Desde cero vs librería

El enfrentamiento cuenta una historia de cruce. En tamaños chicos gana la lista ordenada, porque su inserción — un bisect más un list.insert en C — tiene una constante minúscula aunque sea O(n). Pero O(n) por inserción es O(n²) para construirla, y para los 200000 elementos nuestro BST, con O(n log n) en total, la rebasó de forma decisiva: unos 432 ms del BST contra 1140 ms de la lista ordenada, 2.6 veces más rápido, y la brecha se ensancha con el tamaño. Esa es la ventaja asintótica del BST venciendo por fin a la constante del arreglo — exactamente el cruce que prometía el capítulo de complejidad. Mientras tanto, el set se construyó en 9 ms, un orden de magnitud más rápido que cualquiera de los dos — pero no está ordenado, así que no puede hacer ni una sola de las consultas ordenadas para las que existe el BST. La comparación que hay que recordar no es la velocidad; es la capacidad. Pagas el factor logarítmico del BST para obtener un orden que la hash table no te puede dar a ninguna velocidad.

Dónde te lo vas a encontrar de verdad

Te topas con árboles binarios de búsqueda balanceados siempre que los datos tienen que mantenerse ordenados mientras se actualizan. std::map y std::set en C++, TreeMap y TreeSet en Java, y los mapas ordenados de muchos lenguajes son BST balanceados (normalmente árboles rojo-negro). Los índices de bases de datos son sus primos en disco, los árboles B, tema de un capítulo posterior. Cualquier problema del tipo "mantener un leaderboard ordenado conforme cambian los puntajes", "encontrar el siguiente evento después de ahora" o "contar cuántos valores caen en este rango" tiene un BST por debajo. La versión simple de aquí rara vez se usa directamente — se usan sus descendientes balanceados — pero cada uno de ellos es esta estructura más una regla para mantenerla bajita.

Conclusiones

Un árbol binario de búsqueda ordena sus valores con el invariante "menores a la izquierda, mayores a la derecha", lo que convierte búsqueda, inserción y borrado en una sola caminata hacia abajo de longitud igual a la altura del árbol, y hace que el recorrido in-order entregue la salida ordenada. Balanceado, esa altura es $O(\log n)$ y tienes un contenedor ordenado y rápido — iteración ordenada, rangos, mínimo, máximo, sucesor — que ninguna hash table puede igualar. Su falla fatal es que no se balancea solo, así que la entrada ordenada lo degrada a una lista ligada $O(n)$.

Esa falla es justamente el tema del siguiente capítulo. El árbol AVL es un BST que vigila su propio balance después de cada inserción y cada borrado, y ejecuta rotaciones — reestructuraciones locales que mueven unos cuantos apuntadores — para garantizar que la altura se mantenga en $O(\log n)$ sin importar en qué orden lleguen los datos. Es el BST hecho seguro para usarse de verdad.