View
0
Download
0
Category
Preview:
Citation preview
Árvore B
Uma Árvore B de ordem m é uma árvore, tal que:Cada nó contém no máximo m � 1 valores;Os valores dentro de cada nó estão ordenados;Todos os valores na subárvore esquerda de um valor sãomenores que ele e todos os valores na subárvore direita de umvalor são maiores que ele.Todo os nós, exceto a raiz, contém no mínimo (m � 1)/2valores;Cada nó que não seja uma folha tem n + 1 filhos, onde n é onúmeros de valores no nó.Ela é perfeitamente balanceada, ou seja, todas as subárvoresvazias estão no mesmo nível.
Karina Mochetti Aula 15. Árvore B
Árvore B: Página
Um nó de uma árvore B é chamado de página.Página Raiz: não contém número mínimo de nós.Página Interna: devem conter (m � 1)/2 n < m nós e n + 1filhos.Página Folha: devem conter (m � 1)/2 n < m nós enenhum filho (devem estar todas no mesmo nível).
Karina Mochetti Aula 15. Árvore B
Árvore B: Exemplo
Karina Mochetti Aula 15. Árvore B
Árvore B: Exemplo
Karina Mochetti Aula 15. Árvore B
Árvore B: Exemplo
Karina Mochetti Aula 15. Árvore B
Árvore B: Exemplo
Karina Mochetti Aula 15. Árvore B
Árvore B: Exemplo
Karina Mochetti Aula 15. Árvore B
Árvore B: Exemplo
Karina Mochetti Aula 15. Árvore B
Árvore B: Exemplo
Karina Mochetti Aula 15. Árvore B
Árvore B: Exemplo
Karina Mochetti Aula 15. Árvore B
Árvore B
Cada página possui um vetor de valores e um vetor de ponteiros.
#define ORDEM 1000
typedef struct pagina {int n;int k[ORDEM-1];struct pagina *filho[ORDEM];
} Pagina;
typedef Pagina* ArvoreB;
Karina Mochetti Aula 15. Árvore B
Busca
A busca será mais complexa dentro de uma página. Como cadapágina está ordenada podemos usar busca binária dentro de cadapágina para definir o valor ou o filho da árvore que deve ser seguido.
Karina Mochetti Aula 15. Árvore B
Busca
A busca será mais complexa dentro de uma página. Como cadapágina está ordenada podemos usar busca binária dentro de cadapágina para definir o valor ou o filho da árvore que deve ser seguido.
Karina Mochetti Aula 15. Árvore B
Busca
A busca será mais complexa dentro de uma página. Como cadapágina está ordenada podemos usar busca binária dentro de cadapágina para definir o valor ou o filho da árvore que deve ser seguido.
Karina Mochetti Aula 15. Árvore B
Busca
A busca será mais complexa dentro de uma página. Como cadapágina está ordenada podemos usar busca binária dentro de cadapágina para definir o valor ou o filho da árvore que deve ser seguido.
Karina Mochetti Aula 15. Árvore B
Busca
A busca será mais complexa dentro de uma página. Como cadapágina está ordenada podemos usar busca binária dentro de cadapágina para definir o valor ou o filho da árvore que deve ser seguido.
Karina Mochetti Aula 15. Árvore B
Busca
A busca será mais complexa dentro de uma página. Como cadapágina está ordenada podemos usar busca binária dentro de cadapágina para definir o valor ou o filho da árvore que deve ser seguido.
Karina Mochetti Aula 15. Árvore B
Busca
A busca será mais complexa dentro de uma página. Como cadapágina está ordenada podemos usar busca binária dentro de cadapágina para definir o valor ou o filho da árvore que deve ser seguido.
Karina Mochetti Aula 15. Árvore B
Busca
A busca será mais complexa dentro de uma página. Como cadapágina está ordenada podemos usar busca binária dentro de cadapágina para definir o valor ou o filho da árvore que deve ser seguido.
Karina Mochetti Aula 15. Árvore B
Busca
A busca será mais complexa dentro de uma página. Como cadapágina está ordenada podemos usar busca binária dentro de cadapágina para definir o valor ou o filho da árvore que deve ser seguido.
Karina Mochetti Aula 15. Árvore B
Busca
A busca será mais complexa dentro de uma página. Como cadapágina está ordenada podemos usar busca binária dentro de cadapágina para definir o valor ou o filho da árvore que deve ser seguido.
Karina Mochetti Aula 15. Árvore B
Busca
A busca será mais complexa dentro de uma página. Como cadapágina está ordenada podemos usar busca binária dentro de cadapágina para definir o valor ou o filho da árvore que deve ser seguido.
Karina Mochetti Aula 15. Árvore B
Busca Binária
int binSearch(int* v, int min, int max, int x) {
if (max == min) return min;
int meio = (max-min)/2;
if (v[meio] == x) return meio;
if (v[meio] < x) return binSearch(v, meio+1, max, x);
if (v[meio] > x) return binSearch(v, min, meio-1, x);
}
Complexidade
O(logm), no pior caso o vetor tem m � 1 elementos
Karina Mochetti Aula 15. Árvore B
Busca Binária
int binSearch(int* v, int min, int max, int x) {
if (max == min) return min;
int meio = (max-min)/2;
if (v[meio] == x) return meio;
if (v[meio] < x) return binSearch(v, meio+1, max, x);
if (v[meio] > x) return binSearch(v, min, meio-1, x);
}
ComplexidadeO(logm), no pior caso o vetor tem m � 1 elementos
Karina Mochetti Aula 15. Árvore B
Busca
Pagina *search(Pagina *T, int x, int *i) {
if (T == NULL) {
return NULL;
*i = -1;
}
else {
int p = binSearch(T->k, 0, T->n, x);
if (x == T->k[p]) {
return T;
*i = p;
}
if (x < T->k[p]) return search(T->filho[p], x, i);
if (x > T->k[p]) return search(T->filho[p+1], x, i);
}
}
Complexidade
O(h · logm) o que resulta em O(log n)
Karina Mochetti Aula 15. Árvore B
Busca
Pagina *search(Pagina *T, int x, int *i) {
if (T == NULL) {
return NULL;
*i = -1;
}
else {
int p = binSearch(T->k, 0, T->n, x);
if (x == T->k[p]) {
return T;
*i = p;
}
if (x < T->k[p]) return search(T->filho[p], x, i);
if (x > T->k[p]) return search(T->filho[p+1], x, i);
}
}
ComplexidadeO(h · logm) o que resulta em O(log n)
Karina Mochetti Aula 15. Árvore B
Inserção
Para acharmos o lugar correto para inserir um nó, devemos realizaruma busca na Árvore, até acharmos a folha correspondente, aoachar a folha, teremos 2 casos.
Caso 1: o valor cabe na página.Caso 2: o valor não cabe na página.
Karina Mochetti Aula 15. Árvore B
Inserção: Caso 1
O valor é inserido na página de forma ordenada e o número devalores é atualizado.
Karina Mochetti Aula 15. Árvore B
Inserção: Caso 1
O valor é inserido na página de forma ordenada e o número devalores é atualizado.
Karina Mochetti Aula 15. Árvore B
Inserção: Caso 2
É achada a mediana (valor que está no meio do vetor) entretodos os valores da pagina e o valor a ser inserido.Todos os valores menores que a mediana formaram uma novapagina.Todos os valores maiores que a mediana formaram uma novapagina.A mediana é inserida na página pai, com os valores menores defilho esquerdo e os maiores de filho direto.
Karina Mochetti Aula 15. Árvore B
Inserção: Caso 2
Karina Mochetti Aula 15. Árvore B
Inserção
Deve ser encontrada a folha na qual o valor será inserido.A inserção em uma folha cheia irá percorre a árvore até a raizou até que seja encontrada uma página com espaço.A complexidade do algoritmo será O(log n).Não existem rotações nem fator de balanceamento, mas énecessário manter o vetor de cada página ordenado.A separação de uma página em duas é chamada de quebra dapágina (ou split em inglês).
Karina Mochetti Aula 15. Árvore B
Inserção: Exemplo
Crie a Árvore B de ordem 5 com as seguintes inserções: 25, 5, 1,24, 4, 9, 42, 14, 16, 12
Karina Mochetti Aula 15. Árvore B
Inserção: Exemplo
Crie a Árvore B de ordem 5 com as seguintes inserções: 25, 5, 1,24, 4, 9, 42, 14, 16, 12
Karina Mochetti Aula 15. Árvore B
Inserção: Exemplo
Crie a Árvore B de ordem 5 com as seguintes inserções: 25, 5, 1,24, 4, 9, 42, 14, 16, 12
Karina Mochetti Aula 15. Árvore B
Inserção: Exemplo
Crie a Árvore B de ordem 5 com as seguintes inserções: 25, 5, 1,24, 4, 9, 42, 14, 16, 12
Karina Mochetti Aula 15. Árvore B
Inserção: Exemplo
Crie a Árvore B de ordem 5 com as seguintes inserções: 25, 5, 1,24, 4, 9, 42, 14, 16, 12
Karina Mochetti Aula 15. Árvore B
Inserção: Exemplo
Crie a Árvore B de ordem 5 com as seguintes inserções: 25, 5, 1,24, 4, 9, 42, 14, 16, 12
Karina Mochetti Aula 15. Árvore B
Inserção: Exemplo
Crie a Árvore B de ordem 5 com as seguintes inserções: 25, 5, 1,24, 4, 9, 42, 14, 16, 12
Karina Mochetti Aula 15. Árvore B
Inserção: Exemplo
Crie a Árvore B de ordem 5 com as seguintes inserções: 25, 5, 1,24, 4, 9, 42, 14, 16, 12
Karina Mochetti Aula 15. Árvore B
Inserção: Exemplo
Crie a Árvore B de ordem 5 com as seguintes inserções: 25, 5, 1,24, 4, 9, 42, 14, 16, 12
Karina Mochetti Aula 15. Árvore B
Inserção: Exemplo
Crie a Árvore B de ordem 5 com as seguintes inserções: 25, 5, 1,24, 4, 9, 42, 14, 16, 12
Karina Mochetti Aula 15. Árvore B
Inserção: Exemplo
Crie a Árvore B de ordem 5 com as seguintes inserções: 25, 5, 1,24, 4, 9, 42, 14, 16, 12
Karina Mochetti Aula 15. Árvore B
Árvore B
Uma árvore B de ordem 3 é essencialmente uma árvore 2-3.Árvores B são usadas em banco de dados (ORACLE, SQL) eem sistemas de arquivos (NTFS, HFS).Uma página contém somente as chaves de cada registro enormalmente está na memória secundária. Ao ser acessada étrazida para a memória principal.
Apesar das operações de busca e inserção (e remoção) teremcomplexidade O(log n), o acesso a disco é menor, pois há umacesso por página somente e o número de páginas numa árvoreB é muito menor que o número de nós de uma árvore AVL.
Karina Mochetti Aula 15. Árvore B
Árvore B
Uma árvore B de ordem 3 é essencialmente uma árvore 2-3.Árvores B são usadas em banco de dados (ORACLE, SQL) eem sistemas de arquivos (NTFS, HFS).Uma página contém somente as chaves de cada registro enormalmente está na memória secundária. Ao ser acessada étrazida para a memória principal.Apesar das operações de busca e inserção (e remoção) teremcomplexidade O(log n), o acesso a disco é menor, pois há umacesso por página somente e o número de páginas numa árvoreB é muito menor que o número de nós de uma árvore AVL.
Karina Mochetti Aula 15. Árvore B
Árvore B
Simulador Onlinehttps://www.cs.usfca.edu/~galles/visualization/BTree.html
Karina Mochetti Aula 15. Árvore B
Exercício
Diga quantas comparações são necessárias para encontrarmos onúmero 72 na árvore abaixo.
Karina Mochetti Aula 15. Árvore B
Recommended