Un Interval Tree è una struttura dati ordinata i cui nodi rappresentano degli intervalli e sono quindi caratterizzati da un valore di inizio ed un valore di fine. Un esempio tipico di applicazione è quello in cui si hanno una serie di intervalli a disposizione ed un altro insieme di intervalli query, per i quali si vuole verificare la sovrapposizione con gli intervalli di partenza.
La figura seguente mostra un esempio in cui in blu sono rappresentati una serie di intervalli ed in giallo sono definiti i due intervalli query per cui vogliamo verificare la sovrapposizione con i precedenti:
Figura 1:
La struttura Interval Tree entra in gioco per fornire una soluzione più efficiente rispetto all’approccio naive di applicare una strategia forza bruta e di confrontare quindi ogni intervallo query con tutti quelli a disposizione verificando se, in base ai valori dei relativi estremi, esiste una sovrapposizione totale o parziale tra loro.
In particolare, per rendere più efficiente questo tipo di ricerca si può ricorrere ad un Augmented Interval Tree, una struttura in cui si aumenta l’informazione contenuta in ciascun nodo aggiungendo, oltre agli estremi dell’intervallo, anche l’informazione relativa all’estremo massimo del sottoalbero relativo al nodo che si sta analizzando. Questo valore deve essere calcolato in fase di inserimento di ciascun nodo ed essere aggiornato, a ritroso verso l’alto, in caso di cancellazione di un nodo.
Vediamo un esempio nel quale creiamo l’Augmented Interval Tree relativo ai nodi descritti in precedenza; ogni nodo contiene le informazioni dei suoi estremi, nel formato [5,10] e, sotto, l’informazione relativa al massimo valore del suo sottoalbero.
Figura 2:
Analizziamo la sequenza di inserimento: partendo dal nodo root [5,10] viene poi inserito il secondo nodo che ha come estremi i valori 15 e 25. In questo caso dobbiamo subito procedere con l’aggiornamento dell’informazione aggiuntiva sul massimo valore del sottoalbero per il primo nodo (terza figura in alto a destra). Il secondo nodo ha infatti come estremo massimo 25 e quindi tale valore deve essere riportato nel primo nodo (essendo il secondo nodo nel suo sottoalbero). Procedendo, vengono inseriti i nodi relativi agli intervalli [1,12] e [8,16] ed entrambi non richiedono aggiornamenti sul valore massimo degli altri nodi. 16 infatti, non è superiore al valore massimo di nessuno dei nodi attraversati (25 per entrambi). A questo punto inseriamo il nodo relativo all’intervallo [14,20]. In questo caso il nodo finisce nel sottoalbero di [8,16] e tale nodo ha proprio 16 come valore massimo. Essendo l’estremo 20 maggiore di 16, dobbiamo aggiornare nel nodo [8,16] l’informazione del valore massimo del sottoalbero, facendola passare appunto da 16 a 20. Inseriamo infine i nodi relativi agli ultimi due intervalli, [18,21] e [2,8] che però non richiedono l’aggiornamento di nessuno dei nodi che attravarsano, perchè i loro estremi superiori non superano il valore massimo del sottoalbero in cui finiscono.
Iniziamo ora ad implementare la classe che rappresenta i nodi, che conterrà quindi gli estremi dell’intervallo, l’estremo superiore massimo del sottoalbero ed i riferimenti ai suoi nodi figli destro e sinistro. A questa classe, che chiamiamo Interval, facciamo implementare l’interfaccia Comparable e ridefiniamo poi il metodo compareTo(), in quanto dobbiamo stabilire un criterio per confrontare i nodi e quindi determinarne la posizione di inserimento nell’albero. Inoltre forniamo anche un override del toString() che ci fornisca una rappresentazione leggibile dei nostri nodi, mostrando gli estremi degli intervalli e l’informazione aggiuntiva dell’estrema massimo del sottoalbero del nodo.
Alla luce di quanto detto, la nostra classe Interval sarà la seguente:
class Interval implements Comparable{ private long start; private long end; private long max; private Interval left; private Interval right; public Interval(long start, long end) { this.start = start; this.end = end; this.max = end; } @Override public String toString() { return "[" + this.getStart() + ", " + this.getEnd() + ", " + this.getMax() + "]"; } @Override public int compareTo(Interval i) { if (this.start < i.start) { return -1; } else if (this.start == i.start) { return this.end <= i.end ? -1 : 1; } else { return 1; } } // GETTERS E SETTERS OMESSI PER SEMPLICITA' }
Una volta descritta la struttura del singolo nodo, possiamo passare a definire il nostro Augmented Interval Tree tramite una classe che:
- contiene una reference di tipo Interval che rappresenta la root dell'albero
- fornisce un metodo per l'inserimento dei nuovi nodi
- fornisce un metodo per la stampa "ordinata" dei nodi dell'albero
Per l'inserimento dei nodi creiamo un metodo ricorsivo che percorre l'albero fino a quando non trova il punto corretto in cui il nodo deve essere inserito ed aggiorna inoltre, quando necessario, l'informazione aggiuntiva relativa all'estremo massimo del sottoalbero dei vari nodi. Per la stampa dell'albero, siccome ci interessa verificare se i nodi sono stati inseriti correttamente in base al valore del range che contengono ed al valore massimo del loro sottoalbero, utilizziamo il classico algoritmo ricorsivo di attraversamento ordinato di un albero binario In-Order Tree Traversal.
Creiamo quindi la classe AugmentedIntervalTree che, al momento, si presenta come segue:
public class AugmentedIntervalTree {
private Interval root;
public static Interval insertNode(Interval tmp, Interval newNode) {
if (tmp == null) {
tmp = newNode;
return tmp;
}
// Aggiorno l'estremo massimo del sottoalbero
// in fase di inserimento
if (newNode.getEnd() > tmp.getMax()) {
tmp.setMax(newNode.getEnd());
}
if (tmp.compareTo(newNode) <= 0) {
if (tmp.getRight() == null) {
tmp.setRight(newNode);
}
else {
insertNode(tmp.getRight(), newNode);
}
}
else {
if (tmp.getLeft() == null) {
tmp.setLeft(newNode);
}
else {
insertNode(tmp.getLeft(), newNode);
}
}
return tmp;
}
// In-Order Tree Traversal
public static void printTree(Interval tmp) {
if (tmp == null) {
return;
}
if (tmp.getLeft() != null) {
printTree(tmp.getLeft());
}
System.out.print(tmp);
if (tmp.getRight() != null) {
printTree(tmp.getRight());
}
}
}
A questo punto aggiungiamo alla classe AugmentedIntervalTree un main in cui configuriamo come test lo scenario utilizzato finora come esempio. Per farlo instanziamo un oggetto AugmentedIntervalTree, inseriamo tutti i nodi e poi stampiamo in output la loro sequenza ordinata. La struttura dell'albero è quella illustrata graficamente in precedenza in figura 2, per la quale la sequenza ordinata di nodi che ci aspettiamo come output sarà:
[1, 12, 12][2, 8, 8][5, 10, 25][8, 16, 20][14, 20, 20][15, 25, 25][18, 21, 21]
Modifichiamo quindi la classe AugmentedIntervalTree aggiungendo il main con il codice dell'esempio:
public class AugmentedIntervalTree {
private Interval root;
public static Interval insertNode(Interval tmp, Interval newNode) {
if (tmp == null) {
tmp = newNode;
return tmp;
}
if (newNode.getEnd() > tmp.getMax()) {
tmp.setMax(newNode.getEnd());
}
if (tmp.compareTo(newNode) <= 0) {
if (tmp.getRight() == null) {
tmp.setRight(newNode);
}
else {
insertNode(tmp.getRight(), newNode);
}
}
else {
if (tmp.getLeft() == null) {
tmp.setLeft(newNode);
}
else {
insertNode(tmp.getLeft(), newNode);
}
}
return tmp;
}
public static void printTree(Interval tmp) {
if (tmp == null) {
return;
}
if (tmp.getLeft() != null) {
printTree(tmp.getLeft());
}
System.out.print(tmp);
if (tmp.getRight() != null) {
printTree(tmp.getRight());
}
}
public static void main(String[] args) {
AugmentedIntervalTree ait = new AugmentedIntervalTree();
ait.root = insertNode(ait.root, new Interval(5, 10));
ait.root = insertNode(ait.root, new Interval(15, 25));
ait.root = insertNode(ait.root, new Interval(1, 12));
ait.root = insertNode(ait.root, new Interval(8, 16));
ait.root = insertNode(ait.root, new Interval(14, 20));
ait.root = insertNode(ait.root, new Interval(18, 21));
ait.root = insertNode(ait.root, new Interval(2, 8));
printTree(ait.root);
}
}
Eseguendo il programma otteniamo il risultato seguente:
[1, 12, 12][2, 8, 8][5, 10, 25][8, 16, 20][14, 20, 20][15, 25, 25][18, 21, 21]
Come possiamo vedere questo risultato coincide con quello che ci aspettavamo.
A questo punto possiamo procedere con l'implementazione della funzionalità per cui siamo ricorsi a questo tipo di struttura, ovvero la verifica della sovrapposizione tra i nostri intervalli di partenza ed una lista di intervalli query. A questo scopo definiamo un nuovo metodo che, per ogni intervallo query, scorre l'albero ed aggiunge gli intervalli con i quali esso si sovrappone ad una lista. Nell'effettuare la ricerca dei nodi all'interno dell'Augmented Interval Tree sfrutteremo l'informazione che abbiamo aggiunto, relativa al valore massimo dell'estremo presente nel sottoalbero di ogni nodo, per rendere più efficiente la ricerca ed escludere i confronti non necessari. Il modo in cui la utilizziamo è il seguente: se il valore massimo del sottoalbero del figlio sinistro di un nodo è minore dell'estremo di partenza dell'intervallo query, allora possiamo escludere i nodi di quell'intero sottoalbero dal confronto e passare direttamente al sottoalbero di destra del nodo.
Modificheremo ora la nostra classe AugmentedIntervalTree, aggiungendo:
- un metodo ricorsivo intersectInterval che prende come parametri due intervalli, che rappresentano il nodo dell'albero che stiamo analizzando ed il nodo query, e una lista di intervalli nella quale vengono aggiunti quelli che intersecano il nodo query
- una lista di intervalli query nel main di test per i quali verifichiamo le sovrapposizioni con il metodo intersectInterval e stampiamo in output i risultati
Ancora una volta utilizziamo gli intervalli dell'esempio visto finora, per cui inseriamo nella lista degli intervalli query da verificare: [8,10] e [20,22]
Come evidenziato graficamente in precedenza in figura 1:
- l'intervallo query [8,10] interseca gli intervalli: [5, 10], [1, 12], [2, 8], [8, 16]
- l'intervallo query [20, 22] interseca gli intervalli: [15, 25, 25], [14, 20, 20], [18, 21, 21]
A valle di queste considerazioni, la nostra classe AugmentedIntervalTree diventa:
public class AugmentedIntervalTree {
private Interval root;
public static Interval insertNode(Interval tmp, Interval newNode) {
if (tmp == null) {
tmp = newNode;
return tmp;
}
if (newNode.getEnd() > tmp.getMax()) {
tmp.setMax(newNode.getEnd());
}
if (tmp.compareTo(newNode) <= 0) {
if (tmp.getRight() == null) {
tmp.setRight(newNode);
}
else {
insertNode(tmp.getRight(), newNode);
}
}
else {
if (tmp.getLeft() == null) {
tmp.setLeft(newNode);
}
else {
insertNode(tmp.getLeft(), newNode);
}
}
return tmp;
}
public static void printTree(Interval tmp) {
if (tmp == null) {
return;
}
if (tmp.getLeft() != null) {
printTree(tmp.getLeft());
}
System.out.print(tmp);
if (tmp.getRight() != null) {
printTree(tmp.getRight());
}
}
public void intersectInterval(Interval tmp, Interval i, List res) {
if (tmp == null) {
return;
}
if (!((tmp.getStart() > i.getEnd()) || (tmp.getEnd() < i.getStart()))) {
if (res == null) {
res = new ArrayList();
}
res.add(tmp);
}
if ((tmp.getLeft() != null) && (tmp.getLeft().getMax() >= i.getStart())) {
this.intersectInterval(tmp.getLeft(), i, res);
}
this.intersectInterval(tmp.getRight(), i, res);
}
public static void main(String[] args) {
AugmentedIntervalTree ait = new AugmentedIntervalTree();
ait.root = insertNode(ait.root, new Interval(5, 10));
ait.root = insertNode(ait.root, new Interval(15, 25));
ait.root = insertNode(ait.root, new Interval(1, 12));
ait.root = insertNode(ait.root, new Interval(8, 16));
ait.root = insertNode(ait.root, new Interval(14, 20));
ait.root = insertNode(ait.root, new Interval(18, 21));
ait.root = insertNode(ait.root, new Interval(2, 8));
printTree(ait.root);
System.out.println("\n");
List queries = new ArrayList<>();
queries.add(new Interval(8, 10));
queries.add(new Interval(20, 22));
List over = new ArrayList<>();
for (Interval i : queries) {
over.clear();
ait.intersectInterval(ait.root, i, over);
System.out.println("Nodi che intersecano [" + i.getStart() + ", " + i.getEnd() + "]:");
for (Interval ris : over) {
System.out.println(ris);
}
}
}
}
Eseguendo il programma otteniamo il risultato seguente, in cui viene prima stampato l'albero in ordine e poi vengono elencati, per ogni intervallo query, gli intervalli che esso interseca:
[1, 12, 12][2, 8, 8][5, 10, 25][8, 16, 20][14, 20, 20][15, 25, 25][18, 21, 21] Nodi che intersecano [8, 10]: [5, 10, 25] [1, 12, 12] [2, 8, 8] [8, 16, 20] Nodi che intersecano [20, 22]: [15, 25, 25] [14, 20, 20] [18, 21, 21]
Come possiamo vedere anche questa volta il risultato è esattamente quello che ci aspettavamo.
Aggiungendo una stampa di debug nel metodo intersectInterval che indica il nodo con cui l'intervallo query viene confrontato, possiamo vedere dove l'algoritmo sfrutta l'informazione del valore massimo del sottoalbero dei nodi con la quale abbiamo aumentato il nostro Interval Tree. Ad esempio per l'intervallo query [20,22] otteniamo il risultato seguente:
Confronto: [5, 10, 25] con [20, 22, 22] Confronto: [15, 25, 25] con [20, 22, 22] Confronto: [8, 16, 20] con [20, 22, 22] Confronto: [14, 20, 20] con [20, 22, 22] Confronto: [18, 21, 21] con [20, 22, 22] Nodi che intersecano [20, 22]: [15, 25, 25] [14, 20, 20] [18, 21, 21]
Riferendoci nuovamente alla struttura dell'albero rappresentata in figura 2, notiamo che dopo aver confrontato l'intervallo query con la root, l'algoritmo va vedere se il valore dell'estremo massimo del figlio sinistro della root stessa (12) è maggiore dell'estremo inferiore dell'intervallo query (20). In questo caso non lo è e questo significa che nel sottoalbero sinistro della root non ci sono nodi relativi ad intervalli che si possono sovrapporre con l'intervallo query, per cui esclude tutto il sottoalbero sinistro dai confronti e passa direttamente ad analizzare i nodi del sottoalbero destro della root.
Il codice completo dell'esempio è scaricabile da qui:
Le strutture ad albero non smettono mai di affascinanti, così come i grafi.
L’approccio utilizzato ricorda molto un albero binario di ricerca.
Piccola nota sull’implementazione: avrei evitato di usare la classe di utilità con metodi statici e mi sarei piuttosto appoggiato su un Builder e utilizzato un Visitor per l’attraversamento della struttura ad albero, ma per i fini dell’articolo può andare bene così penso.
Appena posso approfondirò l’argomento proposto :) Grazie
E’ vero, su alberi e grafi ci sono sempre un sacco di cose interessanti da scoprire ed utili per quando si deve lavorare con grandi moli di dati.
Riguardo l’implementazione, è come dici: ho puntato a renderla più semplice possibile nell’articolo, in modo da mantenere il focus sulla struttura e l’algoritmo proposti, senza aggiungere complicazioni non necessarie.
Grazie a te per il consueto scambio positivo.
Davis