As Estruturas de Dados e Algoritmos em Java

Aula 4

Árvores Binárias

Referências Bibliográficas

LARORE, Robert. Estruturas de dados e Algoritmos em Java. Rio de Janeiro: Moderna, 2004. Cap VIII.

Arquivos

ClasseVetor_1.java

ClasseVetor_1Main.java

Resumo

• Em vetores, a pesquisa em um vetor binário é rápida, porém a inserção em um vetor ordenado é muito lenta;
• Inserções e eliminações em uma lista encadeada são as mais rápidas a serem executadas, basta alterar algumas referências. Porém, localizar um elemento específico na lista é difícil;
• Árvores fornecem ambas as características (pesquisa de um vetor e inserção/eliminação de uma lista encadeada), tornando-se uma das estruturas de dados mais interessantes.
• Arvore consiste em nós conectados por arestas;
• As linhas (arestas) entre os nós representam o modo como os nós são relacionados.
• Caminho: pense em alguém caminhando de nó em nó nas arestas que os conectam. A seqüência resultante de nós é chamada de caminho.
• Raiz: o nó da parte superior da árvore é chamado de raiz. Há apenas uma raiz em uma árvore. Para uma coleção de nós e arestas serem definidos como uma árvore, tem que haver um (e apenas um) caminho da raiz até qualquer outro nó.
• Pai: qualquer nó (exceto a raiz) tem exatamente uma aresta que sobe para outro nó. O nó acima dele é chamado de pai do nó.
• Filho: qualquer nó pode ter uma ou mais linhas descendo para outros nós. Eses nós de um dado nó são chamados de seus filhos.
• Folha: um nó que não tem filhos é chamado nó folha. Pode haver apenas uma raiz em uma árvore, mas pode haver muitas folhas.
• Subárvore: qualquer nó pode ser considerado como sendo a raiz de uma subárvore, que consiste em seus filhos, nos filhos de seus filhos, etc. Se você pensar em termos de famílias, a subárvore de um nó contém todos os seus descendentes.
• Visitando: um nó é visitado quando o controle do programa chega ao nó, em geral para executar alguma operação (comparar valores, etc.). Passar simplesmente sobre o nó Nodo caminho de um nó para outro não é considerado como visitar o nó.
• Percorrendo: percorrer uma árvore significa visitar todos os nós em alguma ordem especificada. Por exemplo, visitar todos os nós em ordem ascendente do valor-chave.
• Chaves: vimos que um campo de dados em um objeto é geralmente designado a um valor-chave. Esse valor é usado para buscar o item ou executar outras operações nele. Nos diagramas de árvores, quando um círculo representa um nó que mantém um item de dados, o valor-chave do item é geralmente mostrado Nodo círculo.
• Níveis: o nível de um determinado nó refere-se a quantas gerações o nó está da raiz, ou seja, 1 mais a profundidade do seu pai.
• Árvores binárias: se todo nó em um árvore puder ter Nodo máximo dois filhos, a árvore será chamada de árvore binária (árvore binária de busca).
• Os dois filhos de cada nó em uma árvore são chamados de filho à direita e filho à esquerda;
• Em uma árvore binária de busca, o filho à esquerda de um nó tem que ter uma chave menor que seu pai e o filho à direita de um nó tem que ter uma chave maior ou igual ao seu pai.
• Uma analogia – estrutura hierárquica de arquivos em um sistema de computador.

Classes para implementação de uma árvore não balanceada

Árvores não balanceadas são aquelas que possuem a maioria de seus nós em um lado da raiz.

Classe No: primeiro, precisamos de uma classe que represente a estrutura dos nós. Esses objetos contêm os dados que representam os objetos sendo armazenados e também referências para cada um dos dois filhos de um nó.

package arvore; public class Nodo {         int codigo;                        //dado         String nome;                //dado         int idade;                        //dado         Nodo filhoEsq;        //filho à esquerda deste nó         Nodo filhoDir;        //filho à direita deste nó                  public void mostraNo(){                 {                         System.out.println("{"+codigo+", "+nome+                                         ", "+idade+"} ");                  }         } }

Classe Arvore: precisamos de uma classe a partir da qual instanciamos a árvore dita: o objeto que mantém todos os nós. Ela tem apenas um campo: uma variável Nodo que mantém a raiz, a partir da qual acessamos os demais nós. Possui também os métodos contendo as ações que podemos executar usando uma árvore.

...