CP-UPV Bootcamp - Capítulo 9

Capítulo 9: Árboles y árboles de segmentos

PROBLEMAS DEL CAPÍTULO
Para acceder a los problemas de este capítulo, accede con tu usuario y contraseña a cpupv.contest.codeforces.com. Si no tienes usuario y contraseña, inscríbete aquí.

Introducción

Este capítulo cubre árboles, una continuación del capítulo anterior sobre grafos ya que los árboles son grafos con ciertas características. También cubre una estructura de datos que no tiene que ver tanto con grafos, los árboles de segmentos, que sirven para resolver ciertos problemas de manera muy eficiente.

Índice de contenidos

Árboles

Un árbol es un grafo simple en el que todos los nodos están conectados por un único camino. Para simplificarlo, en el siguiente árbol se ve claramente la estructura de árbol. Fíjate que entre cualquier par de nodos, solo hay una manera de ir de uno a otro.

Características de un árbol

Un árbol es un grafo $G$ no dirigido si satisface una de las siguientes condiciones:

Además, asumiendo que $G$ tiene un número finito de nodos, $n$ por ejemplo:

Más terminología sobre árboles

Los nodos con grado 1 (solo una arista toca el nodo) se llaman hojas. En el árbol que se muestra más arriba, los 4 nodos más bajos son hojas.

Un bosque (o forest en inglés), es un grafo cuyos componentes conexos son todos árboles

Árbol de expansión

Un árbol de expansión de un grafo conexo $G$ es un subgrafo cualquiera de $G$ que contiene todos los nodos de $G$ y que también es un árbol, por ejemplo, en esta figura se muestran diferentes árboles de expansión para un grafo $G$. Es importante notar que no se queda fuera ningún nodo en los grafos con color.

Árbol de expansión mínimo

En un grafo conexo y ponderado (las aristas tienen peso, representando un coste, o una longitud...), el árbol de expansión mínimo es el árbol de expansión cuyo peso sea el mínimo posible. Es posible que existan múltiples árboles de expansión mínimo, pero todos tendrían el mismo peso. En la figura de abajo se muestra en negro el grafo incial, debajo, dos árboles de expansión mínimo (en verde) y un árbol de expansión que no es mínimo (en rojo)

Kruskal

Kruskal es uno de los algoritmos para hallar el árbol de expansión mínimo de un grafo. Para este algoritmo se utilizará la estructura de datos Disjoint Set Union.

Procedimiento
  1. Guardaremos en un array o una cola de prioridad todas las aristas que componen al grafo, por orden de menor a mayor.
  2. Mientras queden nodos por conectar al árbol de expansión mínimo, analizar la siguiente arista más pequeña.
    • Si los dos nodos que conecta la arista pertenecen al mismo componente conexo, descartar esta arista (si se tuviera en cuenta, habría un ciclo en el árbol y eso no es posible)
    • Si los dos nodos que conecta la arista no pertenecen al mismo componente conexo, añadir esa arista al árbol de expansión mínimo.
  3. Si ya están todos los nodos conectados al árbol de expansión mínimo, se acaba el algoritmo y tenemos una lista de las aristas que componen al árbol, en caso contrario volver al paso 2.
Ejemplo

Aquí se muestra un ejemplo paso por paso, se muestran en gris las aristas que aún no se han procesado, en negro las que se han incluido en el árbol de expansión mínimo, en azul la que se va a procesar, en rojo si se rechaza y en verde si se incluye.

  1. Comenzamos con todos los nodos desconectados.
  2. Escogemos la arista con menor peso, la de peso 4
  3. Como los nodos no pertenecen al mismo componente conexo (no crearían ciclos), incluimos la arista en el árbol de expansión mínimo
  4. Ahora la arista con menor peso sería de peso 5, pero hay múltiples aristas. Podemos elegir una al azar
  5. El nodo 4 y el nodo 2 no pertenecen al mismo componente conexo, por eso incluimos la arista en el árbol de expansión mínimo
  6. Escogemos otra arista de peso 5
  7. Esta vez, el nodo 4 y el nodo 5 ya pertenecen al mismo componente conexo. Si incluimos esta arista crearíamos un ciclo y ya no sería un árbol, debemos rechazar esta arista
  8. De nuevo, otra arista aleatoria de peso 5 ya que sigue siendo el menor peso de una arista
  9. Los nodos 3 y 4 están desconectados, podemos incluir la arista en el árbol de expansión mínimo
  10. Cogemos otro nodo de peso 5
  11. Y como el nodo 6 está desconectado del nodo 7 podemos incluirlo
  12. Solo falta una arista de peso 5
  13. Y la incluimos en el árbol de expansión mínimo porque los nodos 3 y 6 están desconectados
  14. Ahora comenzaremos con las aristas de peso 6, seleccionamos una al azar
  15. Los nodos 4 y 6 pertenecen al mismo componente conexo, se debe rechazar la arista
  16. Solo queda una arista de peso 6
  17. El nodo 8 está desconectado, incluimos la arista en el árbol de expansión mínimo
  18. La siguiente arista sería la de peso 7
  19. El nodo 1 está desconectado, y lo incluimos en el árbol de expansión mínimo
  20. Ahora podemos observar que todos los nodos están conectados y pertenecen al mismo componente conexo, lo que significa que hemos encontrado el árbol de expansión mínimo. Siguiendo el procedimiento veríamos que todas las aristas restantes serían rechazadas
  21. Y este es el resultado, el árbol de expansión mínimo tiene un peso de $5+7+5+4+5+5+6=37$

