Árvore Binária e Árvore AVL PDF

Preview

Summary

Download Árvore Binária e Árvore AVL PDF

Description

Árvore Binária e Árvore AVL 1. Árvore Uma árvore pode ser classificada pelo número máximo de filhos de seus nós, podendo ser, por exemplo, N-ária, com no máximo n filhos para cada nó, ternária, com no máximo três filhos, e binária, com no máximo dois filhos. As estruturas de árvores possuem diversas finalidades na modelagem e processamento de dados. As árvores são organizadas e trabalhadas por uma estrutura hierárquica, permitindo a aplicação de diversos algoritmos facilitados, principalmente, por estratégias recursivas. Estruturas de árvore, por exemplo, permitem otimizar buscas em banco de dados, e também, representar diferentes dados. A representação de uma árvore pode ocorrer de várias formas: ● Por uma forma hierárquica; ● Por conceitos da teoria dos conjuntos; ● Pelo diagrama de barras etc. 2. Árvore Binária e Árvore Binária de Busca Uma árvore binária é uma estrutura de dados, em que cada nó possui nenhum, um ou, no máximo, dois filhos. Uma árvore é formada por um conjunto de nós, e se esse conjunto tiver zero elemento, é considerada uma árvore vazia. Para qualquer outro número de elementos, teremos sempre um elemento especial chamado de raiz. Pode existir uma árvore binária sem nenhum nó; se existir pelo menos um nó, teremos uma raiz. Cada nó, em uma árvore binária, pode possuir uma subárvore da esquerda e uma subárvore da direita, conforme ilustra a figura abaixo, em que os nós em verde representam a subárvore da esquerda, os vermelhos a subárvore da direita, e em relação ao nó, a cor azul.

Destacamos, ainda, que o nó principal de uma árvore é chamado de nó raiz; já o nó que não possui filho, é chamado de nó folha; e os demais nós não possuem nomenclatura

especial, podendo ser relacionados aos nomes similares à uma árvore genealógica. Na figura a seguir, por exemplo, o nó A é raiz, e os nós D, E, F e G são folhas. Além disso, podemos ter os seguintes relacionamentos, em que o nó: ● ● ● ● ● ●

B é irmão de C; A é pai dos nós B e C; B é tio dos nós F e G; F é primo dos nós D e E; A é ancestral de todos os outros; D e E são descentes de B.

2.1 Cálculo do Nível de um Árvore Uma árvore pode possuir muitos níveis, sendo a sua altura igual ao valor do maior nível. Representamos os níveis pelo nó raiz, que possui nível zero, sendo os posteriores, obtidos com o acréscimo de um nível, conforme nos mostra a figura abaixo, que possui 3 níveis, sendo o primeiro do nó raiz (nível 0). Por meio dos níveis, podemos calcular a altura de uma árvore, que é sempre igual ao seu maior nível. Logo, na árvore da seguinte figura, a altura é 2. vejamos:

2.2 Classificações das Árvores Uma árvore pode ser classificada como: ● Estritamente Binária: Cada nó tem exatamente zero ou dois filhos. ● Binária Completa: Todos os níveis possuem exatamente dois nós, exceto o penúltimo e último níveis. ● Binária Cheia: Todos os níveis possuem dois nós, exceto o último (nós folhas).

Importante: Toda árvore cheia é completa e estritamente binária, mas nem toda árvore completa é cheia e estritamente binária, e nem toda árvore estritamente binária é cheia e completa.

2.3 Fórmulas para Calcular o Número de Nós nas Árvores Binárias Para calcular o número de nós de uma árvore binária, utilizamos algumas fórmulas importantes: ● Número de nós máximo em um nível n: 2n ● Número mínimo de nós até um nível n: n+1 ● Número de nós até um nível n: 2n+1 -1 Exemplo: Considerando uma árvore com altura 2, calcule: A. O número máximo de nós no nível 2. B. O número mínimo de nós dessa árvore.

C. O número máximo de nós dessa árvore. O primeiro ponto a considerar, para resolver essa questão, é que a altura é igual ao maior nível. Logo, se a árvore possui altura 2, então seu nível máximo é 2. Vamos agora resolver as questões aplicando as fórmulas: A. Número máximo de nós no nível 2. Utilizando a fórmula, podemos calcular o número máximo de nós no nível 2, que é: 2² = 4 (Figura abaixo).

