Introdução

No estudo da ciência da computação, estruturas de dados não lineares como árvores e grafos são fundamentais para modelar problemas complexos. Enquanto listas e pilhas organizam dados sequencialmente, árvores e grafos permitem representar hierarquias e relações intrincadas de forma eficiente. Nesta aula, vamos detalhar árvores binárias de busca, árvores AVL, e os conceitos básicos de grafos, juntamente com seus principais algoritmos de percurso.

Árvores Binárias de Busca (BST)

Uma BST é uma estrutura onde cada nó possui até dois filhos. A propriedade fundamental é que todos os elementos da subárvore esquerda são menores que a raiz, e todos os da subárvore direita são maiores. Isso permite buscas binárias eficientes.

A complexidade das operações depende diretamente da altura da árvore. No pior caso, uma BST pode degenerar em uma lista ligada (O(n)), o que motiva a criação de árvores balanceadas.

struct TreeNode {
    int key;
    TreeNode* left;
    TreeNode* right;
};

Árvores AVL e o Balanceamento

As árvores AVL resolvem o problema de degeneração das BSTs através do balanceamento automático. Cada nó armazena seu fator de balanceamento (diferença entre a altura da subárvore direita e esquerda). Quando este fator sai do intervalo [-1, 1], rotações são aplicadas para rebalancear a árvore.

Existem quatro tipos de rotações: rotação simples à direita, à esquerda, rotação dupla direita-esquerda e esquerda-direita. A grande vantagem é garantir complexidade O(log n) para todas as operações, tornando-as ideais para cenários com muitas buscas.

Node* rotateRight(Node* y) {
    Node* x = y->left;
    Node* T = x->right;
    x->right = y;
    y->left = T;
    return x;
}

Grafos: Definição e Representação

Um grafo é um par ordenado (V, E) composto por um conjunto de vértices (V) e um conjunto de arestas (E). As arestas podem ser direcionadas (dígrafos) ou não direcionadas. A forma mais comum de representar um grafo em um programa é através de matrizes de adjacência ou listas de adjacência.

A matriz de adjacência é uma tabela V×V onde o valor na posição (i, j) indica se existe uma aresta entre os vértices i e j. A lista de adjacência, por sua vez, armazena para cada vértice uma lista de seus vizinhos. Para grafos esparsos, a lista de adjacência é muito mais eficiente em termos de memória.

Busca em Largura (BFS) e Busca em Profundidade (DFS)

Estes são os dois principais algoritmos para navegar por um grafo. A BFS utiliza uma fila e explora o grafo nível por nível. É ideal para encontrar o menor caminho em um grafo não ponderado. A DFS utiliza uma pilha (ou recursão) e explora o grafo até o final de um ramo antes de voltar. DFS é útil para ordenação topológica, detecção de ciclos e componentes fortemente conexos.

from collections import deque
def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    while queue:
        vertex = queue.popleft()
        print(vertex)
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

Aplicações Práticas e Considerações Finais

As árvores são amplamente utilizadas em sistemas de arquivos, interfaces de usuário (componentes DOM), bancos de dados (B-Trees), e algoritmos de compressão (Huffman). Os grafos são a base de redes sociais, sistemas de recomendação, GPS, e motores de busca. Dominar essas estruturas é fundamental para a resolução de problemas reais de forma otimizada.

Pontos-chave

  • BSTs são eficientes mas podem degenerar; AVLs garantem balanceamento.
  • A escolha da estrutura de dados depende do tipo de operação e dos requisitos de desempenho.
  • Grafos modelam relacionamentos complexos; BFS e DFS são algoritmos de percurso fundamentais.
  • Matriz de adjacência ocupa mais memória em grafos esparsos que lista de adjacência.

Perguntas Frequentes

Qual a principal diferença entre uma BST e uma AVL?

A principal diferença é que a AVL é autobalanceável. Uma BST comum pode se tornar uma estrutura linear se os dados forem inseridos em ordem, enquanto a AVL sempre mantém a altura balanceada, garantindo complexidade O(log n) para as operações principais.

Quando devo usar Matriz de Adjacência vs Lista de Adjacência?

Use Matriz de Adjacência quando o grafo for denso (muitas arestas) e você precisar verificar rapidamente se uma aresta existe entre dois vértices. Use Lista de Adjacência para grafos esparsos (poucas arestas) para economizar memória e iterar sobre os vizinhos de um vértice eficientemente.

A DFS recursiva pode causar stack overflow?

Sim, em grafos muito grandes, a recursão da DFS pode estourar a pilha de chamadas. Nesses casos, é recomendado usar uma implementação iterativa explícita com uma pilha para evitar esse problema.

Qual a utilidade de uma ordenação topológica?

Ela é usada para escalonar tarefas dependentes. Por exemplo, em um compilador, a ordenação topológica determina a ordem de compilação dos módulos, garantindo que dependências sejam processadas antes dos módulos que as utilizam.