Árbol de segmentación (segment trees)

Un árbol de segmentación es una estructura de datos que guarda información para todos los intervalos de un array en forma de un arbol. Esta estructura de datos nos permite resolver peticiones sobre un intervalo de un array de forma muy eficiente mientras que se pueden hacer modificaciones al array.

Estos son algunos problemas que resuelve la estructura de datos; resolver las siguientes peticiones es posible en $O(log(n))$:

Introducción al problema

Para explicar la estructura de datos vamos a considerar un problema básico, calcular la suma de elementos en un intervalo en un array: Dado un array de $n$ elementos, $a_0, a_1, a_2, \cdots, a_{n-1}$, queremos calcular la suma de los elementos entre los índices $l$ y $r$ ($\sum_{i=l}^{r} a[i]$). Además, mientras se hacen peticiones entre rangos queremos hacer modificaciones a elementos del array (en el formato $a[i] = x$). Ambas operaciones deben realizarse en $O(log(n))$.

Las soluciones obvias serían:

Debemos usar un segment tree. Utilizaremos la estrategia divide y vencerás; para guardar la suma en cada intervalo podemos guardar primero la suma de todos los elementos del array $a[0 \dots n-1]$. Después podemos partir el array en dos mitades y guardar la suma de cada mitad, $a[0 \dots n/2-1]$ y $a[n/2 \dots n-1]$, y seguir con el proceso hasta que lleguemos a intervalos de tamaño 1. Ahora podemos representar esto como un árbol binario donde la raiz representa la suma de todos los elementos del array y cada nodo tiene dos hijos representando la suma de las dos mitades. Para el array [2, -4, 5, 1, -7]:

En este caso utilizaremos un simple array $T$ de enteros para guardar toda la estructura de datos (para casos más avanzados podría ser un array de un objeto o struct). Pero ¿que tamaño debe tener el array $T$? Pues podemos observar que empezando por el nivel de arriba, cada nivel necesita el doble de nodos que el anterior hasta que el número de nodos en un nivel sea al menos $n$. Como se muestra en la figura de abajo, en el peor de los casos (aquellos donde $n = 2^k+1, k \in \mathbb{N}$), se requieren $4n$ posiciones en el array $T$ para garantizar que podemos guardar el árbol, aunque el último nivel no tiene porque completarse. También podemos ver que la altura del árbol es aproximadamente $log(n)$ porque desde arriba el tamaño del array decrementa por la mitad cada vez.

Construcción del Segment Tree

Antes de construir el árbol de segmentación tenemos que tener claro:

  1. que información guarda cada nodo del árbol, en este caso la suma del intervalo $[l, r]$
  2. como combinar dos nodos hijos. En este caso, se pueden combinar dos nodos hijos sumando sus dos valores. Para un nodo, si se combinan sus dos nodos hijos $a[l_1 \dots r_1]$ y $a[l_2 \dots r_2]$ obtendríamos la suma del rango $a[l_1 \dots r_2]$

Tendremos en cuenta que un nodo hoja es un nodo que representa a un intervalo de tan solo un elemento, por lo que el valor de este nodo será igual al valor en la posición del array inicial correspondiente.

Ahora podemos construir el árbol comenzando con las hojas, asignamos a todos los nodos hoja el valor de la posición correspondiente del array, y se combinan para calcular el valor del nodo del nivel superior, por ejemplo el nodo que guarda el valor $a[0 \dots 0]$ y el nodo $a[1 \dots 1]$ se combinan para obtener el valor del nodo $a[0 \dots 1]$ como se muestra en el ejemplo:

Este proceso se realiza recursivamente comenzando con el nodo raiz (el nodo $a[0 \dots 4]$) y descendiendo hacia abajo hasta llegar a las hojas, después, construir cada hoja de forma trivial y combinar los nodos cuando se empieza a volver de la recursión. Esta operación tarda $O(n)$ ya que se combinan nodos n veces, y la construcción de las hojas es en $O(1)$.

