MÓDULO 5 - ÁRVORES

Prévia do material em texto

<p>Uma das mais importantes classes de estruturas de dados em computação são as árvores. Aproveitando-se de sua organização hierárquica, muitas aplicações são realizadas usando-se algoritmos relativamente simples, recursivos e de eficiência bastante razoável. Definições e representações básicas Uma árvore é uma estrutura de dados que se caracteriza por uma relação de hierarquia entre os elementos que a compõem. Exemplos de estruturas em forma de árvores são: organograma de uma empresa; A divisão de um livro em capítulos, seções, tópicos, etc; A árvore genealógica de uma pessoa. De um modo um pouco mais formal, podemos dizer que uma árvore é um conjunto finito de um ou mais nodos (nós ou vértices), tais que: 1. existe um nodo denominado raiz; 2. os demais nodos formam = 0 conjuntos disjuntos s1, s2, , sm, tais que cada um desses conjuntos também é uma árvore (denominada sub-árvore). Uma floresta é um conjunto de árvores. Se V é um nodo de A, a notação Av indica a subárvore de V com raiz A. Para visualizar esse conceito, pode-se representa-lo graficamente. Há formas diferentes de representações gráficas de uma árvore. Em todas elas, cada nodo poderá ser associado a um identificador, denominado rótulo. a) Representação hierárquica b) Representação por conjuntos (diagrama de inclusão) c) Representação por expressão parentetizada (parênteses aninhados) Cada conjunto de parênteses correspondentes contém um nodo e seus filhos. Se um nodo não tem filhos, ele é seguido por um par de parênteses sem conteúdo. A ( ( D ( ) E ( ) ) ) F ( ) ) ) ) d) Representação por expressão não parentetizada Cada nó é seguido por um número que indica a quantidade de filhos desse nodo, e em seguida por esses filhos, representados do mesmo modo. A 2 Pode-se representar uma árvore de muitos outros modos, mas é interessante notar que, dentre os exemplos apresentados, a representação a) é a que permite uma melhor visualização, e que será utilizada a partir deste ponto. As representações c) e d) não permitem boa visualização da estrutura, mas podem ser úteis para guardar em arquivos os dados de uma árvore. Como, por definição, os subconjuntos s1, são disjuntos, cada nó só pode ter um pai. Assim, o desenho abaixo, por exemplo, não representa uma árvore: Definições Dada uma árvore qualquer: 1) A linha que liga dois nodos da árvore denomina-se aresta. 2) Diz-se que existe caminho entre dois nodos V e W da árvore, se a partir do nodo V puder-se ao nodo W percorrendo-se as arestas que ligam os nodos</p><p>intermediários entre V e W. Observa-se que existe sempre um caminho entre a raiz e qualquer nodo da árvore. 3) Se houver um caminho entre V e W, começando em V diz-se que V é um nodo ancestral de W e W é um nodo descendente de V. Se este caminho contiver uma única aresta, diz-se que V é o nodo pai de W e que W é um nodo filho de V. Dois nodos que são nodos filhos do mesmo nodo pai são denominados nodos irmãos. Uma característica inerente a árvores é que qualquer nodo, exceto a raiz, tem um único nodo pai. 4) Se um nodo não possui nodos descendentes, ele é chamado de folha ou nodo terminal da árvore. 5) Grau de um nodo é o número de nodos filhos do mesmo. Obviamente que um nodo folha tem grau zero. 6) Nível de um nodo é o número de nodos existentes no caminho entre a raiz e o próprio nodo. A raiz tem nível 1. 7) O grau da árvore é igual ao grau do nodo de maior grau da árvore. 8) O nível da árvore é igual ao nível do nodo de maior nível da árvore. ÁRVORES BINÁRIAS Definição da Estrutura de Dados Uma árvore binária contém dois filhos: filho direito e filho esquerdo. typedef struct tree_node tree_node, *tree; struct tree_node { tipo data; tree left; tree right; } typedef enum { PREORDER, INORDER, POSTORDER } ORDER; Definições auxiliares # define DATA(T) ((T)->data) # define LEFT(T) # define RIGHT(T) ((T)->right) Operações 1) Alocar um nó e inicializar o campo de dados int allocate_tree_node (tree *p_T, tipo data) { tree T; T = (tree)malloc (sizeof(tree_node)) ; if (T==NULL)</p><p>return ERRO; *p_T = T; DATA(T) = data; LEFT(T) = NULL: = NULL; return OK; } 2) Liberar o espaço alocado para o nó void free_tree_node(tree *p_T) { free(*p_T); *p_T=NULL: } 3) Inicializar uma árvore vazia int init_tree (tree *p_T) { *p_T=NULL; return OK; } 4) Verificar se a árvore está vazia int T) { return (T==NULL) ? TRUE : FALSE; } 5) Alocar um nó na árvore com data sendo a raiz e atribuir uma árvore à direita e outra à esquerda int make_root(tree *p_T, tipo data, tree right, tree left) if (empty_tree(*p_T) == FALSE) return ERRO; if ERRO) return ERRO; LEFT(*p_T) = left; = return OK; }</p><p>6) Destruir uma árvore void destroy_tree(tree *p_T, void (*p_func_f)()) { if (empty_tree(*p_T) == FALSE) { if (p_func_f != NULL) (*p_func_f) (DATA(*p_T); } } Atravessamento em Árvores Binárias Atravessar uma árvore significa percorrer todos os seus nós. Tradicionalmente, existem 3 atravessamentos possíveis de uma árvore: infixa ou em-ordem prefixa ou pré-ordem posfixa ou pós-ordem Atravessamento Em-Ordem No atravessamento infixa, vamos tratar a sub-árvore esquerda, depois a raiz e finalmente a sub-árvore direita. Atravessamento Pré-Ordem No atravessamento prefixa, vamos tratar a raiz, depois a sub-árvore esquerda e finalmente a sub-árvore direita. Atravessamento Pós-Ordem No atravessamento posfixa, vamos tratar a sub-árvore esquerda, depois a sub-árvore direita e finalmente a raiz. ÁRVORES BINÁRIAS BALANCEADAS - AVL Uma árvore binária balanceada, chamada de árvore AVL, é uma árvore binária na qual as alturas das duas subárvores de cada um dos nós nunca diferem em mais de 1. balanceamento de um nó é igual a diferença entre as suas altura esquerda e direita. Portanto, cada nó de uma árvore balanceada tem balanceamento igual a -1, 0 ou 1, dependendo da comparação entre as alturas esquerda e direita. Lembrando que a altura de um nó n da árvore é o número de nós do maior caminho de n até um de seus descendentes. As folhas tem altura 1. Uma árvore binária completa com n>0 nós tem altura mínima, que é igual a 1 + floor(log (n)). A Figura mostra uma árvore binária balanceada. Os valores dentro do nó são altura do nó e seu balanceamento.</p><p>5,-1 3,1 2,0 1,0 2,0 3,-1 1,0 1,0 1,0 1,0 1,0 1,0 1,0 Caso a probabilidade de pesquisar uma chave em uma tabela seja a mesma para todas as chaves, uma árvore binária balanceada terá a busca mais eficiente. Infelizmente o método de inserção em árvores binárias não garante que a árvore permanecerá balanceada. Como já vimos a estrutura da árvore depende da ordem em que as chaves são inseridas na árvore. Exercício 1: (POSCOMP2005) Árvores binárias podem ser usadas para guardar e recupérar informações com número de operações proporcional a altura da árvore. Quais das seguintes figuras representam árvores binárias de altura balanceada ou do tipo AVL - Adelson, Velski e Landis:</p><p>(I) (II) (III) (IV) A) Somente a (I) e a (IV) são AVL B) Somente a (I) é AVL C) Somente a (I) e (II) e (III) são AVL D) Somente a (II) e a (III) são AVL E) Todas são AVL Exercício 2:</p><p>O resultado da impressão da árvore apresentada, utilizando a ordem de atravessamento infixa, será? eu e estrutura dados adoro de A) eu adoro estrutura de dados e arquivo B) eu adoro estrutura de arquivo e dados C) eu arquivo adoro estrutura e de dados D) dados arquivo eu adoro estrutura de e E) arquivo eu e estrutura adoro dados de Exercício 3:</p><p>Apresentada a arvore abaixo, qual forma de atravessamento resultará na expressão a + b*c: A A) infixa B) prefixa C) posfixa D) alterfixa E) recursiva Exercício 4:</p><p>Dada a árvore abaixo, qual é a representação em parentesis da mesma: b) A C B D E F H I K J L A) B) C) D) E) Exercício 5:</p><p>b) A C B D E F H I K J L Baseado na árvore acima, indica a alterantiva falsa A) Se o atravessamento utilizado for infixo, o primeiro elemento apresentado será a letra A B) Se o atravessamento utilizado for préfixo, o primeiro elemento apresentado será a letra H C) Se o atravessamento utilizado for posfixo, o primeiro elemento apresentado será a letra H D) Se o atravessamento utilizado for prefixo, o ultimo elemento apresentado será a letra G E) Se o atravessamento utilizado for prefixo, o ultimo elemento apresentado será a letra L</p>