Baixe o app para aproveitar ainda mais
Prévia do material em texto
1 1 Árvores B Prof. Cláudio Campelo, PhD Departamento de Sistemas & Computação / UFCG Estrutura de Dados e Algoritmos Introdução 2 � Rudolf Bayer, Binary B-Trees for Virtual Memory, ACM-SIGFIDET Workshop 1971, San Diego, California, Session 5B, p. 219-235 � Motivação � Custo alto de acesso a memória secundária � A leitura de uma página (nó) é cara em I/O � Solução � Aumentou o número de chaves em cada nó (página) 2 Ideia 3 Árvore B 4 � Características � Ela é uma árvore balanceada � Todas as folhas estão no último nível � Possui um número máximo de filhos que cada nó pode ter (ordem) � Nó de uma árvore B são chamados de páginas (guardam mais de 1 elemento) 3 Árvore B 5 � Propriedades (árvore B de ordem m) � Cada nó tem no máximo m filhos � Cada nó interno (diferente de raiz e de folha) tem no mínimo m/2 filhos � A raiz tem pelo menos 2 filhos se não for folha. � Todas as folhas estão no mesmo nível e não têm filhos � Um nó interno com k filhos possui k-1 elementos. � Os elementos de cada nó estão ordenados e servem como separadores dos filhos. Árvore B 6 � Propriedades (árvore B de ordem m) � Cada nó tem no máximo m filhos � Cada nó interno (diferente de raiz e de folha) tem no mínimo m/2 filhos � A raiz tem pelo menos 2 filhos se nao for folha. � Todas as folhas estão no mesmo nível e nao tem filhos � Um nó interno com k filhos possui k-1 elementos. � Os elementos de cada nó estão ordenados e servem como separadores dos filhos. 4 Exemplo (ordem 3) 7 Nó com mais de uma chave, ordenada balanceada 5 10 3 4 6 8 11 13 14 12 17 15 raiz Estrutura de um nó 8 public class BNode<T extends Comparable<T>> { } } 5 Estrutura de um nó 9 public class BNode<T extends Comparable<T>> { LinkedList<T> elements; LinkedList<BNode<T>> children; BNode<T> parent; int maxKeys; int maxChildren; public BNode(int order){ this.maxChildren = order; this.maxKeys = order - 1; this.elements = new LinkedList<T>(); this.children = new LinkedList<BNode<T>>(); } } Estrutura de um nó 10 public class BNode<T extends Comparable<T>> { public boolean equals(Object obj) { boolean resp = false; return resp; } 6 Estrutura de um nó 11 public class BNode<T extends Comparable<T>> { public boolean equals(Object obj) { boolean resp = false; if(obj != null){ if(obj instanceof BNode){ if(this.size() == ((BNode<T>)obj).size()){ resp = true; int i = 0; while(i<this.size() && resp){ resp = resp && this.getElementAt(i). equals(((BNode<T>) obj).getElementAt(i)); i++; } } } } return resp; } Interface da árvore B 12 public interface BTree<T extends Comparable<T>> { BNode<T> getRoot(); boolean isEmpty(); int height(); BNodePosition<T> search(T element); void insert(T element); BNode<T> maximum(BNode<T> node); BNode<T> minimum(BNode<T> node); void remove(T element); int size(); } 7 Interface da árvore B 13 public interface BTree<T extends Comparable<T>> { BNode<T> getRoot(); boolean isEmpty(); int height(); BNodePosition<T> search(T element); void insert(T element); BNode<T> maximum(BNode<T> node); BNode<T> minimum(BNode<T> node); void remove(T element); int size(); } O retorno é o nó contendo o elemento e a posição do elemento nele (BNode, Position) Pesquisa 14 public class BNodePosition<T extends Comparable<T>> { BNode<T> node; int position; public BNodePosition(BNode<T> node, int position) { this.node = node; this.position = position; } public BNodePosition() { } } 8 Pesquisa 15 � A ideia é similar à pesquisa em BST � Diferença � Um nó pode ter mais de uma chave � Dentro do nó fazemos uma pesquisa linear � Procura se o elemento está no nó � Se não estiver, então procura na sub-árvore cujos separadores são x1 e x2 tal que x1 < valor procurado < x2. � Pode acontecer variações: � valor procurado < x1: valor procurado é menor que o menor elemento � x2 < valor procurado: valor procurado é maior que maior elemento procurado � O retorno é o nó contendo o elemento e a posição do elemento nele (BNode, Position) Pesquisa (exemplo) 16 � Pesquisa do nó 8 5 10 3 4 6 8 11 13 14 12 17 15 raiz 9 Pesquisa (exemplo) 17 � Pesquise pelas chaves 14, 7, 17 5 10 3 4 6 8 11 13 14 12 17 15 Pesquisa 18 B-TREE-SEARCH(BNode x, K k) i ← 1 while i ≤ x.size and k > x.keys[i] i ← i + 1 if i ≤ x.size and k = x.keys[i] return (x, i) if x.leaf return (null,null) return B-TREE-SEARCH(x.children[i], k) 10 Inserções 19 � Acontecem sempre nas folhas � Algoritmo localiza a folha conveniente para fazer a inserção � Se o nó folha não está cheio então o elemento será inserido nele em ordem � Se o nó folha está cheio � Faça o split (divisão) do nó. Um elemento vai subir. � Faça o promote (promoção) do elemento a subir na árvore � Se o pai estiver cheio faz o split e promote no pai Inserções 20 � Split � Escolha o elemento médio (mediana de separação) dos elementos do nó (já considerando o novo elemento inserido) � Valores menores que a mediana são colocados em um novo nó folha (esquerdo) e valores maiores são colocados em um outro novo nó folha (direito) � A mediana é inserida como novo elemento do pai (isso pode causar um split no pai) � Filhos da mediana contêm os demais elementos do antigo nó; � Um split na raiz origina uma nova raiz. 11 Inserções (exemplo | m=3) 21 Inserções (exemplo | m=4) 22 12 Inserções (exemplo | m=4) 23 Remoções 24 � É análoga à inserção, porém com alguns complicadores, visto que uma chave pode ser removida de qualquer nó. � Assim como na inserção, precisamos garantir que, ao removermos a chave as propriedades da árvore- B não sejam violadas. � Duas operações podem ser necessárias: � Concatenação; � Redistribuição. 13 Remoções 25 � Pontos a se considerar: � O elemento removido em um nó interno pode ser separador de seus nós filhos. � Deletar um elemento pode deixar o nó com número de elementos e filhos menor que o mínimo exigido. � 2 Casos: � O elemento pertence a uma folha; � O elemento pertence a um nó interno; Remoções (Nó Interno) 26 � Chave x não está em uma folha: � x é substituída por y: � a menor chave em uma folha tal que y é maior que x (sucessor); ou � a maior chave em uma folha tal que y é menor que x (predecessor); Portanto, é suficiente fazer análise da remoção em uma folha! (mais adiante veremos ilustrações de remoções de nós internos) 14 Remoções (Elemento em uma folha) 27 � Remove o elemento do nó folha. � Se acontece underflow, verifique os irmãos e transfira uma chave ou então faça a fusão do nó com um irmão. � Se a deleção acontece no filho da direita transfira o valor máximo do filho da esquerda para o pai se não acontecer underflow no filho da esquerda (depois desça a penúltima chave do pai para o filho). � O caso simétrico é análogo (com filho à esquerda); � Se não for possível usar elementos de algum irmão então faça junção de irmãos usando valores do pai Remoções (Elemento em uma folha) 28 � Não acontece underflow (ordem 5) >>>>> Buscando 50 >>>> 50 removido!>>>>> Buscando 50 >>>> 15 Remoções (Elemento em uma folha) 29 � Acontece underflow >>>>>>>>> Redistribuição >>>>>>>>> >>>>> Buscando 29 >>>> 29 removido! Remoções (Elemento em uma folha) 30 � Acontece underflow Concatenação >>>>>> Redistribuição >>>>>> >>>>>>>>>>>> Buscando 22 >>>>>>>>>>>> 22 removido! >>>>>>> Buscando 47 >>>>>> 47 removido! 16 Remoções (Elemento em umafolha) 31 � Acontece underflow Concatenação >>>>>>>>> Buscando 74 >>>>>>>>> 74 removido! Remoções (Elemento em um nó interno) 32 � Escolhe um novo separador (sucessor/predecessor – em uma folha) � Ajusta o nó que teve o elemento removido, como visto anteriormente. >>>> Substituído pelo sucessor (20) >>>> >>> Removendo o 15 >>> 17 Remoções (Elemento em um nó interno) 33 � Escolhe um novo separador (sucessor/predecessor – em uma folha) � Ajusta o nó que teve o elemento removido, como visto anteriormente. >>>> Concatenando >>>> >>> Concatenando >>> Referências 34 � Capítulo 19 � 1a edição
Compartilhar