Estrutura de Dados Parte 4 - Árvore

Árvores

Árvores são estruturas hierárquicas que permitem fazer associações entre elementos chamados de nós. Esses elementos podem ser pais ou/ou filhos, isso significa que, diferente das listas, os nós não estão dispostos de maneira linear e sim acima ou abaixo uns dos outros. Sempre que um nó possuir filhos teremos uma sub-árvore.

Para entender melhor essa estrutura precisamos primeiro conhecer algumas partes de uma árvore:

Nó raiz: é o primeiro nó da estrutura, é a partir dele que os outros nós irão existir.

Nós filhos: são nós que pertencem ao nó raiz ou a qualquer outro nó.

Grau: o grau de um nó é determinado pela quantidade de filhos que ele possui.

Nível: o nó raiz é considerado o nível zero, a partir dele, cada geração é considerada mais um nível.

Nós folhas: são nós que não possuem filhos.

Profundidade: é o maior nível de uma árvore.

Para serem consideradas árvores essas estruturas podem ter apenas um nó raiz e

os nós podem ter apenas um nó pai.

As árvores podem ser usadas para representar diversas situações:

1. Estrutura de pastas
2. Árvore genealógica
3. Organograma de uma empresa

 

Os tipos de árvores são:

1. Árvores binárias
2. Árvores B
3. Árvores 2-3

Existem outros tipos de árvores mais complexas que não iremos tratar aqui.

Árvores Binárias

São árvores onde os nós obrigatoriamente possuem 0, 1 ou 2 filhos. Os filhos são posicionados sempre na esquerda ou na direita de acordo com o critério de grandeza adotado.

Árvore B

São árvores que possuem uma ordem de grandeza M que define a quantidade de elementos chave que um nó irá possuir.
O nó raiz deverá possuir no mínimo 2 elementos chaves.
Cada nó deverá possuir no máximo M-1 e no mínimo M/2 elementos chave.

Por exemplo, uma árvore B com ordem de grandeza M=5, teria em seu nó raiz no mínimo dois elementos.Cada um desses elementos teria em seu nó filho no máximo 4 e no mínimo 2 elementos, cada elemento possuiria por sua vez um nó filho que seguiria o mesmo raciocínio.

Árvores 2-3

São árvores que permitem mais de um elemento (chave) em um único nó. Nessa estrutura,
se o nó possuir uma única chave, poderá possuir de 0 a 2 nós filhos. Agora se o nó possuir duas chaves, poderá ter de 0 a 3 nós filhos.
Podemos dizer que árvores 2-3 são árvores B com ordem de grandeza M=4

public class Arvore{
 
 public static void main(String[] args) {
  No raiz = new No("Raiz");
  
  No no1 = new No("No 1");
  No no11 = new No("No 1.1");
  No no12 = new No("No 1.2");
  
  no1.add(no11, 1);
  no1.add(no12, 2);
  
  No no2 = new No("No 2");
  No no21 = new No("No 2.1");
  no2.add(no21, 1);
  
  
  No no3 = new No("No 3");
  No no31 = new No("No 3.1");
  No no32 = new No("No 3.2");
  No no33 = new No("No 3.3");
  
  No no331 = new No("No 3.3.1");
  
  no33.add(no331, 1);
  
  no3.add(no31, 1);
  no3.add(no32, 2);
  no3.add(no33, 3);
  
  raiz.add(no1, 1);
  raiz.add(no2, 2);
  raiz.add(no3, 3);
  
  raiz.imprimir();
  
  
  System.out.println("--------");
  
  raiz.remover(2);
  raiz.imprimir();
  
  System.out.println("--------");
  
  no3.imprimir();
 }

}

public class No {

 private No[] filhos = new No[10];
 private String descricao;

 public No(String descricao) {
  this.descricao = descricao;
 }

 public void add(No no, int posicao) {
  filhos[posicao] = no;
 }

 public No[] getFilhos() {
  return filhos;
 }

 public String getDescricao() {
  return descricao;
 }

 public void imprimir() {
  imprimir(0);
 }

 public void remover(int i) {
  filhos[i] = null;
 }


 private void imprimir(int i) {
  System.out.println(tab(i)+descricao);
  i++;
  for (No no : filhos) {
   if (no != null) {
    no.imprimir(i);
   }
  }
  
 }

