Enlace/árbol cortado
Un árbol de enlace/corte es una estructura de datos para representar un bosque , un conjunto de árboles enraizados , y ofrece las siguientes operaciones:
El bosque representado puede consistir en árboles muy profundos, por lo que si representamos el bosque como una colección simple de árboles punteros principales , puede llevarnos mucho tiempo encontrar la raíz de un nodo determinado. Sin embargo, si representamos cada árbol en el bosque como un árbol de enlace/corte, podemos encontrar a qué árbol pertenece un elemento en O (log( n )) tiempo amortizado. Además, podemos ajustar rápidamente la colección de enlaces/árboles cortados a los cambios en el bosque representado. En particular, podemos ajustarlo para fusionar (enlazar) y dividir (cortar) en O ( log (n)) tiempo amortizado .
Los árboles de enlace/corte dividen cada árbol en el bosque representado en caminos separados por vértices, donde cada camino está representado por una estructura de datos auxiliar (a menudo árboles separados , aunque el documento original es anterior a los árboles separados y, por lo tanto, utiliza árboles de búsqueda binarios sesgados). Los nodos en la estructura de datos auxiliar están ordenados por su profundidad en el árbol representado correspondiente. En una variación, Naive Partitioning , las rutas están determinadas por las rutas y los nodos a los que se accedió más recientemente, de forma similar a Tango Trees . En partición por tamañolas rutas están determinadas por el hijo más pesado (hijo con la mayoría de los hijos) del nodo dado. Esto da una estructura más complicada, pero reduce el costo de las operaciones de amortizado O (log n) al peor de los casos O (log n). Tiene usos para resolver una variedad de problemas de flujo de red y para organizar conjuntos de datos.
En la publicación original, Sleator y Tarjan se refirieron a los árboles de enlace/corte como "árboles dinámicos" o "árboles dinamómetros dinámicos".
Tomamos un árbol donde cada nodo tiene un grado arbitrario de nodos desordenados y lo dividimos en caminos. A esto lo llamamos el árbol representado . Estos caminos están representados internamente por árboles auxiliares (aquí usaremos árboles separados), donde los nodos de izquierda a derecha representan el camino desde la raíz hasta el último nodo del camino. Los nodos que están conectados en el árbol representado que no están en la misma ruta preferida (y, por lo tanto, no están en el mismo árbol auxiliar) se conectan a través de un puntero principal de ruta . Este puntero se almacena en la raíz del árbol auxiliar que representa la ruta.
Cuando se realiza un acceso a un nodo v del árbol representado , el camino que se toma se convierte en el camino preferente . El hijo preferido de un nodo es el último hijo que estaba en la ruta de acceso, o nulo si el último acceso fue a v o si no se hizo ningún acceso a esta rama particular del árbol. Un borde preferido es el borde que conecta el hijo preferido con v .
