sábado, 14 de junho de 2014

Usando grafos em Java - Parte 3

Agora veremos como implementar em Java as duas pesquisas. A seguir mostramos as duas classes que serão implementadas:




Vimos no post anterior a teoria por trás destas duas pesquisas. Vamos ver no vídeo agora como implementá-las.

Implementando árvore binária - parte 3

Vamos acrescentar a nossa classe algumas outras funções úteis. Como vimos no primeiro vídeo (de teoria) existem 3 formas mais comuns de caminhamento na árvore binária. Vamos implementá-las neste vídeo. Na verdade, já realizamos um caminhamento LNR.

Vamos buscar também o menor e o maior valor armazenado na árvore. Veremos que isto pode ser obtido por uma pesquisa simples.

Para isto vamos alterar nossa classe Arvore para que ela tenha os seguintes métodos:
Veja no vídeo como as alterações são feitas.

Implementando árvore binária - parte 2

Neste post terminaremos nossa classe de árvore binária.O diagrama de classe que teremos está indicado abaixo:

Vemos que na classe de Arvore somente precisamos armazenar a raiz da árvore. As demais ligações são obtidas a partir dos atributos Esq e Dir em No. No vídeo veremos como implementar

  • pesquisar(): que verificar se existe na árvore um nó com um determinado valor, retornando o nó se este existir ou nulo se não existir
  • balancear(): como nosso procedimento de inserção não insere os valores de forma balanceada, temos que criar um procedimento que faz o balanceamento da árvore (reduz a altura da árvore ao mínimo)
  • toString(): gera a árvore como uma string para que possamos apresentar o conteúdo dela
  • altura(): que retorna a altura da árvore.



Se vocês analizarem o método de balanceamento, irão ver que existe um problema. O que acontece se existem elementos repetidos na árvore?

domingo, 8 de junho de 2014

Implementando árvore binária - parte 1

Neste post iremos mostrar como implementar em Java uma árvore binária. Utilizaremos Generics assim é possível tornar a nossa árvore capaz de suportar qualquer classe de dados. Se você quiser ver um pouco da teoria de árvore, dê uma olhada em Usando árvores binárias em Java.


sábado, 7 de junho de 2014

Usando árvores binárias em Java

Você vai me peguntar: por que é que eu preciso conhecer como implementar uma árvore binária em Java? Afinal a API do Java já possui duas classes bastante úteis que são TreeSet e TreeMap. As operações em TreeSet são O( log(n) ) - o que é muito bom.

A resposta é por que a árvore binária é uma estrutura clássica e a menos que você queira ser somente um daqueles usuários que não sabe o que está fazendo e como programador você não pode se dar ao luxo de ser somente um usuário. No vídeo a seguir veremos uma introdução às árvores binárias.