Árvore Binária de Pesquisa (ABP) PDF

Árvore binária de pesquisa (ABP) – elementos comparáveis Nas Árvores Binárias de Pesquisa, os elementos colecionados devem ser, de alguma forma, comparáveis uma vez que os mesmos são dispostos na árvore de acordo com a ordem estabelecida entre eles (menores à esq...

Árvore binária de pesquisa (ABP) – elementos comparáveis Nas Árvores Binárias de Pesquisa, os elementos colecionados devem ser, de alguma forma, comparáveis uma vez que os mesmos são dispostos na árvore de acordo com a ordem estabelecida entre eles (menores à esquerda e maiores à direita) À semelhança do que fizemos nas estruturas lineares, iremos também neste tipo de estruturas, por razões de simplicidade, comparar sempre os seus elementos pela ordem intrínseca dos mesmos (e não usando um objeto comparador), exigindo, para o efeito, que E represente uma classe comparável. Ou seja, impondo o seguinte tipo de restrição: class SearchBinaryTree... Árvores Algoritmos e Estrutura de Dados 24  A classe SearchBinaryTree [1/4] public class SearchBinaryTree extends LinkedBinaryTree{ // Segue-se um conj. de operações herdadas que não devem ser permitidas, pois não // asseguram a organização específica duma ABP. Opta-se por sobrepor o compor- // tamento herdado dessas operações pelo lançamento de uma exceção adequada. public Position addRoot(E e){ throw new UnsupportedOperationException("Operação não permitida numa ABP"); } public Position addLeft(Position p, E e){ throw new UnsupportedOperationException("Operação não permitida numa ABP"); } public Position addRight(Position p, E e){ throw new UnsupportedOperationException("Operação não permitida numa ABP"); } public E set(Position p, E e){ throw new UnsupportedOperationException("Operação não permitida numa ABP"); } // Método auxiliar que compara um elemento 'e' com um nodo 'n'. private int compEN(E e, Node n){ return e.compareTo(n.getElement());} //continua... Árvores Algoritmos e Estrutura de Dados 25  Inserção numa ABP 50 inserção do elemento 10 50 O processo de inserção deve garantir que a organização 20 75 20 75 própria de uma árvore binária de pesquisa se mantenha. 80 80 O algoritmo é simples: 70 10 70 começando no nodo raiz, vai-se seguindo pelo lado esquerdo ou direito, consoante o elemento a 50 50 inserir seja, respetivamente, menor ou maior que o do nodo inserção do elemento 72 corrente; é no momento em que já não há 20 75 20 75 nodo descendente por onde seguir que se acrescenta ao nodo corrente um nodo folha com o novo elemento; 10 70 80 10 70 80 se nessa caminhada descendente for encontrado um elemento igual, então ou nada se faz ou limitamo- nos a atualizar o elemento. 60 72 60 Árvores Algoritmos e Estrutura de Dados 26  Algoritmo de inserção numa ABP Para o processamento das estruturas em forma de árvore, opta-se normalmente por algoritmos recursivos como vimos, as próprias ABP, sendo árvores binárias, são facilmente definidas na forma recursiva e é por essa razão que os algoritmos definidos pela via recursiva resultam incomparavelmente mais simples e compactos Se a árvore for nula, a inserção de um elemento ‘e’ limitar-se-á a criar o nodo raiz com esse elemento. Caso não seja nula, a árvore pode ser vista como uma subárvore iniciada num nodo n=root e o algoritmo de inserção passa a poder ser descrito, de forma recursiva, pelos seguintes passos: //note que raiz é o nodo raiz da subárvore, e não necessariamente da árvore global 1. SE e = elem do nodo raiz n ENTÃO atualizar elemento 2. SENÃO 3. SE e < elem do nodo raiz n ENTÃO 4. SE raiz n não tiver filho esq ENTÃO 5. acrescentar filho esq com o elemento ‘e’ 6. SENÃO mandar inserir ‘e’ na subárvore esq 7. SENÃO 8. SE raiz n não tiver filho dir ENTÃO 9. acrescentar filho dir com o elemento ‘e’ 10. SENÃO mandar inserir ‘e’ na subárvore dir Árvores Algoritmos e Estrutura de Dados 27  A classe SearchBinaryTree [2/4] (inserção de elemento) public class SearchBinaryTree extends LinkedBinaryTree{ // código anterior... public E put(E e){ //devolve o elemento substituído, caso já exista um igual if(isEmpty()) { super.addRoot(e); return null; } else return put(root,e); //invoca o método recursivo } //Método auxiliar recursivo que insere o elemento 'e' na subárvore iniciada em 'n' private E put(Node n, E e){ E res=null; if(compEN(e,n)==0){ //substitui o elemento res=n.getElement(); n.setElement(e); }else if(compEN(e,n) elem do nodo raiz n ENTÃO 7. mandar remover o elemento na subárvore direita 8. SENÃO //elem. iguais: o elemento a remover é o que está no nodo n 9. SE raiz n tem menos de dois filhos ENTÃO 10. remover raiz n pelo método remove() herdado 11. SENÃO 12. substituir raiz n pelo nodo com menor elemento da subárvore dir substituir raiz n pelo nodo com o menor elemento da subárvore direita O nodo de substituição terá também ele que ser retirado da sua posição original mas isso não será difícil, pois no máximo ele só terá a subárvore direita (bastará, por isso, usar o método remove() herdado). Árvores Algoritmos e Estrutura de Dados 31 A classe SearchBinaryTree [3/4] (remoção de elemento) public class SearchBinaryTree extends LinkedBinaryTree{ // código anterior... private Node minNode(Node n) { //Devolve o nodo com o menor dos elementos if (n.getLeft()==null) return n; //da subárvore iniciada no nodo 'n'. else return minNode(n.getLeft()); } private E remove(Node n, E e){ //Método auxiliar recursivo que remove o if(n==null) return null; //elemento 'e' da subárvore iniciada em 'n'. else if(compEN(e,n)0) return remove(n.getRight(),e); else //'n' é o nodo a remover if(numChildren(n)