En las matemáticas combinatorias y la informática teórica , la descomposición de trayectorias pesadas (también llamada descomposición ligera-pesada ) es una técnica para descomponer un árbol enraizado en un conjunto de trayectorias . En una descomposición de ruta pesada, cada nodo no hoja selecciona un "borde pesado", el borde del hijo que tiene el mayor número de descendientes (rompiendo los lazos arbitrariamente). Los bordes seleccionados forman los caminos de la descomposición.
Si los bordes de un árbol T están divididos en un conjunto de bordes pesados y bordes ligeros, con un borde pesado desde cada nodo que no es una hoja hasta uno de sus hijos, entonces el subgrafo formado por los bordes pesados consiste en un conjunto de caminos, con cada vértice no hoja perteneciente exactamente a un camino, el que contiene su borde pesado. Se puede considerar que los nodos de las hojas del árbol que no son el punto final de un borde grueso forman trayectorias de longitud cero. De esta forma, cada vértice pertenece exactamente a uno de los caminos. Cada camino tiene un vértice principal, su vértice superior.
Alternativamente, las trayectorias de los bordes pesados pueden extenderse incluyendo un borde ligero, el que va desde el principio de la trayectoria hasta su padre. [1] En esta variación de la descomposición, algunos vértices pertenecen a múltiples caminos, pero cada borde de T pertenece exactamente a un camino.
Los caminos de la descomposición pueden organizarse ellos mismos en un árbol llamado "árbol de caminos", "árbol de caminos pesados" o "árbol comprimido". Cada nodo del árbol de la ruta corresponde a una ruta de la descomposición de la ruta pesada. Si p es un camino de la descomposición de caminos pesados, entonces el padre de p en el árbol de caminos es el camino que contiene el padre de la cabeza de p . La raíz del árbol de ruta es la ruta que contiene la raíz del árbol original. Alternativamente, el árbol del camino puede formarse a partir del árbol original mediante la contracción del borde de todos los bordes pesados.
Un borde "ligero" de un árbol determinado es un borde que no se seleccionó como parte de la descomposición de la ruta pesada. Si un borde de luz conecta dos nodos del árbol x e y , con x el padre de Y , entonces x debe tener al menos el doble de los descendientes como y . Por lo tanto, en cualquier camino de raíz a hoja de un árbol con n nodos, puede haber como máximo log 2 n bordes claros. De manera equivalente, el árbol del camino tiene una altura máxima de log 2 n .
Sleator y Tarjan (1983) introdujeron la descomposición de trayectorias pesadas como parte del análisis amortizado de su estructura de árbol de enlace / corte , [2] y por Harel y Tarjan (1984) como parte de su estructura de datos para los antepasados comunes más bajos , [3 ] La estructura de datos de enlace / árbol cortado utiliza una partición de un árbol dinámico en rutas que no es necesariamente la descomposición de la ruta pesada; su análisis utiliza una función potencialmedir su distancia desde la descomposición de la ruta pesada y la pequeña altura del árbol de la ruta implica que cada operación de estructura de datos realiza solo una pequeña cantidad de pasos que no se pueden cargar contra las mejoras de esta función. [2] En la estructura de datos del ancestro común más bajo, la descomposición se utiliza para incrustar el árbol de entrada en un árbol binario completo de profundidad logarítmica, lo que permite que cada consulta se resuelva mediante operaciones bit a bit de tiempo constante . [3]