Árbol de segmento

En ciencias de la computación, un árbol de segmento (en inglés: Segment tree) es una estructura de datos en forma de árbol para guardar intervalos o segmentos. Permite consultar cuál de los segmentos guardados contiene un punto. Este es, en principio, una estructura estática; es decir, su contenido no puede ser modificado una vez que su estructura es construida. Una estructura de datos similar es el árbol de intervalo.

Un árbol de segmento para un conjunto I de n intervalos usa O(n log n) de memoria de almacenamiento y puede construirse en un tiempo O(n log n). Los árboles de segmento soportan búsqueda para todos los intervalos que contienen un punto de consulta en O(log n + k), k el número de intervalos o segmentos recuperados.^[1]

Algunas aplicaciones del árbol de segmento son vistas en las áreas de la geometría computacional y en los sistemas de información geográfica.

El árbol de segmentos puede generalizarse para espacios multidimensionales.

Descripción de estructura

Esta sección describe la estructura de un árbol de segmento en un espacio de una dimensión.

Sea S un conjunto de intervalos o segmentos. Sea p₁, p₂, ..., p_m una lista de distintos puntos extremos de intervalos, ordenada de izquierda a derecha. Considere la división de la línea de los números reales provocado por estos puntos. La región de esta división es llamada intervalos elementales. Por tanto, los intervalos elementales son, de izquierda a derecha:

(-\infty ,p_{1}),[p_{1},p_{1}],(p_{1},p_{2}),[p_{2},p_{2}],...,(p_{m-1},p_{m}),[p_{m},p_{m}],(p_{m},+\infty )

Es decir, la lista de intervalos elementales está compuesta de intervalos abiertos entre dos puntos finales consecutivos p_i y p_i+1, alternándose con intervalos cerrados compuesto por un único punto extremo. Puntos por separados son tratados como intervalos porque la respuesta a una consulta no es necesariamente la misma en el interior de un intervalo elemental que en sus puntos extremos.^[2]

Dado un conjunto I de intervalos o segmentos, un árbol de segmento T para I está estructurado de la siguiente manera:

T es un árbol binario.
Sus nodos hojas corresponden a los intervalos elementales provocados por los puntos extremos en I, en una forma ordenada: la hoja más a la izquierda coincide con el intervalo más a la izquierda. El intervalo elemental correspondiente a una hoja v es denotado por Int(v).
Los nodos internos de T coinciden con intervalos que son la unión de intervalos elementales: el intervalo Int(N) correspondiente al nodo N es la unión de los intervalos correspondientes a las hojas del subárbol con raíz en N. Eso implica que Int(N) es la unión de los intervalos de sus dos hijos.
Cada nodo v en T almacena el intervalo Int(v) y un conjunto de intervalos, en alguna estructura de datos. Este subconjunto canónico del nodo v contiene los intervalos [x, x′] de I tal que [x, x′] contiene Int(v) y no contiene Int(padre(v)). Es decir, cada segmento en I almacena los segmentos que abarcan completamente su intervalo, pero no abarca completamente el intervalo de su padre.^[3]

Requerimientos de almacenamiento

Esta sección analiza el costo de almacenamiento de un árbol de segmento en un espacio de una dimensión.

Un árbol de segmento T en un conjunto I de n intervalos usa O(nlogn) de almacenamiento.

Prueba:

Lema: Cualquier intervalo [x, x′] de I es almacenado en el conjunto canónico para como máximo dos nodos en la misma profundidad.

Prueba: Sea v₁, v₂, v₃ tres nodos en la misma profundidad, enumerados de izquierda a derecha y p(v) el nodo padre de cualquier nodo v. Suponga [x, x′] es almacenado en v₁ y v₃. Esto significa que [x, x′] abarca todo el intervalo desde el punto extremo izquierdo de Int(v₁) hasta el punto extremo derecho de Int(v₃). Note que todo segmento en un nivel en particular no se solapa y se encuentra ordenado de izquierda a derecha: esto es verdadero por construcción para el nivel que contienen las hojas y la propiedad no se pierde cuando se mueve desde cualquier nivel al nivel inmediato superior por combinación de pares de segmentos adyacentes. Ahora p(v₂) = p(v₁) o el primero a la derecha del último (Los bordes en el árbol no se cruzan). En el primer caso, el punto más a la izquierda de Int(p(v₂)) es el mismo que el punto más a la izquierda de Int(v₁); en el segundo caso, el punto más a la izquierda de Int(p(v₂)) está a la derecha del punto más a la derecha de Int(p(v₁)), por lo tanto también está a la derecha del punto más a la derecha de Int(v₁). En ambos casos Int(p(v₂)) comienza en/a la derecha del punto más a la izquierda de Int(v₁). Razonamiento similar muestra que Int(p(v₂)) termina en/a la izquierda del punto más a la derecha de Int(v₃). Int(p(v₂)) en consecuencia debe estar contenido en [x, x′]; por eso, [x, x′] no podrá estar almacenado en v₂.

