<Direto ao Ponto 52> Estruturas de Dados - Árvores

Artigos desta série: ( < ) Anterior | Índice | Seguinte ( > )

Olá, dev!

(e na figura da capa deste artigo (alguns dos meus livros )

Este é mais um artigo da série DIRETO AO PONTO, que eu estou escrevendo para a DIO. Ele vai tratar de uma estrutura hierárquica de dados, as árvores.

Sumário

1. Introdução

2. As árvores

3. Formas de implementação de árvores

4. Exemplos de aplicações implementadas com árvores

5. Considerações finais

6. Referências

1 – Introdução

Eu criei a série de artigos DIRETO AO PONTO com o objetivo de apresentar, de forma simples e direta, conhecimentos básicos da programação e de computação, principalmente, para os iniciantes.

Aqui, são tratados de temas como lógica de programação, linguagens, hardware dos computadores, história da computação e assuntos relacionados à plataforma da DIO, como a escrita de artigos e os desafios de código.

Neste artigo, eu vou falar sobre as árvores e as aplicações que usam árvores na implementação. Dentre estas aplicações, estão as árvores de busca, índice para bancos de dados e parsing de linguagens e compiladores.

2 – As árvores

Da mesma forma que as pilhas, as árvores também são um Tipo Abstrato de Dado (TAD), um modelo matemático que especifica um conjunto de dados e as operações que podem ser realizadas sobre eles, sem tratar da implementação destas operações.

Diferentemente das estruturas anteriores, que eram lineares, a estrutura de dados árvore é do tipo hierárquico, muito usada na representação de dados como organogramas, árvores genealógicas, taxonomias biológicas, modelos de Computação Gráfica etc.

Existem vários tipos de árvores, sendo estes os mais comuns:

· Árvores binárias - Cada nó tem, no máximo, 2 filhos (esquerdo e direito). É a base para outros tipos de árvores, como as árvores binárias de busca e as árvores balanceadas.

· Árvores n-árias - Cada nó pode ter múltiplos filhos, no máximo N filhos. É uma generalização das árvores binárias, usada, por exemplo, em sistemas de arquivos, onde cada diretório pode ter um número arbitrário de subdiretórios ou arquivos.

· Árvores binárias de busca (“Binary Search Tree” - BST) - Para cada nó, todos os valores na subárvore esquerda são menores que o valor do nó, e todos os valores na subárvore direita são maiores. Ela permite operações de busca eficientes.

· Árvores B e B+ - São muito eficientes para operações em disco e armazenam grandes volumes de dados, por isso, são comuns em sistemas de banco de dados e sistemas de arquivos.

· Árvores balanceadas - Numa árvore balanceada, as subárvores esquerda e direita de cada nó têm alturas aproximadamente iguais, é uma árvore equilibrada. Elas garantem operações de busca, inserção e exclusão de baixa complexidade, como O(log n). Exemplos são árvores Red-Black.

· Árvores de busca; É usada para armazenar dados de forma ordenada, permitindo inserção, exclusão e pesquisa de elementos em tempo logarítmico.

· Árvores de decisão – Cada nó interno representa uma pergunta ou teste em relação a uma característica, cada ramo representa o resultado do teste e cada folha representa uma decisão ou resultado. É muito usada em aprendizado de máquina e inteligência artificial.

· Árvores de sintaxe - Representa a estrutura sintática de uma expressão ou declaração em uma linguagem de programação, de acordo com sua gramática. É muito usada em compiladores.

· Árvores Red-Black - Árvores binárias de busca balanceada que têm um conjunto de regras de coloração (vermelho e preto) para garantir que o caminho mais longo da raiz a qualquer folha seja, no máximo, duas vezes mais longo que o caminho mais curto. Usada em bibliotecas de software para implementar mapas e conjuntos ordenados.

Cada tipo de árvore é otimizado para diferentes casos de uso, então escolher a estrutura correta depende do problema que se deseja resolver.

Uma árvore possui as seguintes características principais:

· Hierárquica: Ela é composta por nós (ou vértices), onde há uma relação pai-filho entre os elementos;

· Nó Raiz: O nó raiz é o ponto de partida da árvore e é o único nó que não tem um pai. Todos os outros nós se derivam da raiz;

· Nós Filhos: Nós que se originam de outro nó (chamado nó pai);

· Nós Folhas: Nós que não têm filhos, são os nós terminais da árvore;

· Subárvore: Uma subárvore é uma parte da árvore que é composta por um nó e todos os seus descendentes;

· Recursiva: Cada subárvore de uma árvore também é uma árvore, o que facilita a implementação de algoritmos recursivos;

· Altura da Árvore: Distância máxima (número de arestas) da raiz até uma folha;

· Profundidade de um Nó: Distância entre ele e o nó raiz.

· Grau de um Nó: Número de filhos do nó. Em uma árvore binária, cada nó só pode ter até dois filhos.

Além da criação de uma variável de um tipo específico para manipular árvores (ou algum tipo primitivo, que pode similar uma árvore – vetor, ponteiro, lista) e inicialização, as operações básicas que podem ser realizadas com uma árvore (em pseudo-código) são:

· Inserção de um nó;

· Remoção de um nó;

· Acesso a algum nó.

A inserção e remoção de nós em uma árvore dependem do tipo de árvore utilizada e seguem regras específicas para manter as propriedades da estrutura.

Por simplicidade didática (e falta de espaço para tratar de todos os tipos!), vamos tratar apenas na inserção e remoção em uma árvore binária de busca (BST), uma das árvores mais comuns usadas em algoritmos e estruturas de dados. Os textos sobre as operações abaixo seguem PANTUZA [1]:

Inserção de um nó – Para este tipo de árvore, a lógica de inserção se baseia no valor do nó que está sendo inserido:

Se o valor do novo nó for menor que o valor do nó atual, ele é inserido à sua esquerda;
Caso contrário, ele é inserido à direita;
O processo continua recursivamente até encontrar uma posição vazia (nulo), onde o novo nó será inserido.

Veja os exemplos seguintes:

Inserção do nó 4 na árvore inicial:

1. Começa na raiz ( 5 )

2. 4 < 5 – Vá para o nó da esquerda ( 3 );

3. 4 > 3 – Vá para o nó da direita ( vazio );

4. O nó está vazio – inserir o 4 aí.

Remoção de um nó – Neste caso, a remoção de um nó depende do número de filhos do nó que vai ser removido. Estes são os casos principais:

Caso 1: Nó Sem Filhos (Nó Folha)

Ele pode ser removido da árvore sem problemas;

Caso 2: Nó com Um Filho

O filho desse nó substitui o nó a ser removido;

Caso 3: Nó com Dois Filhos

É preciso encontrar o sucessor in-order (o menor nó da subárvore direita) ou o predecessor in-order (o maior nó da subárvore esquerda) para substituir o nó a ser removido.
Depois da substituição, o sucessor ou predecessor deve ser removido da sua posição original.

Remoção do nó raiz da árvore:

1. Começa na raiz ( 5 )

2. Busca pelo mínimo à direita. Vá para a direita ( 8 );

3. Vá para a esquerda, em busca o valor filho menor ( 7 );

4. Este filho menor ( 7 ) passa a ser o pai do seu pai ( 8 );

5. O seu antigo pai ( 8 ) fica com o filho da esquerda nulo;

6. Remove o nó raiz ( 5 );

7. Susbtitui o nó raiz pelo pai do ( 8 );

Acesso a um nó (Busca) – O acesso é obtido percorrendo a árvore por meio da comparação do valore dos nós e o desvio para a esquerda (caso o valor do nó buscado seja menor) ou para a direita, caso contrário. Se for igual, o nó foi encontrado.

Buscar o elemento de valor 4

1. Começa na raiz

2. 4 = 5? Não! 4 < 5, então siga para o nó da esquerda (3);

3. 4 = 3? Não! 4 > 3, então siga para o nó da direita (4);

4 = 3? SIM! Encontrou o 4.

O acesso a todos os elementos de uma árvore é chamado de percurso ou travessia (traversal). Um percurso é uma técnica para visitar todos os nós da árvore em uma ordem específica. Existem três tipos principais de percursos para árvores binárias:

Pré-ordem – Ordem de visita: Raiz, Esquerda, Direita.

Primeiro, é visitado o nó raiz, depois, a subárvore esquerda é percorrida, recursivamente, e, por último, a subárvore direita, recursivamente.

Em ordem – Ordem de visita: Esquerda, Raiz, Direita.

Percorrer primeiro a subárvore esquerda, depois visitar o nó raiz e, por último, percorrer a subárvore direita;

Pós-ordem – Ordem de vista: Esquerda, Direita, Raiz.

Percorrer a subárvore esquerda, recursivamente, depois a subárvore direita, recursivamente, e, finalmente, visitar o nó raiz;

Por exemplo, para esta árvore acima, teremos os seguintes percursos (ver figura a seguir):

· Pré-ordem: F, B, A, D, C, E, G, I, H

· Em-ordem: A, B, C, D, E, F, G, H, I

· Pós-ordem: A, C, E, D, B, H, I, G, F

3 – Formas de implementação de árvores

Uma árvore pode ser implementada de várias maneiras: usando vetor estático, lista encadeada (com ponteiros), com um tipo lista (list) ou por um tipo específica (TreeSet). Vamos ver um resumo de cada uma delas.

Cada abordagem tem suas características e é escolhida com base no contexto de uso e nos requisitos de desempenho.

I - IMPLEMENTAÇÃO COM LISTA ENCADEADA (COM PONTEIROS)

O uso de ponteiros e listas encadeadas (ligadas) para implementar vários tipos de estruturas de dados (listas, filas e pilhas) já foi bem detalhado para aqueles casos, este aqui é só mais uma implementação semelhante àquelas.

Por isso, vou mostrar apenas como se representa uma árvore com ponteiros, uma vez que as operações de inserção, exclusão e busca já foram detalhadas na seção anterior.

A figura abaixo mostra uma estrutura de uma árvore representada por nós e links para o nó da esquerda e o nó da direita.

Um exemplo de uma estrutura árvore na linguagem C é:

struct No {

int info;

struct No* esquerda; // Ponteiro para o filho esquerdo

struct No* direita; // Ponteiro para o filho direito

};

Um exemplo de uma estrutura árvore com lista encadeada para os nós na linguagem C++ é:

struct NoArvore {

int info;

vector<NoArvore*> filhos; // Vetor de ponteiros para filhos

};

II - IMPLEMENTAÇÃO COM VETOR ESTÁTICO

Um vetor estático é uma técnica eficiente, principalmente para árvores completas ou quase completas.

Neste caso, os elementos do vetor são organizados para que a relação pai-filho seja mantida.

A regra para esta representação é a seguinte:

Para um nó localizado no índice i:

· O filho esquerdo está em 2 * i + 1

· O filho direito está em 2 * i + 2

Ou seja, o nó raiz está no índice 0, o filho da esquerda está no ídice 1 e o da direita no índice 2, e assim por diante.

Veja um exemplo de Uso em Python:

arvore = [6, 3, 8, 2, 5, 7, 9]

A figura a seguir mostra a árvore e do vetor associado a ela:

Pode ser que a árvore não esteja completa, faltando elementos, nesse caso, a representação por um vetor ficaria assim, onde o valor nulo pode ser -1, Null, None etc.:

Esta representação por vetor estático é muito usada em estruturas como heap binário e árvores binárias completas.

III - IMPLEMENTAÇÃO USANDO A ESTRUTURA LIST

Neste caso, pode-se partir de uma lista, que representa a árvore como em um vetor estático. Depois, cria-se uma lista para cada nó, com seus filhos. Um filho vazio é representado por None.

arvore = [50, 30, 70, 20, 40, 60, 80]

no = [50, 30, 70]

no = [30, 20, 40]

no = [70, 60, 80]

IV - IMPLEMENTAÇÃO USANDO UM TIPO ESPECÍFICO PARA ÁRVORE

Cada linguagem que oferece algum tipo específico (ou biblioteca) define as características do tipo e os métodos oferecidos para a manipulação das árvores.

Algumas delas são C, C++, C#, Java, Python, Javascript, Go, Haskell e Rust.

4 – Exemplos de aplicações implementadas com árvore

A seguir, seguem alguns programas básicos que implementam pilhas, em linguagens diferentes:

NA LINGUAGEM PASCAL – USANDO VETOR ESTÁTICO

Nesta implementação, utilizamos um vetor para representar uma árvore binária completa, onde a relação entre pai e filhos é mantida com base em índices.

Estrutura de Armazenamento

O nó raiz está no índice 0.
Para um nó em um índice i: (I >= 0)
O filho esquerdo está em 2 * i + 1.
O filho direito está em 2 * i + 2.
O pai está em (i - 1) div 2 (divisão inteira).

program ArvoreBinariaVetor;
 
const
 TAMANHO_MAX = 15; { Tamanho máximo da árvore }
 
type
 TArvore = array[0..TAMANHO_MAX - 1] of Integer;
 
var
 arvore: TArvore;
 i: Integer;
 
{ Inicializa a árvore com valores padrão }
procedure InicializarArvore(var arv: TArvore);
var
 i: Integer;
begin
 for i := 0 to TAMANHO_MAX - 1 do
 arv[i] := -1; { -1 indica um nó vazio }
end;
 
{ Insere um valor na árvore }
procedure Inserir(var arv: TArvore; valor: Integer);
var
 i: Integer;
begin
 i := 0;
 while (i < TAMANHO_MAX) and (arv[i] <> -1) do
 begin
 if valor < arv[i] then
   i := 2 * i + 1 { Vai para o filho esquerdo }
 else
   i := 2 * i + 2; { Vai para o filho direito }
 end;
 
 if i < TAMANHO_MAX then
 arv[i] := valor
 else
 WriteLn('Erro: A árvore está cheia, não é possível inserir ', valor);
end;
 
{ Exibe a árvore em ordem (in-order traversal) }
procedure EmOrdem(var arv: TArvore; indice: Integer);
begin
 if (indice < TAMANHO_MAX) and (arv[indice] <> -1) then
 begin
 EmOrdem(arv, 2 * indice + 1); { Percorre filho esquerdo }
 Write(arv[indice], ' ');       { Exibe o valor do nó }
 EmOrdem(arv, 2 * indice + 2); { Percorre filho direito }
 end;
end;
 
begin
 InicializarArvore(arvore);
 
 { Inserindo valores na árvore }
 Inserir(arvore, 50);
 Inserir(arvore, 30);
 Inserir(arvore, 70);
 Inserir(arvore, 20);
 Inserir(arvore, 40);
 Inserir(arvore, 60);
 Inserir(arvore, 80);
 
 { Exibindo a árvore em ordem }
 WriteLn('Árvore em ordem:');
 EmOrdem(arvore, 0);
 WriteLn;
end.

Saída do programa

Árvore em ordem:

20 30 40 50 60 70 80

LINGUAGEM C – USANDO LISTA ENCADEADA COM PONTEIROS

Aqui está um exemplo de um programa em C que implementa uma árvore binária usando ponteiros. Nesta abordagem, cada nó da árvore é uma estrutura (struct) que contém um valor e ponteiros para seus nós filhos.

Cada nó é representado por uma estrutura contendo:

· Um campo data para armazenar o valor (dado);

· Um ponteiro para o filho esquerdo (esquerdo);

· Um ponteiro para o filho direito (direito).

#include <stdio.h>
#include <stdlib.h>
 
// Definição de um nó da árvore binária
struct No {
 int dado;
 struct No* esquerdo;
 struct No* direito;
};
 
// Função para criar um novo nó
struct No* criarNo(int valor) {
 struct No* novoNo = (struct No*)malloc(sizeof(struct No));
 novoNo->dado = valor;
 novoNo-> esquerdo = NULL;
 novoNo-> direito = NULL;
 return novoNo;
}
 
// Função para inserir um valor na árvore binária de busca
struct No* inserir(struct No* raiz, int valor) {
 if (raiz == NULL) {
     // Se a árvore está vazia, cria um novo nó
     return criarNo(valor);
 }
 
 // Inserir na subárvore esquerda ou direita com base no valor
 if (valor < raiz->dado) {
     raiz-> esquerdo = inserir(raiz-> esquerdo, valor);
 } else {
     raiz-> direito = inserir(raiz-> direito, valor);
 }
 
 return raiz;
}
 
// Função para percorrer a árvore em ordem (travessia em ordem)
void travessiaEmOrdem(struct No* raiz) {
 if (raiz != NULL) {
     travessiaEmOrdem(raiz-> esquerdo);     // Percorre a subárvore esquerda
     printf("%d ", raiz->dado);        // Exibe o valor do nó
     travessiaEmOrdem(raiz-> direito);    // Percorre a subárvore direita
 }
}
 
// Função principal
int main() {
 struct No* raiz = NULL; // Inicializa a árvore vazia
 
 // Inserindo valores na árvore
 raiz = inserir(raiz, 50);
 raiz = inserir(raiz, 30);
 raiz = inserir(raiz, 70);
 raiz = inserir(raiz, 20);
 raiz = inserir(raiz, 40);
 raiz = inserir(raiz, 60);
 raiz = inserir(raiz, 80);
 
 // Exibindo a árvore em ordem
 printf("Árvore em ordem (travessia em ordem): ");
 travessiaEmOrdem(raiz);
 printf("\n");
 
 return 0;
}

Saída do programa

Árvore em ordem (travessia em ordem): 20 30 40 50 60 70 80

NA LINGUAGEM PYTHON – USANDO O TIPO LIST

Neste caso, a representação inicial da árvore é implementada por uma lista, como se fosse um vetor estático. Depois, cada nó é representado por uma lista, e a estrutura da árvore é construída recursivamente.

Cada nó da árvore é uma lista com três elementos:

· O primeiro elemento é o valor do nó.

· O segundo elemento é a subárvore esquerda.

· O terceiro elemento é a subárvore direita.

# Função para criar um novo nó da árvore
def criar_no(valor):
 return [valor, None, None] # [valor, filho_esquerdo, filho_direito]
 
# Função para inserir um valor na árvore binária de busca
def inserir(no, valor):
 if no is None:
     return criar_no(valor)
 
 if valor < no[0]:
     no[1] = inserir(no[1], valor) # Insere na subárvore esquerda
 else:
     no[2] = inserir(no[2], valor) # Insere na subárvore direita
 
 return no
 
# Função para percorrer a árvore em ordem (in-order traversal)
def em_ordem(no):
 if no is not None:
     em_ordem(no[1])            # Percorre a subárvore esquerda
     print(no[0], end=' ')      # Exibe o valor do nó
     em_ordem(no[2])            # Percorre a subárvore direita
 
# Função principal
def main():
 raiz = None # Inicializa a árvore vazia
 
 # Inserindo valores na árvore
 valores = [50, 30, 70, 20, 40, 60, 80]
 for valor in valores:
     raiz = inserir(raiz, valor)
 
 # Exibindo a árvore em ordem
 print("Árvore em ordem (travessia em ordem):")
 em_ordem(raiz)
 print()
 
# Executa a função principal
if __name__ == "__main__":
 main()

Saída do programa

Árvore em ordem (travessia em ordem):

20 30 40 50 60 70 80

LINGUAGEM JAVA – USANDO O TIPO ESPECÍFICO TREE

Vamos usar uma estrutura específica para manipular árvores, a classe TreeSet, para implementar uma árvore binária de busca, baseada em uma árvore Red-Black, uma árvore binária de busca autobalanceada.

A classe TreeSet implementa a interface NavigableSet, a qual estende internamente a interface SortedSet, cuja hierarquia é mostrada abaixo:

Alguns métodos implementados por esta estrutura (TreeSet) são:

· add(): inclui um elemento na árvore;

· remove(): remove um elemento da árvore;

· size(): retorna o número de elementos da árvore;

· contains(): verifica se um determinado elemento está na árvore;

· clear(): limpa a árvore, removendo todos os seus elementos;

· isEmpty(): verifica se a árvore está vazia, sem elementos.

import java.util.TreeSet;
 
public class ArvoreExemplo {
 public static void main(String[] args) {
     // Criando uma TreeSet para armazenar valores inteiros
     TreeSet<Integer> arvore = new TreeSet<>();
 
     // Inserindo valores na árvore
     arvore.add(50);
     arvore.add(30);
     arvore.add(70);
     arvore.add(20);
     arvore.add(40);
     arvore.add(60);
     arvore.add(80);
 
     // Exibindo os valores da árvore em ordem crescente
     System.out.println("Valores da árvore em ordem: " + arvore);
 
     // Verificando se um valor específico está presente na árvore
     int valorBusca = 40;
     if (arvore.contains(valorBusca)) {
         System.out.println("O valor " + valorBusca + " está presente na árvore.");
     } else {
         System.out.println("O valor " + valorBusca + " não está presente na árvore.");
     }
 
     // Removendo um valor da árvore
     arvore.remove(30);
     System.out.println("Valores da árvore após remover 30: " + arvore);
 
     // Encontrando o menor e o maior valor na árvore
     System.out.println("Menor valor na árvore: " + arvore.first());
     System.out.println("Maior valor na árvore: " + arvore.last());
 }
}

Saída do programa

Valores da árvore em ordem: [20, 30, 40, 50, 60, 70, 80]

O valor 40 está presente na árvore.

Valores da árvore após remover 30: [20, 40, 50, 60, 70, 80]

Menor valor na árvore: 20

Maior valor na árvore: 80

5 – Considerações finais

Este é mais um artigo da série DIRETO AO PONTO, que eu estou escrevendo para a DIO. Neste artigo eu tratei das árvores, mais um Tipo Abstrato de Dado (TAD), juntamente com as listas, filas e pilhas.

Uma árvore é uma estrutura de dados hierárquica, muito usada na programação.

Elas são apropriadas em aplicações que usam representação de dados como organogramas, árvores genealógicas, taxonomias biológicas, modelos de Computação Gráfica.

As aplicações mais comuns que usam árvore são Banco de Dados, IA e Machine Learning, Compiladores, Organização de Arquivos, Redes, Compressão de Dados, Algoritmos de Jogos etc.

Uma árvore pode ser implementada de várias formas, usando vetores estáticos, ponteiros, listas ou estruturas específicas para manipulação de pilhas, como TreeSet, da linguagem Java

Algumas destas formas são bem antigas (vetores), mas continuam em uso por serem muito didáticas, principalmente para os iniciantes em programação, já outras são bem trabalhosas (com ponteiros), pois exigem completo gerenciamento da memória pelo programador.

As formas mais atuais de implementação são usando listas (como em Python) ou estruturas específicas, como a classe TreeSet, da linguagem Java.

Neste artigo, foram mostrados os detalhes dos conceitos e das operações usadas para a implementação de árvores usando várias abordagens.

Também foram apresentados exemplos de códigos com a implementação de árvores binárias de busca, usando cada uma das 4 formas citadas anteriormente, vetores estáticos, ponteiros para listas encadeadas, tipo list, do Python, e um tipo específico, TreeSet, do Java.

No próximo artigo, vamos falar dos grafos, estruturas de dados muito usadas na programação.

6 – Referências

Praticamente todo o conteúdo deste artigo foi tirado do que eu aprendi (e me lembro) sobre o assunto desde o início da minha carreira como programador, desde os anos 80 até agora.

Para criar os códigos dos exemplos, eu consultei o ChatGPT e fiz algumas correções necessárias para sair do jeito que eu queria. Todos os códigos foram testados e rodaram sem problemas.

No entanto, destaco esta referência sobre árvores de busca binária, com exemplos bem didáticos, com figuras animadas.

[1] Gustavo PANTUZA. Tipos abstratos de dados - Árvore de busca binária (Binary search tree). Disponível em: <https://blog.pantuza.com/artigos/tipos-abstratos-de-dados-arvore-de-busca-binaria-binary-search-tree>. Acesso em: 12/10/2024.

Artigos desta série: ( < ) Anterior | Índice | Seguinte ( > )