Árbol de intervalos utilizando un contenedor basado en árboles GNU

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 cualquiera de los intervalos existentes.

Un árbol de intervalos se puede implementar como un árbol de búsqueda binaria aumentada (preferiblemente autoequilibrado) y, por lo tanto, nos permite realizar las operaciones requeridas en una complejidad de tiempo O (logN). 

Cada Node del árbol almacenará la siguiente información: 

1. Un intervalo i : representado como un par [bajo, alto].
2. Metadata max of right-endpoints : el máximo de los puntos finales derechos de todos los intervalos almacenados en el subárbol enraizado en este Node. Almacenar estos metadatos es cómo estamos aumentando el árbol.

Ejemplo de árbol de intervalos utilizado en el árbol de intervalos | Conjunto 1 : 

en el árbol de intervalos | Conjunto 1 , vimos cómo implementar un árbol de intervalo usando un BST simple (que no es autoequilibrado). En este artículo, utilizaremos el contenedor integrado basado en árboles de GNU para implementar un árbol de intervalos. Los beneficios de hacerlo son: 

• No tenemos que codificar nuestra propia estructura de datos de árbol.
• Obtenemos las operaciones predeterminadas como insertar y eliminar listas para usar.
• Podemos usar la implementación del árbol rojo-negro incorporado , lo que significa que nuestro árbol se autoequilibrará .

Usaremos la implementación basada en políticas de GNU de la estructura de datos de árbol . 

El artículo Estructuras de datos basadas en políticas en g++ presenta la estructura de datos basada en políticas de GNU junto con los archivos de encabezado necesarios. 

Definiremos nuestra propia política Node_update de modo que podamos mantener el máximo de extremos derechos de intervalos en el subárbol como metadatos en los Nodes de nuestro árbol. 

La sintaxis para definir una Node_policy personalizada es: 

template <
    typename Const_Node_Iterator,
    typename Node_Iterator,
    typename Cmp_Fn_,
    typename Allocator_>
;
struct custom_node_update_policy {
    typedef type_of_our_metadata
        metadata_type;
 
    void operator()(
        node_iterator it,
        const_node_iterator end_it)
    {
        // ...
    }
 
    // ...other methods that we need
}

• type_of_our_metadata: int en nuestro caso, ya que queremos almacenar los metadatos «máximo de extremos derechos de intervalos en el subárbol».
• void operator()(node_iterator it, const_node_iterator end_it): método que se llama internamente para restaurar la invariancia del Node , es decir, mantener los metadatos correctos, después de que se haya invalidado la invariancia. 
• it: node_iterator al Node cuya invariancia necesitamos restaurar.
• end_it : const_node_iterator a un Node justo después de la hoja.

Consulte Contenedores basados ​​en árboles de GNU para obtener más detalles.

También definiremos un método de búsqueda por superposición que busca cualquier intervalo en el árbol que se superponga con un intervalo i dado .

// pseudocode for overlapSearch

Interval overlapSearch(Interval i) {
    // start from root
    it = root_node

    while (it not null) {
        if (doOVerlap(i, it->interval)) {
              // overlap found
               return it->interval
        }

        if (left_child exists
                     AND
             left_child->max_right_endpoint
                   >= it->left_endpoint) {
            // go to left child
            it = it->left_child
        }

        else {
            // go to right child
            it = it->right_child
        }
    }

    // no overlapping interval found
    return NO_INTERVAL_FOUND
}

A continuación se muestra la implementación del árbol de intervalos:

// CPP program for above approach
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
typedef pair<int, int> Interval;
 
// An invalid interval, used as
// return value to denote that no
// matching interval was found
const Interval NO_INTERVAL_FOUND = { 1, 0 };
 
// interval update policy struct
template <class Node_CItr,
          class Node_Itr,
          class Cmp_Fn, class _Alloc>
struct interval_node_update_policy {
 
    // Our metadata is maximum of
    // right-endpoints of intervals in the
    // sub-tree, which is of type int
    typedef int metadata_type;
 
    // An utility function to check
    // if given two intervals overlap
    bool doOverlap(Interval i1,
                   Node_CItr i2)
    {
        return (i1.first <= (*i2)->second
                && (*i2)->first <= i1.second);
    }
 
    // Search for any interval that
    // overlaps with Interval i
    Interval overlapSearch(Interval i)
    {
        for (Node_CItr it = node_begin();
             it != node_end();) {
            if (doOverlap(i, it)) {
                return { (*it)->first,
                         (*it)->second };
            }
 
            if (it.get_l_child() != node_end()
                && it.get_l_child()
                           .get_metadata()
                       >= i.first) {
                it = it.get_l_child();
            }
            else {
                it = it.get_r_child();
            }
        }
        return NO_INTERVAL_FOUND;
    }
 
    // To restore the node-invariance
    // of the node pointed to by
    // (it). We need to derive the
    // metadata for node (it) from
    // its left-child and right-child.
    void operator()(Node_Itr it,
                    Node_CItr end_it)
    {
        int max_high = (*it)->second;
 
        if (it.get_l_child() != end_it) {
            max_high = max(
                max_high,
                it.get_l_child()
                    .get_metadata());
        }
 
        if (it.get_r_child() != end_it) {
            max_high = max(
                max_high,
                it.get_r_child()
                    .get_metadata());
        }
 
        // The max of right-endpoint
        // of this node and the max
        // right-endpoints of children.
        const_cast<int&>(
            it.get_metadata())
            = max_high;
    }
 
    virtual Node_CItr node_begin() const = 0;
    virtual Node_CItr node_end() const = 0;
    virtual ~interval_node_update_policy() {}
};
 
// IntervalTree data structure
// rb_tree_tag: uses red-black search tree
// interval_node_update_policy:
// our custom Node_update policy
typedef tree<Interval,
             null_type,
             less<Interval>,
             rb_tree_tag,
             interval_node_update_policy>
    IntervalTree;
 
// Driver Code
int main()
{
    IntervalTree IT;
    Interval intvs[] = { { 15, 20 },
                         { 10, 30 },
                         { 17, 19 },
                         { 5, 20 },
                         { 12, 15 },
                         { 30, 40 } };
 
    for (Interval intv : intvs) {
        IT.insert(intv);
    }
 
    Interval toSearch = { 25, 29 };
    cout << "\nSearching for interval ["
         << toSearch.first << ", "
         << toSearch.second << "]";
    Interval res = IT.overlapSearch(toSearch);
    if (res == NO_INTERVAL_FOUND)
        cout << "\nNo Overlapping Interval\n";
    else
        cout << "\nOverlaps with ["
             << res.first << ", "
             << res.second << "]\n";
 
    Interval toErase = { 10, 30 };
    IT.erase(toErase);
    cout << "\nDeleting interval ["
         << toErase.first << ", "
         << toErase.second
         << "]\n";
 
    cout << "\nSearching for interval ["
         << toSearch.first << ", "
         << toSearch.second << "]";
    res = IT.overlapSearch(toSearch);
    if (res == NO_INTERVAL_FOUND)
        cout << "\nNo Overlapping Interval\n";
    else
        cout << "\nOverlaps with ["
             << res.first << ", "
             << res.second << "]\n";
    return 0;
}

Searching for interval [25, 29]
Overlaps with [10, 30]

Deleting interval [10, 30]

Searching for interval [25, 29]
No Overlapping Interval

Complejidad del tiempo 

Todas las operaciones son de tamaño logarítmico, es decir, O(logN) , donde N es el número de intervalos almacenados en el árbol. 

Podemos lograr una complejidad logarítmica en el peor de los casos porque se usa internamente un árbol rojo-negro que es autoequilibrado.