El conjunto I tiene como máximo 4n + 1 intervalo elemental. Porque T es un árbol balanceado con a lo máximo 4n + 1 nodos hojas, su altura es O(logn). Como cualquier intervalo es almacenado a lo máximo dos veces en una profundidad del árbol, entonces la cantidad total almacenada es O(nlogn).^[4]

Construcción

Esta sección describe la construcción de un árbol de segmento en un espacio de una dimensión.

Un árbol de segmento desde el conjunto de segmentos I, puede ser construido como sigue. Primero, los puntos finales de los intervalos en I se ordenan. Los intervalos elementales son obtenidos desde este. Entonces, un árbol binario balanceado es construido con los intervalos elementales y para cada nodo v es determinado el intervalo Int(v) que este representa. Quedando computar los subconjuntos canónicos para los nodos. Para lograr esto, los intervalos en I son insertados uno por uno en el árbol de segmento. Un intervalo X = [x, x′] puede ser insertado en un subárbol en T, usando el siguiente procedimiento:^[5]

Si Int(T) está contenido en X entonces se almacena X en T y final.
Si no:
Si X se interseca con el subconjunto canónico del hijo izquierdo de T entonces inserta X en este hijo, recursivamente.
Si X se interseca con el subconjunto canónico del hijo derecho de T entonces inserta X en este hijo, recursivamente.

La operación de construcción completa toma un tiempo O(nlogn), donde n es el número de segmentos en I.

Prueba

Ordenar los puntos finales toma un tiempo O(nlogn). Construir un árbol binario balanceado desde los puntos finales ordenados toma tiempo lineal con respecto a n.

La inserción de un intervalo X = [x, x′] en el árbol cuesta O(logn).

Prueba: Visitar cada nodo toma un tiempo constante (asumiendo que los subconjuntos canónicos son almacenados en una estructura de datos simple como una lista enlazada). Cuando nosotros visitamos el nodo v nosotros almacenamos X en v o Int(v) contiene un punto extremo de X. Como se prueba arriba, un intervalo es almacenado a lo máximo dos veces en cada nivel del árbol. Hay también a lo máximo un nodo en cada nivel cuyo intervalo correspondiente contiene a x y un nodo cuyo intervalo contiene a x′. Así que, a lo sumo cuatro nodos por nivel son visitados. Debido a que hay O(logn) niveles, el costo total de la inserción es O(logn).^[1]

Algoritmo para la construcción de un árbol de segmento en C++:

#include <cstdio>
#include <vector>

//Tipo de los puntos
#define Point float
//Representa +infinito
#define FLT_MAX 1E+37

using namespace std;

struct Segment
{
    Point minValue;
    Point maxValue;
};

//Nodos del árbol de segmento
struct BinaryTree
{
    Point minValue;
    bool minOpen;
    Point maxValue;
    bool maxOpen;
    vector<Segment> subSet;
    BinaryTree *leftChild;
    BinaryTree *rightChild;
};

//Built methods

//Comparar dos puntos
//utilizados para ordenar la lista de puntos extremos
int cmp(const void *arg1, const void *arg2)
{
    Point value1 = *(Point *)arg1;
    Point value2 = *(Point *)arg2;
    if (value1 < value2)
        return -1;
    if (value1 > value2)
        return 1;
    return 0;
}

inline BinaryTree* Union(BinaryTree* nodeMin, BinaryTree* nodeMax)
{
    BinaryTree* result = new BinaryTree();
    result->minValue = nodeMin->minValue;
    result->minOpen = nodeMin->minOpen;
    result->maxValue = nodeMax->maxValue;
    result->maxOpen = nodeMax->maxOpen;
    return result;
}

inline BinaryTree* CreateLeafNode(Point minValue, Point maxValue, bool minOpen, bool maxOpen)
{
    BinaryTree* newNode = new BinaryTree();
    newNode->minOpen = minOpen;
    newNode->maxOpen = maxOpen;
    newNode->minValue = minValue;
    newNode->maxValue = maxValue;
    newNode->leftChild = 0;
    newNode->rightChild = 0;
    newNode->subSet = vector<Segment>();
    return newNode;
}