 private String tab(int i) {
  String retorno = "";
  for (int j = 0; j < i; j++) {
   retorno +="  ";
  }
  return retorno;
 }

}

Estrutura de Dados Parte 3 - Lista

Quem diria, não levou 8 anos mas sim 8 dias para continuar a série =D.

A definição de Lista é muito simples: elas mantêm a ordem de inserção e permitem a repetição dos elementos. As operações básicas são:

ADD(x): operação para adicionar um elemento no final da lista.
ADD(i,x): operação para adicionar um elemento em uma posição específica.
GET(i): operação para recuperar um elemento em uma posição específica.
REMOVE(i): operação para remover um elemento em uma posição específica.

O tipo de lista mais simples é o Vetor. Sua implementação é baseada em uma estrutura sequencial, onde por padrão os elementos são adicionados no final, após o último elemento. Seu acesso é através da posição (índice) em que foram inseridos.

Essa implementação é excelente para acessar rapidamente um elemento, por exemplo, para acessar o elemento 63, basta informar o índice 2 e o acesso será direto (GET(2))

Porém não é tão interessante quando queremos inserir um elemento em uma posição no meio, por exemplo, na posição 3 (ADD(2, 18)) pois teríamos que deslocar todos os demais elementos para direita.

Apesar esse deslocamento ser uma operação simples, em um vetor com muitos elementos essa operação pode ser custosa e demorada.

public class Vetor implements Lista {

 String[] elementos = new String[10];
 int indice;

 @Override
 public void add(String elemento) {
  elementos[indice] = elemento;
  indice++;
 }
 
 @Override
 public String get(int i) {
  return elementos[i];
 }

 @Override
 public void add(int posicao, String elemento) {
  for (int i = indice - 1; i >= posicao; i--) {
   elementos[i + 1] = elementos[i];
  }

  elementos[posicao] = elemento;
  indice++;
 }
 
 @Override
 public void remove(int posicao) {
  elementos[posicao] = null;
  
  for (int i = posicao; i+1 < elementos.length; i++) {
   elementos[i] = elementos[i+1];
  }

  indice--;
 }
 
 public static void main(String[] args) {
  Vetor vetor = new Vetor();
  vetor.add("A");
  vetor.add("C");
  vetor.add("D");
  vetor.add("E");
  
  System.out.println(Arrays.asList(vetor.elementos));

  vetor.add(1, "B");

  String c = vetor.get(2);
  System.out.println(c);
  
  System.out.println(Arrays.asList(vetor.elementos));

  vetor.remove(2);
  
  System.out.println(Arrays.asList(vetor.elementos));
 }

}

Eis que surgem as Listas ligadas para o resgate =D.
Essas listas possuem uma implementação mais elaborada. Para percorrer os elementos é necessário que cada elemento saiba onde está seu sucessor.

A grande vantagem desta implementação é que se precisarmos inserir um elemento no meio (ADD(2,'E')), basta fazer com que o elemento anterior aponte para o novo e o novo para o sucessor tornando a inserção uma operação rápida.

Em contrapartida, como nem tudo são flores, o acesso a um determinado elemento pelo índice já não é mais tão fácil. Na verdade, precisamos navegar do primeiro elemento perguntando onde está o próximo até chegarmos na posição desejada.
Além disso a navegação ocorre apenas em uma direção, do primeiro elemento até o último e há casos em que gostaríamos de ir e voltar nessa navegação.

public class ListaLigada implements Lista {

 No primeiro;
 No ultimo;

 @Override
 public void add(String elemento) {

  if (primeiro == null) {
   primeiro = new No(elemento);
   ultimo = primeiro;
  } else {
   ultimo.proximo = new No(elemento);
   ultimo = ultimo.proximo;
  }

 }

 @Override
 public String get(int posicao) {
  No no = buscarNo(posicao);
  return no.elemento;
 }

  @Override
 public void add(int posicao, String elemento) {
  No retorno = buscarNo(posicao-1);
  No novo = new No(elemento);
  novo.proximo=retorno.proximo;
  retorno.proximo = novo;
 }

 @Override
 public void remove(int posicao) {
  No retorno = buscarNo(posicao-1);
  No temp = retorno.proximo;
  retorno.proximo = temp.proximo;
 }
 
