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;
 }

}