BinaryTree* BuiltBalancedBinaryTree(Point endPoints[], int countEndPoint)
{
        BinaryTree* elementaryInterval[countEndPoint * 2 + 1];
        Point minValue = -FLT_MAX;
        for(int i = 0; i < countEndPoint; i++)
        {
            int towI = 2 * i;
            elementaryInterval[towI] = CreateLeafNode(minValue, endPoints[i], true, true);
            elementaryInterval[towI + 1] = CreateLeafNode(endPoints[i], endPoints[i], false, false);
            minValue = endPoints[i];
        }
        int countNodes = countEndPoint * 2 + 1;
        elementaryInterval[countNodes - 1] = CreateLeafNode(endPoints[countEndPoint - 1], FLT_MAX, true, true);
        while (countNodes > 1)
        {
            for(int i = 0; i < countNodes / 2; i++)
            {
                int towI = 2 * i;
                BinaryTree *newNode = Union(elementaryInterval[towI], elementaryInterval[towI + 1]);
                newNode->leftChild = elementaryInterval[towI];
                newNode->rightChild = elementaryInterval[towI + 1];
                newNode->subSet = vector<Segment>();
                elementaryInterval[i] = newNode;
            }
            if (countNodes % 2)
            {
                elementaryInterval[countNodes / 2] = elementaryInterval[countNodes - 1];
            }
            countNodes = countNodes / 2 + (countNodes % 2);
        }
        return elementaryInterval[0];
}

inline bool ContainsIntNode(Segment segment, BinaryTree *tree)
{
    return tree->minValue >= segment.minValue & tree->maxValue <= segment.maxValue;
}

inline bool IntersectIntNode(Segment segment, BinaryTree *tree)
{
     return (segment.minValue < tree->maxValue | (segment.minValue == tree->maxValue & !tree->maxOpen))
        & (segment.maxValue > tree->minValue | (segment.maxValue == tree->minValue & !tree->minOpen));
}

void InsertSegment(Segment segment, BinaryTree *tree)
{
    if (ContainsIntNode(segment, tree))
    {
        tree->subSet.push_back(segment);
        return;
    }
    //Si es nodo hoja
    if (!tree->leftChild)
        return;
    if (IntersectIntNode(segment, tree->leftChild))
        InsertSegment(segment, tree->leftChild);
    if (IntersectIntNode(segment, tree->rightChild))
        InsertSegment(segment, tree->rightChild);
}

void DeleteEqualPoint(Point *endPoint, int *countEndPoint)
{
    int count = *countEndPoint;
    int index = 0;
    int i = 0;
    while (i < count)
    {
        endPoint[index] = endPoint[i];
        while (i < count && endPoint[index] == endPoint[i])
            i++;
        index++;
    }
    *countEndPoint = index;
}

//Crea el árbol de segmento a partir del conjunto de segmentos
BinaryTree* BuiltTree(Segment segments[], int segmentCount)
{
    int countEndPoint = segmentCount * 2;
    Point *endPoints = new Point[countEndPoint];
    for(int i = 0; i < segmentCount; i++)
    {
        int towI = 2 * i;
        endPoints[towI] = segments[i].maxValue;
        endPoints[towI + 1] = segments[i].minValue;
    }
    qsort(endPoints, countEndPoint, sizeof(Point), cmp);
    DeleteEqualPoint(endPoints, &countEndPoint);
    BinaryTree *tree = BuiltBalancedBinaryTree(endPoints, countEndPoint);
    delete [] endPoints;
    for (int i = 0; i < segmentCount; i++)
        InsertSegment(segments[i], tree);
    return tree;
}

//Libera la memoria ocupada por el árbol construido
void DeleteTree(BinaryTree *tree)
{
    if (tree->leftChild != 0)
        DeleteTree(tree->leftChild);
    if (tree->rightChild != 0)
        DeleteTree(tree->rightChild);
    delete tree;
}

Consulta

Esta sección describe la operación de consulta de un árbol de segmento en un espacio de una dimensión.

Una consulta para un árbol de segmento, recibe un punto q_x y recupera una lista de todos los segmentos almacenados que contienen el punto q_x.

Formalmente; dado un nodo (subárbol) v y un punto de consulta q_x, la consulta puede ser hecha usando el siguiente algoritmo:

Reportar todos los intervalos en I(v).
Si v no es una hoja:
- Si q_x está en Int(hijo izquierdo de v) entonces
  - Realizar una consulta en el hijo izquierdo de v.
- Si q_x está en Int(hijo derecho de v) entonces
  - Realizar una consulta en el hijo derecho de v.

En un árbol de segmento que contiene n intervalos, quienes contienen un punto de consulta pueden ser reportados en un tiempo O(logn + k), donde k es el número de intervalos reportados.

Prueba: El algoritmo de consulta visita un nodo por nivel del árbol, así que en total visita O(logn) nodos. Por otro lado, en un nodo v, los segmentos en I son reportados en un tiempo O(1 + k_v), donde k_v es el número de intervalos en el nodo v reportados. La suma de todos los k_v para todos los nodos v visitados es k el número de segmentos reportados.^[4]