 private No buscarNo(int posicao) {
  No retorno = primeiro;
  int contador = 0;
  while (contador < posicao) {
   retorno = retorno.proximo;
   contador++;
  }
  return retorno;
 }
 
 public void imprimir() {
  String conteudo = primeiro.elemento;
  No proximoNo = primeiro.proximo;
  while(proximoNo != null) {
   conteudo+=", "+proximoNo.elemento;
   proximoNo = proximoNo.proximo;
  }
  System.out.println(conteudo);
 }

 public static void main(String[] args) {
  ListaLigada listaLigada = new ListaLigada();
  listaLigada.add("A");
  listaLigada.add("C");
  listaLigada.add("D");
  listaLigada.add("E");
  
  listaLigada.imprimir();

  listaLigada.add(1, "B");
  
  listaLigada.imprimir();

  String c = listaLigada.get(2);
  System.out.println(c);

  listaLigada.remove(2);
  
  listaLigada.imprimir();


 }

}

Para ter uma navegação bidirecional, a listas podem ser duplamente ligadas. Isso significa que o elemento sabe não só a posição do próximo mas também do anterior a ele, seu antecessor.

public class ListaDuplamenteLigada implements Lista {

 No primeiro;
 No ultimo;

 @Override
 public void add(String elemento) {
  addFim(elemento);
 }

 public void addFim(String elemento) {

  if (primeiro == null) {
   primeiro = new No(elemento);
   ultimo = primeiro;
  } else {
   No novo = new No(elemento);
   ultimo.proximo = novo;
   novo.anterior = ultimo;
   ultimo = novo;
  }
 }

 public void addInicio(String elemento) {
  if (primeiro == null) {
   primeiro = new No(elemento);
   ultimo = primeiro;
  } else {
   No novo = new No(elemento);
   
   primeiro.anterior = novo;
   novo.proximo = primeiro;
   primeiro = novo;
  }
 }

 @Override
 public String get(int posicao) {
  No no = buscarNo(posicao);
  return no.elemento;
 }

 @Override
 public void add(int posicao, String elemento) {
  No novo = new No(elemento);
  
  No esquerda = buscarNo(posicao - 1);  
  No direita = esquerda.proximo;
  
  novo.proximo = direita;
  novo.anterior = esquerda;
  
  direita.anterior = novo;
  esquerda.proximo = novo;
  
 }

 @Override
 public void remove(int posicao) {
  No retorno = buscarNo(posicao);
  
  No esquerda = retorno.anterior;
  No direita = retorno.proximo;
  
  esquerda.proximo = direita;
  direita.anterior = esquerda;
 }

 private No buscarNo(int posicao) {
  No retorno = primeiro;
  int contador = 0;
  while (contador < posicao) {
   retorno = retorno.proximo;
   contador++;
  }
  return retorno;
 }

 public void imprimirParaFrente() {
  String conteudo = primeiro.elemento;
  No proximoNo = primeiro.proximo;
  while (proximoNo != null) {
   conteudo += ", " + proximoNo.elemento;
   proximoNo = proximoNo.proximo;
  }
  System.out.println(conteudo);
 }
 
 public void imprimirParaTras() {
  String conteudo = ultimo.elemento;
  No noAnterior = ultimo.anterior;
  while (noAnterior != null) {
   conteudo += ", " + noAnterior.elemento;
   noAnterior = noAnterior.anterior;
  }
  System.out.println(conteudo);
 }

 public static void main(String[] args) {
  ListaDuplamenteLigada listaLigada = new ListaDuplamenteLigada();
  listaLigada.add("C");
  listaLigada.add("D");
  listaLigada.add("E");
  
  listaLigada.imprimirParaTras();
  listaLigada.imprimirParaFrente();
  System.out.println();
  listaLigada.addInicio("A");

  listaLigada.imprimirParaTras();
  listaLigada.imprimirParaFrente();
  System.out.println();

  listaLigada.add(1, "B");

  listaLigada.imprimirParaTras();
  listaLigada.imprimirParaFrente();
  System.out.println();

  String c = listaLigada.get(2);
  System.out.println(c);

  listaLigada.remove(2);

  listaLigada.imprimirParaTras();
  listaLigada.imprimirParaFrente();
  System.out.println();

 }

}

