Arvores - Algoritmos e Estrutura de Dados PDF

Árvores Árvores n-árias, árvores binárias, árvores de decisão, árvores binárias de pesquisa, AVLs, Heaps, travessias, … Algoritmos e Estrutura de Dados 1  Estruturas em árvore As estruturas em forma de árvore (invertida) são utilizadas na...

Árvores Árvores n-árias, árvores binárias, árvores de decisão, árvores binárias de pesquisa, AVLs, Heaps, travessias, … Algoritmos e Estrutura de Dados 1  Estruturas em árvore As estruturas em forma de árvore (invertida) são utilizadas na representação hierárquica de informação tais como, classificação dos seres vivos, árvores root genológicas, árvores de decisão, diagramas A organizacionais, etc. internal Trata-se de um conjunto de nodos, interligados B C D entre si segundo uma relação hierárquica (de pais external e filhos em que cada filho só pode ter um pai) E F G H I Existe um nodo raíz (topo da hierarquia), do qual descendem outros nodos intermédios , que terão J K L também eles descendentes, e assim sucessivamente, até se chegar aos nodos terminais – aqueles que não têm descendentes (folhas da árvore ou também conhecidos como nodos externos). Árvores Algoritmos e Estrutura de Dados 2  Implementação de árvores Na implementação das estruturas em forma de Iterable árvore vamos usar uma combinação de classes abstratas e concretas, visando uma maior reutilização do código, à semelhança do que é Tree BinaryTree feito na JCF. Para uma melhor compreensão do caminho que vai ser seguido, segue-se um digrama com a hierarquia dos tipos AbstractTree AbstractBinaryTree de árvore a criar. LinkedBinaryTree AbstractMap E=Entry SearchBinaryTree TreeMap Árvores Algoritmos e Estrutura de Dados 3  Abstraindo a entidade nodo - Position Na definição da interface da ADT Árvore (Tree) usaremos uma abstração da entidade nodo, que designaremos por Position e que consistirá numa interface com um único método: E getElement() A classe Node será depois definida como privada dentro da estrutura de dados concreta que vier a implementar a ADT Tree, implementando a interface Position A interface Position do nodo funciona como que uma máscara, que esconde quase a totalidade das funcionalidades do nodo, deixando apenas visível para o exterior o método consultor getElement(); dessa forma, consegue-se garantir que quem use a Tree apenas possa consultar o elemento guardado no nodo, ficando desse modo assegurados os princípios de abstração e encapsulamento; Com a abstração Position consegue-se assim uma forma de referenciar os nodos ao nível da interface da própria árvore, portanto ainda antes deles serem definidos foi essencialmente visando esse objetivo que se optou por abstrair a entidade nodo, através da interface Position. Árvores Algoritmos e Estrutura de Dados 4  A Interface Tree public interface Tree extends Iterable { Position root(); //devolve a posição do nodo raiz Position parent(Position p); //devolve a posição do nodo ascendente de p Iterable children(Position p); //returns an iterable collection //of the positions representing p's children int numChildren(Position p); //devolve nº de nodos descendentes de p boolean isInternal(Position p); //verifica se p é nodo interno (não folha) boolean isExternal(Position p); //verifica se p é nodo externo (folha) boolean isRoot(Position p); //verifica se a posição p é nodo raiz int size(); //devolve nº total de nodos boolean isEmpty(); //verifica se não existem nodos Iterable positions();//devolve uma coleção iterável contendo todas as posições }} public interface Position { E getElement( ); } Árvores Algoritmos e Estrutura de Dados 5  Iteração duma árvore Fazer com que um iterador transite entre dois nodos de uma árvore pode ser algo bastante complexo, dado que é necessário garantir que se visitem todos os nodos, sem se passar duas vezes pelo mesmo mesmo que a transição seja de um nodo para um dos seus descendentes, é necessário decidir qual escolher; e a transição complica-se ainda mais sempre que se chegue a um nodo folha. Uma forma de simplificar o processo passa por copiar para uma coleção linear o conteúdo da árvore, e depois pôr o iterador a percorrer essa coleção Pois bem, esse é funcionamento típico dos iteradores de captura instantânea (snapshot iterators), como vimos já anteriormente – ver diagrama no diapositivo seguinte; É o próprio iterador que guarda dentro de si a tal coleção linear que mantém uma cópia dos nodos da árvore; Em vez de se duplicarem os elementos colecionados (coleção por cópia), tipicamente a coleção linear mantém apenas as referências dos elementos originais (col. por ref.) Sempre que há uma alteração na árvore (put(), remove(), …) a coleção linear deixa de refletir o conteúdo original, podendo, por isso, o iterador ficar inutilizado. Para a conversão da árvore numa sequência linear de nodos teremos que percorrer toda a árvore optaremos por uma travessia do tipo PREORDER, uma das três travessias que estudaremos mais à frente é sempre mais simples fazer toda a travessia da árvore de forma seguida do que através transições individuais Árvores separados no tempo. Algoritmos e Estrutura de Dados 6  Iterador a usar numa estrutura em árvore Snapshot iterator Coleção iterável cursor Árvores Algoritmos e Estrutura de Dados 7  A classe abstrata AbstractTree [1/2] public abstract class AbstractTree implements Tree { public boolean isInternal(Position p) { return numChildren(p) > 0; } public boolean isExternal(Position p) { return numChildren(p) == 0; } public boolean isRoot(Position p) { return p == root( ); } public boolean isEmpty( ) { return size( ) == 0; } private void subtreePositions (Position p, List list) { list.add(p); // for preorder, we add position p before exploring subtrees for (Position c : children(p)) subtreePositions(c, list); } public Iterable positions( ) { List list = new ArrayList( ); if (!isEmpty( )) subtreePositions(root( ), list); // fill the list recursively return list; } // continua... Árvores Algoritmos e Estrutura de Dados 8  A classe abstrata AbstractTree [2/2] public abstract class AbstractTree implements Tree { // código anterior... public Iterator iterator( ) { return new ElementIterator( ); } //---------------- nested ElementIterator class ---------------- private class ElementIterator implements Iterator { Iterable snapshot = positions(); Iterator posIterator = snapshot.iterator( ); public boolean hasNext( ) { return posIterator.hasNext( ); } public E next( ) { return posIterator.next( ).getElement( );}//return element } }} Árvores Algoritmos e Estrutura de Dados 9  Árvore binária A forma de árvore mais popular é a binária, pela sua simplicidade, facilidade de implementação, mas também por um conjunto importante de caraterísticas que apresenta de grande utilidade prática. Cada nodo só pode possuir até dois descendentes. Os dois descendentes formam um par ‘ordenado’ um é conhecido pelo nodo esquerdo e outro pelo nodo direito É este tipo de árvore que iremos estudar com mais detalhe. A melhor forma de definirmos as estruturas em árvore é pela via recursiva. Assim, uma árvore Binária pode ser vista como sendo um nodo raiz root e duas subárvores que iniciam nos dois nodos descendentes. A B C left subtree right subtree Árvores Algoritmos e Estrutura de Dados 10  Ligação dos nodos numa árvore binária root elem left right elem elem left right left right elem elem elem elem left right elem elem elem elem elem elem Árvores Algoritmos e Estrutura de Dados 11  Representação mais rigorosa das ligações numa árvore binária root elem left right elem elem left right left right elem elem elem elem left right elem elem elem elem elem elem Árvores Algoritmos e Estrutura de Dados 12  A Interface BinaryTree public interface BinaryTree extends Tree { Position left(Position p);//devolve a posição do nodo esquerdo de p Position right(Position p);//devolve a posição do nodo direito de p Position sibling(Position p);//devolve a posição do nodo irmão de p } Árvores Algoritmos e Estrutura de Dados 13  A classe abstrata AbstractBinaryTree public abstract class AbstractBinaryTree extends AbstractTree implements BinaryTree{ public Position sibling(Position p) { Position parent = parent(p); if (parent == null) return null; // p must be the root if (p == left(parent)) // p is a left child return right(parent); // (right child might be null) else // p is a right child return left(parent); // (left child might be null) } public int numChildren(Position p) { int count=0; if (left(p) != null) count++; if (right(p) != null) count++; return count; } public Iterable children(Position p) { List list = new ArrayList(2); // max capacity of 2 if (left(p) != null) list.add(left(p)); if (right(p) != null) list.add(right(p)); return list; } } Árvores Algoritmos e Estrutura de Dados 14 A classe LinkedBinaryTree [1/5] public class LinkedBinaryTree extends AbstractBinaryTree { //---------------- nested Node class ---------------- protected static class Node implements Position{ // tipo de nodo a usar private E element; // an element stored at this node private Node parent; // a reference to the parent node (if any) private Node left; // a reference to the left child (if any) private Node right; // a reference to the right child (if any) public Node(E e, Node above, Node leftChild, Node rightChild) { element = e; parent = above; left = leftChild; right = rightChild; } // accessor methods public E getElement( ) { return element; } public Node getParent( ) { return parent; } public Node getLeft( ) { return left; } public Node getRight( ) { return right; } // update methods public void setElement(E e) { element = e; } public void setParent(Node parentNode) { parent = parentNode; } public void setLeft(Node leftChild) { left = leftChild; } public void setRight(Node rightChild) { right = rightChild; } } //----------- end of nested Node class ----------- Algoritmos e Estrutura de Dados 15 // continuamos dentro da classe LinkedBinaryTree...  A classe LinkedBinaryTree [2/5] public class LinkedBinaryTree extends AbstractBinaryTree { // código anterior... protected Node root = null; // root of the tree private int size = 0; // number of nodes in the tree protected Node node(Position p){ if (!(p instanceof Node)) throw new IllegalArgumentException("Tipo de posição inválido!"); return (Node) p; // safe cast } // accessor methods (not already implemented in AbstractBinaryTree) public int size( ) { return size; } public Position root( ) { return root; }//implicit up cast (from Node to Position) public Position parent(Position p) {return node(p).getParent( ); } public Position left(Position p) {return node(p).getLeft( );} public Position right(Position p) {return node(p).getRight( );} //continua... 16 Árvores Algoritmos e Estrutura de Dados  A classe LinkedBinaryTree [3/5] public class LinkedBinaryTree extends AbstractBinaryTree { // código anterior... // update methods supported by this class public Position addRoot(E e){ if (!isEmpty( )) return null; root = new Node(e, null, null, null); size = 1; return root; } public Position addLeft(Position p, E e){ Node n = node(p); if (n.getLeft( ) != null) return null; Node child = new Node(e, n, null, null); n.setLeft(child); size++; return child; } //continua... 17 Árvores Algoritmos e Estrutura de Dados  A classe LinkedBinaryTree [4/5] public class LinkedBinaryTree extends AbstractBinaryTree { // código anterior... public Position addRight(Position p, E e){ Node n = node(p); if (n.getRight( ) != null) return null; Node child = new Node(e, n, null, null); n.setRight(child); size++; return child; } public E set(Position p, E e){ Node n = node(p); E temp = n.getElement( ); n.setElement(e); return temp; } //continua... Árvores Algoritmos e Estrutura de Dados 18  A classe LinkedBinaryTree [5/5] public class LinkedBinaryTree extends AbstractBinaryTree { // código anterior... public E remove(Position p) { if (numChildren(p) == 2) return null;//não se remove o nodo se tiver 2 filhos Node n = node(p); Node parent = n.getParent( ); Node child = (n.getLeft( ) != null ? n.getLeft( ) : n.getRight( ) ); if (child != null) child.setParent(parent); // child’s grandparent // becomes its parent if (n == root) root = child; // child becomes root else if (n == parent.getLeft( )) parent.setLeft(child); else parent.setRight(child); size--; E temp = n.getElement( ); n.setElement(null); // help garbage collection n.setLeft(null); //para perder a ligação à árvore n.setRight(null); //para perder a ligação à árvore n.setParent(null); //para perder a ligação à árvore return temp; } } //----------- end of LinkedBinaryTree class ----------- 19 Árvores Algoritmos e Estrutura de Dados  Árvores de Decisão Decidir o que fazer numa tarde de Domingo Uma utilização importante das árvores é como instrumento de apoio na tomada de decisões. tenho o estudo a tais estruturas dá-se o nome de árvores de decisão. em dia? Estas árvores permitem chegar a uma decisão entre um conjunto diverso de decisões não sim possíveis, como resultado das respostas dadas a uma série de questões. Tratando-se de questões do tipo sim/não (condições), estaremos na presença de uma fico em vai estar a árvore binária. casa chover? Cada nodo interno representa uma dada condição; não sim Partindo-se da raiz, vai-se sucessivamente escolhendo o filho esquerdo ou direito de cada nodo intermédio de acordo com o valor da respetiva condição, “sim” ou “não”; tenho fico em Com a avaliação de cada condição, deslocamo-nos de um nodo pai para um nodo filho, perfazendo- visitas? casa se assim um caminho na árvore desde a raiz até a uma das suas folhas; A árvore chama-se de decisão, porque cada folha representa a decisão a tomar quando as não sim condições associadas a todos os seus nodos ascendentes assumem um conjunto específico valores. vai estar fico em Mas uma árvore de decisão pode também ser vista como um modelo de decisões e as casa frio? suas possíveis consequências As condições associadas aos nodos podem ser vistas como as decisões a tomar, e o conteúdo das não sim folhas algum tipo de consequência que resulte dessas decisões. vou ao A Árvore de Decisão é uma estrutura muito usada em Inteligência Artificial passeio cinema Representa um dos algoritmos mais importantes da Machine Learning (Aprendizagem Automática) Quando considerada nesse contexto, a árvore cresce de forma automática, com base num conjunto de dados que lhe é fornecido Árvores Algoritmos e Estrutura de Dados 20  Árvore binária de pesquisa (ABP) Uma estrutura de dados que permite suportar de forma muito eficiente toda a informação de coleções de grandes dimensões é a Árvore Binária de Pesquisa Se a árvore estiver devidamente equilibrada (balanceada), é fácil demonstrar que, qualquer que seja o elemento, é possível chegar até ele ao fim de k iterações (k nodos consultados), sendo k o nº de níveis da árvore. Como n=2k-1 é o tamanho da coleção, o algoritmo de pesquisa é de ordem de complexidade logarítmica – O(log n) –, uma vez que k=log2(n+1) Por exemplo, só precisamos, no máximo, de k=20 iterações para encontrarmos um qualquer elemento de uma coleção com mais de um milhão de elementos (1.048.575) A organização típica dos nodos numa árvore binária de pesquisa tem por base a seguinte regra: O elemento de um qualquer nodo é sempre maior do que qualquer elemento que pertença à subárvore esquerda e menor que qualquer elemento que pertença à subárvore direita. Uma árvore binária de pesquisa é parecida a uma árvore de decisão em que a questão colocada em cada um dos nodos internos é se o elemento procurado é menor ou maior (ou igual) que o elemento guardado nesse nodo, e com as folhas a comportarem-se como nodos “normais” – não representado decisões, portanto. Árvores Algoritmos e Estrutura de Dados 21  Árvore binária de pesquisa (ABP) – exemplo root 50 left right 20 100 left right left right 5 35 80 105 left right 28 70 85 25 30 84 Árvores Algoritmos e Estrutura de Dados 22  A ABP SearchBinaryTree Iterable Tree BinaryTree AbstractTree AbstractBinaryTree LinkedBinaryTree SearchBinaryTree Árvores Algoritmos e Estrutura de Dados 23