B. O número mínimo de nós dessa árvore. O número mínimo de nós ocorre quando todos os nós são inseridos em uma mesmo direção, se assemelhando à estrutura de uma lista. Utilizando a fórmula, verificamos que o número mínimo de nós, até o nível 2, é: 2+1 =3 (Figura abaixo).

C. O número máximo de nós dessa árvore.

O número máximo de nós leva em consideração que a árvore é cheia. Utilizando a fórmula, verificamos que o número máximo de nós, até o nível 2, é: 22+1 -1 = 8 -1 = 7 (Figura abaixo).

2.4 Árvore Binária de Busca Uma árvore binária de busca é uma árvore binária, em que todos os nós da subárvore da esquerda são menores, e todos os nós da subárvore da direita são maiores que o nó raiz. Esse tipo de estrutura é muito utilizado para aplicações de buscas, a fim de melhorar o desempenho, como a procura por índices etc. A figura seguinte ilustra um exemplo de uma árvore binária de busca.

2.5 Percursos Um percurso serve para caminhar pelos nós de uma árvore, trabalhando com seus valores. Os percursos clássicos em uma árvore binária de busca são os percursos em pré-ordem, pós-ordem ou ordem simétrica (em ordem). Esses algoritmos podem ser implementados facilmente de maneira recursiva. Na descrição dos percursos a seguir, utilizaremos a árvore da figura seguinte como exemplo.

Vejamos, detalhadamente, cada percurso: Percurso em pré-ordem: Esse percurso visita os elementos da árvore, aplicando os seguintes passos: 1. Visita raiz; 2. Percorre a subárvore da esquerda (em pré-ordem); 3. Percorre a subárvore da direita (em pré-ordem). Na árvore da figura anterior, o resultado da aplicação do percurso pré- ordem seria: 7-3-1-5-8-9. Percurso em pós-ordem: Esse percurso visita os elementos da árvore, aplicando os seguintes passos: 1. Percorre a subárvore da esquerda (em pós-ordem); 2. Percorre a subárvore da direita (em pós-ordem); 3. Visita raiz. Na árvore da figura anterior, o resultado da aplicação do percurso pós- ordem seria: 1-5-3-9-8-7. Percurso em ordem simétrica (em ordem): Esse percurso visita os elementos da árvore, aplicando os seguintes passos: 1. Percorre a subárvore da esquerda (em ordem simétrica); 2. Visita raiz; 3. Percorre a subárvore da direita (em ordem simétrica).

Na árvore da figura anterior, o resultado da aplicação do percurso em ordem seria: 1-3-5-7-8-9. Os percursos em árvores estudados anteriormente são muito importantes, pois permitem que todos os nós de uma árvore sejam visitados. 3. AVL Uma árvore AVL é uma ABB (árvore binária de busca) balanceada, ou seja, a diferença entre seus níveis das subárvores é, no máximo, 1. Dessa forma, a cada nó inserido, é verificada a necessidade de balanceamento, por meio de operações de rotação. Com a finalidade de garantir o balanceamento em árvore AVL, são feitas rotações, conforme nos mostra a figura abaixo.

A grande vantagem desse tipo de árvore é a menor complexidade de busca. Comparando essa estrutura com a busca sequencial em uma lista sequencial, podemos verificar um ganho em relação à complexidade no pior caso. Isso ocorre porque na lista sequencial, é preciso comparar cada elemento, fazendo com que a complexidade no pior caso seja O(n). Na estrutura da árvore AVL em cada iteração (nível comparado), eliminamos metade dos valores, obtendo a complexidade O (log2 n), o que nem sempre ocorre em uma árvore binária, em que todos os elementos podem ser inseridos em uma mesma direção, não ocorrendo, portanto, o balanceamento. Exemplo: inserção de números ordenados. A grande vantagem da utilização de uma árvore balanceada é o seu desempenho nas buscas, em que são realizadas menos comparações. Na árvore da figura abaixo, por exemplo, se quisermos realizar uma busca pelo número 1, sempre vamos para à esquerda, eliminando, em cada nível, metade dos valores restantes....