Resumindo:
- Listas são estruturas que permitem armazenar elementos garantindo sua ordem de inserção e permitindo repetir elementos.
- Vetor tem acesso rápido e fácil aos elementos porém pode demorar mais para inserir em determinadas posições.
- Listas ligadas e duplamente ligadas são excelentes para inserção em posições desejadas porém não são boas para acessar elementos específicos.

A sua escolha em relação à qual usar vai depender da sua necessidade. Acesso ou Inserção.

Podemos concluir também que as Pilhas e Listas são um tipo de lista que possuem características mais específicas.

Estrutura de Dados Parte 2 - Fila

Continuando a sequência de post's sobre estrutura de dados (8 anos depois =D)

Sempre gosto de começar o post com algum exemplo, e tento aproximá-lo ao máximo de situações que acontece em nosso dia-a-dia. Acredito que associar a algo prático ou a algo da nossa rotina torna mais fácil a compreensão do assunto, e tem algo mais comum que Filas no nosso dia-a-dia? Se vamos ao banco tem fila, se vamos ao supermercado tem fila, se vamos ao cinema na estreia dos Vingadores... tem fila. Apesar delas serem uma parte relativamente irritante da nossa vida, as filas são uma ótima forma de armazenar informações que pretendemos usar depois.

Quando temos que enfrentar filas no nosso dia a dia, procuramos sempre pela menor pois sabemos que quanto menor, mais rápido chegará nossa vez. Em outras palavras, por manterem a ordem, sabemos que quem chega primeiro é atendido primeiro.

Nas filas, ao contrários das Pilhas, o primeiro elemento a entrar é sempre o primeiro elemento a sair. Essa característica é conhecida como FIFO (First In, First Out) e possui apenas duas operações básicas chamadas de INSERT e REMOVE.


INSERT: operação para inserir um elemento no final da fila.
REMOVE: operação para remover um elemento do início da fila.

Outros operações que podem ser úteis:

isFull: operação que indica se a fila está cheia.
isEmpty: operação que indica se a fila está vazia.
size: operação que indica o tamanho da fila.

Uma implementação simples em java seria:

public class Fila {

 int tamanho = 10;
 String[] elementos = new String[tamanho];
 int fim = 0;
 int inicio = 0;

 public void insert(String elemento) {
  elementos[fim] = elemento;

  if (elemento != null && fim < tamanho) {
   fim++;
  }
 }

 public String remove() {
  String elemento = elementos[inicio];

  if (elemento != null) {
   inicio++;
  }
  return elemento;
 }

 public boolean isEmpty() {
  return inicio == fim;
 }

 public boolean isFull() {
  return size() == tamanho;
 }

 public int size() {
  return fim - inicio;
 }
 
 public static void main(String[] args) {
  Fila fila = new Fila();
  fila.insert("1");
  fila.insert("2");
  fila.insert("3");
  
  String e1 = fila.remove();
  System.out.println(e1);
  
  String e2 = fila.remove();
  System.out.println(e2);
  
  String e3 = fila.remove();
  System.out.println(e3);
 }

}

Reparem que ao executar o código, a saída será 1 2 3, nessa ordem, justamente por que o 1 foi o primeiro elemento inserido e será o primeiro a ser removido.

O que acontece se atingirmos a capacidade máxima da nossa fila? como seria possível continuar adicionando elementos? o que ocorre se removemos todos os elementos da lista? será que conseguimos continuar usando?

Há muitas melhorias que podem ser feitas nesta implementação para resolver as questões acima, mas isso deixaria a explicação bem mais complexa. Quem sabe não faço um post avançado sobre o assunto…

Uma coisa importante para ressaltar é que a maioria das linguagens de programação possuem uma biblioteca rica em estrutura de dados e que na maioria das vezes são suficientes para resolver 90% dos problemas. Nesses casos é preferível utilizar essas implementações pois já são otimizadas e testadas.

Filas são amplamente utilizadas na programação para resolver problemas que requerem uma ordem de execução como por exemplo a fila de arquivos para impressão ou o buffer de um vídeo no youtube.

Torcendo para que não leve mais 8 anos, esperem pelo próximo post sobre Listas.