Gli alberi R e la suddivisione in Minimum Bounding Rectangles

Struttura dati che suddivide l’albero R in rettangoli

Gli R-Tree (Rectangle), o alberi R in italiano, rappresentano una generalizzazione dell’MB+ Tree. Gli alberi R sono degli alberi B ma vengono utilizzati per l’organizzazione dei dati multidimensionali come dati spaziali, coordinate geografiche, ecc.

La struttura dati di un albero R divide lo spazio in un MBR (Minimum Bounding Rectangles), in ogni rettangolo ogni nodo dell’albero R ha numero variabile di entry (fino ad un certo numero prefissato). Ogni dato (entry), che non sia un nodo foglia, contiene due entità: la prima identifica il nodo figlio, la seconda rappresenta l’MBR che contiene tutte le entry del nodo figlio.
Ogni nodo non foglia contiene un puntatore che punta ad un nodo di un livello più basso ed un rettangolo che copre tutti i rettangoli associati ai discendenti del nodo. Infine, nei nodi foglia viene memorizzata la lista dei vettori che ricadono dentro al singolo rettangolo di livello inferiore.

Dall’esempio si può notare che le due chiavi della struttura datistruttura dati contenute nella radice dell’albero (R1 e R2) rappresentano i due rettangoli più grandi e si intersecano tra loro perchè appartengono allo stesso nodo. Ogni altro nodo andrà a formare un nuovo rettangolo per ogni chiave al suo interno che a sua volta conterrà un rettangolo per ogni figlio.

Gli alberi R e la suddivisione in Minimum Bounding Rectangles

Negli alberi R gli elementi simili hanno posizioni vicini grazie alle operazioni di inserimento e cancellazione, ad esempio l’inserimento di un nuovo elemento verrà inserito nel nodo foglia che richiede il minor numero di estensioni delle dimensioni dell’MBR.

Gli alberi R e la suddivisione in Minimum Bounding Rectangles

Photo Credit: Wiki Commons

Pubblicato in Sistemi Informativi Taggato con: , , , ,

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *

*