Algoritmo para realizar consultas en el árbol de segmento construido con el algoritmo anterior:

//Query methods
inline bool ContainPoint(BinaryTree *tree, Point point)
{
    return (tree->minValue < point | (tree->minValue == point & !tree->minOpen))
        & (tree->maxValue > point |  (tree->maxValue == point & !tree->maxOpen));
}

void Query(BinaryTree *tree, Point point, vector<Segment> *report)
{
    if (ContainPoint(tree, point))
    {
        int sizeSubSet = tree->subSet.size();
        for(int i = 0; i < sizeSubSet; i++)
        {
            (*report).push_back(tree->subSet[i]);
        }
    }
    //Si es nodo hoja
    if (!tree->leftChild)
        return;
    if (ContainPoint(tree->leftChild, point))
        Query(tree->leftChild, point, report);
    if (ContainPoint(tree->rightChild, point))
        Query(tree->rightChild, point, report);
}

Generalización para espacios multidimensionales

El árbol de segmento puede ser generalizado a espacios multidimensionales, en forma de árbol de segmento multinivel. En versiones multidimensionales, el árbol de segmento almacena una colección de rectángulos de ejes paralelos y puede recuperar los rectángulos que contienen un punto de consulta dado. La estructura usa O(nlog^dn) de almacenamiento y responde consultas en O(log^dn). El uso de fractional cascading baja el tiempo de consulta por un factor logarítmico. El uso del árbol de intervalo en el nivel más profundo de las estructuras asociadas baja el almacenamiento con un factor logarítmico.^[6]

Notas

La consulta que pregunta por todos los intervalos que contienen un punto dado, es a menudo referida como stabbing query.^[7]

El árbol de segmento es menos eficiente que el árbol de intervalo para consultas con rangos en una dimensión, debido a su requisito de almacenamiento más alto: O(nlogn) en contra del O(n) del árbol de intervalo. Lo importante del árbol de segmento es que los segmentos dentro del subconjunto canónico de cada nodo pueden ser almacenados de cualquier manera arbitraria.^[7]

Para n intervalos cuyos puntos finales están en el rango de un entero pequeño (small integer), existe una estructura de datos óptima con un tiempo de procesamiento lineal y un tiempo de consulta O(1+k) para reportar todos los k intervalos que contienen al punto de consulta dado.

Otra ventaja del árbol de segmento es que puede ser fácilmente adaptado para consultas de cantidad; esto es, reportar el número de segmentos que contienen un punto dado, en lugar de reportar todos los segmentos. En lugar de guardar los intervalos en subconjuntos canónicos, puede simplemente guardar el número de ellos. Semejante árbol de segmento usa almacenamiento lineal y requiere un tiempo de consulta O(logn), así que es óptimo.^[8]

Una versión multidimensional del árbol de intervalo es árbol de búsqueda con prioridad y no existe, es decir, no hay ninguna extensión clara de estas estructuras que solucione el problema análogo multidimensional. Pero las estructuras pueden ser usadas como estructura asociada de árboles de segmentos.^[6]

Historia

El árbol de segmento fue descubierto por J. L. Bentley en 1977; en "Solutions to Klee’s rectangle problems".^[7]

Referencias

↑ ^a ^b (de Berg et al., 2000, p. 227)
↑ (de Berg et al., 2000, p. 224)
↑ (de Berg et al., 2000, pp. 225–226)
↑ ^a ^b (de Berg et al., 2000, p. 226)
↑ (de Berg et al., 2000, pp. 226–227)
↑ ^a ^b (de Berg et al., 2000, p. 230)
↑ ^a ^b ^c (de Berg et al., 2000, p. 229)
↑ (de Berg et al., 2000, pp. 229–230)

Fuentes citadas

de Berg, Mark; van Kreveld, Marc; Overmars, Mark; Schwarzkopf, Otfried (2000). «More Geometric Data Structures». Computational Geometry: algorithms and applications (2nd edición). Springer-Verlag Berlin Heidelberg New York. ISBN 3-540-65620-0. doi:10.1007/978-3-540-77974-2.
http://www.cs.nthu.edu.tw/~wkhon/ds/ds10/tutorial/tutorial6.pdf

Datos: Q2377385

[Schwarzkopf1-1] (de Berg et al., 2000, p. 227)

[2] (de Berg et al., 2000, p. 224)

[3] (de Berg et al., 2000, pp. 225–226)

[Schwarzkopf2-4] (de Berg et al., 2000, p. 226)

[5] (de Berg et al., 2000, pp. 226–227)

[Schwarzkopf3-6] (de Berg et al., 2000, p. 230)

[Schwarzkopf4-7] (de Berg et al., 2000, p. 229)

[8] (de Berg et al., 2000, pp. 229–230)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]