Petición de suma

Ahora el árbol está construido y queremos saber la suma de los elementos en el intervalo $a[l \dots r]$. Usaremos los valores de los intervalos precomputados para ahorrarnos mucho tiempo.

Vamos a asumir que buscando el intervalo $a[l \dots r]$ deseado, nos encontramos en el nodo que representa al intervalo $a[tl \dots tr]$. Hay tres casos posibles:

Procesar una petición de suma consiste en ir buscando recursivamente todos los nodos que representen el intervalo total sin solaparse

Petición de actualización

Ahora queremos modificar un elemento del array inicial. Tenemos que modificar el árbol, pero es más simple que encontrar la suma.

Recursivamente tenemos que descender el árbol hasta llegar al nodo hoja correspondiente, modificar el valor de este nodo, y al volver hacia atrás en la recursión combinar el nuevo valor con el valor del otro hijo.

Implementación

Ahora solo queda el código de ejemplo. Falta mencionar cómo se puede guardar el árbol en un array:

Estas 4 funciones muestran todas las funciones necesarias para resolver la mayoría de problemas de segment trees. En este código se resuelve el problema de la suma de elementos en un segmento:

const int MAXN = 10000; // el valor máximo de elementos en el array según el problema
int t[4*MAXN];

/* 
En algunos problemas será necesario crear un árbol de un tipo de dato personalizado, debemos utilizar un struct

struct custom_node {
    int sum, pref, suff, ans;
}

custom_node t[4*MAXN];

custom_node combine(custom_node a, custom_node b) {
    ...
}
*/

int combine(int a, int b) {
    return a+b
}

void build(int a[], int v, int tl, int tr) {
    if (tl == tr) {
        t[v] = a[tl];
    } else {
        int tm = (tl + tr) / 2;
        build(a, v*2, tl, tm);
        build(a, v*2+1, tm+1, tr);
        t[v] = combine(t[v*2], t[v*2+1]);
    }
}

int sum(int v, int tl, int tr, int l, int r) {
    if (l > r)              return 0;
    if (l == tl && r == tr) return t[v];

    int tm = (tl + tr) / 2;
    return sum(v*2, tl, tm, l, min(r, tm))
        + sum(v*2+1, tm+1, tr, max(l, tm+1), r);
}

void update(int v, int tl, int tr, int pos, int new_val) {
    if (tl == tr) t[v] = new_val;
    else {
        int tm = (tl + tr) / 2;
        if (pos <= tm)  update(v*2, tl, tm, pos, new_val);
        else            update(v*2+1, tm+1, tr, pos, new_val);
        t[v] = combine(t[v*2], t[v*2+1]);
    }
}

Anexo

Disjoint Set Union

La estructura de datos Disjoint Set Union (o DSU) sirve para combinar conjuntos de elementos e identificar a que conjunto pertenece un elemento. Por añadir contexto, vamos a utilizar esta estructura de datos para resolver el algoritmo de Kruskal, donde queremos saber si la próxima arista uniría a dos nodos en el mismo componente conexo o no:

En la figura de encima, la arista roja pertenece al árbol de expansión mínimo, pero ¿cómo lo sabríamos? Tanto el nodo '4' como el '6' están conectados a algo, pero como no pertenecen al mismo componente conexo se deben unir e incluir la arista en el árbol de expansión mínimo.

¿Cómo funciona?

Existen 3 operaciones para esta estructura de datos:

// const int NUM_NODOS = 8;
int nodoPadre[ /*NUM_NODOS*/ ];

void make_set(int v) {
    nodoPadre[v] = v;
}

int find_set(int v) {
    if (v == nodoPadre[v]) return v;
    return find_set(nodoPadre[v]);
}

void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) nodoPadre[b] = a;
}

Con estas operaciones podemos realizar el algoritmo de Kruskal. Asumiendo que se utilizan aristas por orden de menor peso, podemos observar como se emplea DSU para evitar unir nodos en el mismo componente conexo (después de la primera figura se saltan varios pasos)

Pequeña optimización

Asumimos ahora que después de unir nodos obtenemos una cadena muy larga de nodos para unir al conjunto:

Esto es ineficiente porque la operación find_set tendrá un coste de $O(N)$, podemos realizar un cambio para optimizar la estructura de datos:

int find_set(int v) {
    if (v == parent[v]) return v;
    return parent[v] = find_set(parent[v]);
    // En una línea, actualizar parent[v] y devolver el valor
}

Ahora cada vez que consultemos el representante de un nodo, ese nodo y todos los nodos padres apuntarán directamente al representante: