Árbol de intervalos – Part 1

Considere una situación en la que tenemos un conjunto de intervalos y necesitamos que las siguientes operaciones se implementen de manera eficiente. 
1) Agregar un intervalo 
2) Eliminar un intervalo 
3) Dado un intervalo x, encuentre si x se superpone con alguno de los intervalos existentes.
Árbol de intervalos: la idea es aumentar un árbol de búsqueda binaria (BST) autoequilibrado como Red Black Tree , AVL Tree , etc. para mantener un conjunto de intervalos para que todas las operaciones se puedan realizar en tiempo O (Inicio de sesión). 
Cada Node de Interval Tree almacena la siguiente información. 
a) i : Un intervalo que se representa como un par [bajo, alto] 
b) max : Máximo altovalor en el subárbol enraizado con este Node.
El valor bajo de un intervalo se utiliza como clave para mantener el orden en BST. Las operaciones de inserción y eliminación son las mismas que las de inserción y eliminación en el BST de autoequilibrio utilizado. 
 

La operación principal es buscar un intervalo superpuesto. El siguiente es un algoritmo para buscar un intervalo superpuesto x en un árbol de intervalos enraizado con root . 

Interval overlappingIntervalSearch(root, x)
1) If x overlaps with root's interval, return the root's interval.

2) If left child of root is not empty and the max  in left child 
is greater than x's low value, recur for left child

3) Else recur for right child.

¿Cómo funciona el algoritmo anterior?  
Sea x el intervalo a buscar. Necesitamos probar esto en los siguientes dos casos.
Caso 1: cuando vamos al subárbol derecho, uno de los siguientes debe ser verdadero.  
a) Hay una superposición en el subárbol derecho: esto está bien ya que necesitamos devolver un intervalo superpuesto. 
b) No hay superposición en ninguno de los subárboles: vamos al subárbol derecho solo cuando el izquierdo es NULL o el valor máximo en el izquierdo es menor que x.low . Entonces el intervalo no puede estar presente en el subárbol izquierdo.
Caso 2: Cuando vamos al subárbol izquierdo, uno de los siguientes debe ser verdadero.  
a) Hay una superposición en el subárbol izquierdo: esto está bien ya que necesitamos devolver un intervalo superpuesto. 
b) No hay superposición en ninguno de los subárboles: esta es la parte más importante. Necesitamos considerar los siguientes hechos. 
… Fuimos al subárbol izquierdo porque x.low <= max en el subárbol izquierdo 
…. max en el subárbol izquierdo es un máximo de uno de los intervalos, digamos [a, max] en el subárbol izquierdo. 
…. Dado que x no se superpone con ningún Node en el subárbol izquierdo , x.high debe ser más pequeño que ‘ a ‘. 
…. Todos los Nodes en BST están ordenados por valor bajo, por lo que todos los Nodes en el subárbol derecho deben tener un valor bajo mayor que ‘ a ‘. 
…. De los dos hechos anteriores, podemos decir que todos los intervalos en el subárbol derecho tienen un valor bajo mayor que x.high . Entonces xno puede superponerse con ningún intervalo en el subárbol derecho.
Implementación del árbol de intervalos: 
A continuación se muestra la implementación en C++ del árbol de intervalos. La implementación utiliza la operación de inserción básica de BST para simplificar las cosas. Idealmente, debería ser la inserción de AVL Tree o la inserción de Red-Black Tree . La eliminación de BST se deja como ejercicio.
 

#include <iostream>
using namespace std;
 
// Structure to represent an interval
struct Interval
{
    int low, high;
};
 
// Structure to represent a node in Interval Search Tree
struct ITNode
{
    Interval *i;  // 'i' could also be a normal variable
    int max;
    ITNode *left, *right;
};
 
// A utility function to create a new Interval Search Tree Node
ITNode * newNode(Interval i)
{
    ITNode *temp = new ITNode;
    temp->i = new Interval(i);
    temp->max = i.high;
    temp->left = temp->right = NULL;
    return temp;
};
 
// A utility function to insert a new Interval Search Tree Node
// This is similar to BST Insert.  Here the low value of interval
// is used tomaintain BST property
ITNode *insert(ITNode *root, Interval i)
{
    // Base case: Tree is empty, new node becomes root
    if (root == NULL)
        return newNode(i);
 
    // Get low value of interval at root
    int l = root->i->low;
 
    // If root's low value is smaller, then new interval goes to
    // left subtree
    if (i.low < l)
        root->left = insert(root->left, i);
 
    // Else, new node goes to right subtree.
    else
        root->right = insert(root->right, i);
 
    // Update the max value of this ancestor if needed
    if (root->max < i.high)
        root->max = i.high;
 
    return root;
}
 
// A utility function to check if given two intervals overlap
bool doOVerlap(Interval i1, Interval i2)
{
    if (i1.low <= i2.high && i2.low <= i1.high)
        return true;
    return false;
}
 
// The main function that searches a given interval i in a given
// Interval Tree.
Interval *overlapSearch(ITNode *root, Interval i)
{
    // Base Case, tree is empty
    if (root == NULL) return NULL;
 
    // If given interval overlaps with root
    if (doOVerlap(*(root->i), i))
        return root->i;
 
    // If left child of root is present and max of left child is
    // greater than or equal to given interval, then i may
    // overlap with an interval is left subtree
    if (root->left != NULL && root->left->max >= i.low)
        return overlapSearch(root->left, i);
 
    // Else interval can only overlap with right subtree
    return overlapSearch(root->right, i);
}
 
void inorder(ITNode *root)
{
    if (root == NULL) return;
 
    inorder(root->left);
 
    cout << "[" << root->i->low << ", " << root->i->high << "]"
         << " max = " << root->max << endl;
 
    inorder(root->right);
}
 
// Driver program to test above functions
int main()
{
    // Let us create interval tree shown in above figure
    Interval ints[] = {{15, 20}, {10, 30}, {17, 19},
        {5, 20}, {12, 15}, {30, 40}
    };
    int n = sizeof(ints)/sizeof(ints[0]);
    ITNode *root = NULL;
    for (int i = 0; i < n; i++)
        root = insert(root, ints[i]);
 
    cout << "Inorder traversal of constructed Interval Tree is\n";
    inorder(root);
 
    Interval x = {6, 7};
 
    cout << "\nSearching for interval [" << x.low << "," << x.high << "]";
    Interval *res = overlapSearch(root, x);
    if (res == NULL)
        cout << "\nNo Overlapping Interval";
    else
        cout << "\nOverlaps with [" << res->low << ", " << res->high << "]";
    return 0;
}

Producción: 

Inorder traversal of constructed Interval Tree is
[5, 20] max = 20
[10, 30] max = 30
[12, 15] max = 15
[15, 20] max = 40
[17, 19] max = 40
[30, 40] max = 40

Searching for interval [6,7]
Overlaps with [5, 20]

Aplicaciones del árbol de intervalos: el 
árbol de intervalos es principalmente una estructura de datos geométricos y, a menudo, se usa para consultas de ventanas, por ejemplo, para encontrar todas las carreteras en un mapa computarizado dentro de una ventana gráfica rectangular, o para encontrar todos los elementos visibles dentro de una escena tridimensional (Fuente wiki ).
Árbol de intervalos frente a árbol 
de segmentos Tanto los árboles de segmentos como los de intervalos almacenan intervalos. El árbol de segmentos está optimizado principalmente para consultas de un punto determinado, y los árboles de intervalos están optimizados principalmente para consultas superpuestas de un intervalo determinado.
Ejercicio: 
1) Implementar la operación de eliminación para el árbol de intervalos. 
2) Extienda la búsqueda de intervalos() para imprimir todos los intervalos superpuestos en lugar de solo uno. 
http://en.wikipedia.org/wiki/Interval_tree 
http://www.cse.unr.edu/~mgunes/cs302/IntervalTrees.pptx  
Introducción a los algoritmos 3.ª edición por Clifford Stein, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest  
https://www.youtube .com/watch?v=dQF0zyaym8A
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.