Árvore Rtree

Prévia do material em texto

R-TREE
Equipe 10:
Pedro Iunes
Gabriel Bandeira
Jonathan Magalhães
Conteúdo
• História
• Conceito
• Características
• Minimum Bounding Rectangle (MBR)
• Aplicação
• Estrutura de dados
• Inserção
• Split
• Remoção
História
• Foi proposta em 1984.
• Pelo engenheiro de software Antonin Guttman.
• A ideia era criar uma árvore multiway para o acesso no
espaço com o fim de indexar informação
multidimensional.
• Este tipo de árvore ficou conhecida como Árvore R, pelo
fato de ela usar Retângulos de Limite Mínimo
(MBR – Minimum Bounding Rectangle) para delimitar
uma área no espaço.
• Seu Funcionamento básico consiste em definir
Retângulos, chamados de MBRs que contenham as
informações inseridas na Árvore.
História
Antonin Guttman
Conceito
• É uma estrutura de dados hierárquica derivada das
árvores B
• A diferença está na natureza das chaves:
• Valores numéricos ou alfanuméricos simples, no caso
de árvore B.
• Usa-se métodos de acesso no espaço com o fim de
indexar informação multidimensional, por exemplo, as
coordenadas (X,Y) de uma posição geográfica, no
caso das árvores R.
• São árvores de dados estruturados que são usadas para
Métodos de Acesso Espacial, ou seja, para indexar
informação multidimensional (como coordenadas
geográficas, retângulos e polígonos)
Conceito
• Organiza objetos próximos em MBR.
• Nas folhas o MBR envolve um grupo de objetos
• Nos níveis superiores, o MBR envolve os MBRs que
formam seus filhos.
• A árvore R não serve para organizar exatamente o
contorno ou a forma gráfica do objeto, e sim o seu
retângulo envolvente mínimo (MBR).
• Este retângulo é formado a partir da observação dos
limites geométricos mínimo e máximo expresso pelas
coordenadas dos seus pontos inferior esquerdo e
superior direito.
• A complexidade O é dada por 𝑙𝑜𝑔𝑀 𝑛. Onde m é o
número máximo de filhos em cada nó.
Características
• Árvore R de ordem (m,M).
• Número máximo de entradas por nó: M
• Número mínimo de entradas por nó: 𝑚 ≤
𝑀
2
• Altura máxima da árvore: ℎ𝑚𝑎𝑥 = log𝑚 𝑁 − 1
• N : número de objetos inseridos.
• O número mínimo de entradas permitido na raiz é 2, a menos 
que a raiz seja uma folha. Nesse caso, ela pode conter apenas 
uma ou nenhuma entrada.
• Todas as folhas estão no mesmo nível.
Minimum Bounding Rectangle (MBR)
Aplicação
• Sistemas de Informações Geográficas (GIS). 
• Sistemas CAD.
• Arquiteturas VLSI.
• Sistemas P2P, Bioinformática, Data Streams.
Estrutura de dados
• #define M 5 //Grau máximo da árvore
• const int m = M/2 //Grau mínimo da árvore
• typedef struct matriz { //Estrutura das chaves
• int **Mat; //Uma matriz n-dimensional
• char localizador; //Serve para a localização mais rápida da matriz
• } matriz;
• typedef struct no {
• int num_chaves; //Quantidade de chaves armazenadas
• matriz chaves[M-1] ; //Chaves armazenadas
• struct no *filhos[M]; //Filhos
• bool folha; //FALSE se o nó for interno
• } no;
Inserção
• Para cada nó, se o objeto a ser inserido está contido em um
dos filhos, basta tentar inseri-lo nesse nó.
• Caso não esteja contido em um dos filhos é preciso realizar um
método.
• O método utilizado pela R-tree original consiste em escolher o nó
cujo MBR será menos expandido para acomodar o novo dado.
• Em caso de empate, será escolhida a sub-árvore representada
pela MBR de menor área.
• Ao chegar no nó-folha, o objeto é inserido no próprio nó.
• Caso exceda o número de ocupação de cada nó, será preciso
dividir o nó que excede o número de elementos permitidos.
Inserção
• Para cada objeto ou nó desse grupo excedido, calcula-se o
acréscimo no MBR se adicionado a R1 ou R2 e o atribui ao nó
cuja inserção desse elemento representa o menor acréscimo
de área para o MBR.
• Caso excedido o número de filhos do pai nesse nó, será
aplicado os mesmos algoritmos a esse pai, até chegar a raiz
(se necessário), podendo levar a criação de uma nova raiz.
Split
• Distribui as M entradas de um nó mais a nova entrada em
dois nós.
• Reduzir a área de cobertura.
• Seleção dos primeiros objetos de cada grupo: seeds. Na 
árvore R, dois objetos são promovidos ao nó índice.
• Distribuição dos objetos restantes.
Inserção e Split
Inserção e Split
Inserção e Split
Inserção e Split
Inserção e Split
Inserção e Split
Inserção e Split
Remoção
• Parecido com a B-tree.
• Eliminar uma entrada de uma página pode precisar atualizar 
os retângulos do nó pai.
• No entanto, quando uma página é underfull, As chaves não 
vão ser redistribuídas com os seus vizinhos. Em vez disso, a 
página será dissolvido e todos os seus filhos (que pode ser 
sub-árvores, não apenas objetos folha) será reinserido.
Referências
• http://pt.wikipedia.org/wiki/%C3%81rvores_R
• http://prezi.com/dvntxp6ragfb/arvore-r/
• http://wiki.icmc.usp.br/images/c/cb/SCC578920131-Rtree.pdf
• http://en.wikipedia.org/wiki/R-tree
• http://www-db.deis.unibo.it/courses/SI-LS/papers/Gut84.pdf
• http://www.dpi.inpe.br/livros/bdados/cap6.pdf
• http://www.inf.ufg.br/mestrado/sites/www.inf.ufg.br.mestrado/
files/uploads/Dissertacoes/Thiago%20Borges.pdf
• Site para testar a árvore R:
• http://gis.umb.no/gis/applets/rtree2/jdk1.1/
Dúvidas?