Estrutura de Dados

Dado, tipo de dado (TD) e tipo abstrato de dado (TAD)

Antes de entrar em cada estrutura específica, vale fixar um vocabulário que aparece tanto em entrevista quanto na documentação de qualquer linguagem:

Definição: Dado

Um valor bruto, sem significado por si só — 10, "b", 2.6, true. Um dado só vira informação quando ganha contexto (2.6 sozinho não diz nada; "a taxa de juros é de 2.6% ao mês" diz).

Definição: Tipo de dado (TD)

A categoria em que um dado se enquadra — numérico, lógico, literal (texto/caractere). São os tipos primitivos de uma linguagem (em Java: int, double, boolean, char, ...; ver Java). Um TD é sempre amarrado à linguagem de programação que o disponibiliza.

Definição: Tipo abstrato de dado (TAD)

Uma estrutura construída a partir de tipos primitivos, que representa no mundo computacional (abstrato) algo que existe no mundo real (concreto) — uma fila de banco, uma pilha de pratos, uma lista de tarefas. Ao contrário de um TD, um TAD não é amarrado a nenhuma linguagem específica: o conceito de pilha é o mesmo em Java, Python ou C, só a sintaxe muda. Todo TAD é implementado internamente usando TDs (e outros TADs), mas quem usa um TAD não precisa saber desses detalhes internos — só das operações que ele expõe (esse é o sentido de "abstrato" aqui: abstrai os detalhes de implementação, sem perder a capacidade de representar o problema real).

Os TADs mais comuns costumam ser agrupados em quatro famílias, que servem de mapa para o resto desta página:

• Lineares — elementos numa sequência, um após o outro: Vetor/Matriz, Pilha, Fila, Lista.
• Hierárquicos/relacionais — elementos conectados por relações mais ricas que "um após o outro": Árvore, Grafo.
• Hash — acesso por chave em vez de posição: Mapa/Dicionário (Map, ver Collections Framework abaixo).
• Conjuntos — sem duplicados, sem ordem garantida: Set.

Ponteiro

Definição: Ponteiro

Uma forma de acessar um dado indiretamente pelo seu endereço de memória, em vez de pelo seu valor direto. Linguagens como C dão acesso explícito a esse endereço; linguagens mais modernas (Java, C#, Python) escondem esse mecanismo atrás de referências — a variável de um objeto guarda, por trás dos panos, um endereço de memória, mas a linguagem não deixa o programador manipular esse endereço diretamente (ver Referência, não valor). O ganho de esconder o ponteiro é segurança (menos classe de erro por acesso indevido a memória); o custo é uma camada a mais de abstração entre o código e o que a máquina realmente faz.

Memória: heap e stack

Dois tipos de memória do computador importam para quem programa: a memória principal (RAM — acesso rápido, dados voláteis, perdidos ao desligar) e a memória secundária (disco — acesso mais lento, dados duráveis). É dentro da RAM que vivem duas regiões que todo software usa constantemente: heap e stack.

Definição: Heap

Região de memória onde vivem os objetos criados dinamicamente (em Java, tudo que é criado com new) e as variáveis de escopo global. Múltiplos programas (e, dentro de um mesmo programa, múltiplas stacks) compartilham o mesmo heap, cada um com sua própria área dentro dele.

Definição: Stack (pilha de execução)

Região de memória que guarda o controle de chamadas de função/método: cada chamada empilha um novo quadro com suas variáveis locais, o endereço de retorno e os parâmetros recebidos — removido assim que aquela função/método termina. Diferente do heap, o espaço que a stack ocupa é prioritariamente alocado de forma estática (decidido de antemão), enquanto o heap é alocado dinamicamente (sob demanda, conforme o programa roda). Ver a aplicação concreta desse conceito na JVM em Referência, não valor (variável de objeto na stack guardando uma referência para o objeto no heap).

Array

Um array é a estrutura mais básica para guardar uma coleção de valores do mesmo tipo, em posições sequenciais e de tamanho fixo — definido no momento da criação e que não muda depois.

Produto[] produtos = new Produto[10]; // array de 10 posições, todas nulas no início
produtos[0] = produto;                // acesso por índice, começando em 0

Pontos que valem a pena ter na ponta da língua:

• Índices vão de 0 até tamanho - 1. Um array de 10 posições vai de produtos[0] a produtos[9] — tentar acessar produtos[10] estoura o índice.
• Tamanho fixo é a maior limitação prática: se o array já está cheio, não existe "adicionar mais uma posição" — seria preciso criar um array novo, maior, e copiar tudo. É essa limitação que leva a maioria dos códigos Java a preferir as classes de Collections (List, Map, ...) no dia a dia, que crescem dinamicamente por trás dos panos.
• Um array é, ele mesmo, um objeto — tem um atributo length (não é método, não leva ()) com o tamanho total.

for (Produto produto : produtos) { // enhanced-for (Java 5): sem índice, sem length
    if (produto != null) {
        System.out.println(produto.getValor());
    }
}

O enhanced-for (for (Tipo item : colecao)) evita ter que controlar índice e condição manualmente — e, com isso, evita também a classe de bug mais comum em arrays: estourar o índice por engano (ArrayIndexOutOfBoundsException, ver Boas Práticas).

Alguns detalhes de sintaxe e comportamento que valem a pena conhecer:

• Os colchetes podem vir logo após o tipo ou logo após o nome da variável — as duas formas são equivalentes: int[] x; e int x[];.
• O atalho de literal ({1, 2, 5, 7, 5}) só funciona na mesma linha da declaração — se a declaração e a atribuição estiverem em linhas separadas, é obrigatório o new:

  int[] numbers = {1, 2, 5, 7, 5};      // ok
  int[] numbers2;
  numbers2 = {1, 2, 5, 7, 5};            // erro de compilação — falta o new
  numbers2 = new int[]{1, 2, 5, 7, 5};   // ok
  

• Criar um array com tamanho negativo compila normalmente — o erro só aparece em tempo de execução, como NegativeArraySizeException.
• Um array de tipos não primitivos (de referências) começa com todas as posições null — acessar um membro de uma posição não preenchida lança NullPointerException, não ArrayIndexOutOfBoundsException (o índice existe, o objeto naquela posição que não existe ainda).

Definição: Por que acesso por índice é O(1)

Um array ocupa um bloco contíguo de memória — todas as posições uma logo depois da outra. Isso permite calcular o endereço exato de qualquer posição direto, sem percorrer as anteriores: endereço_base + tamanho_do_tipo × índice. Para um int (4 bytes) começando no endereço 1000, o elemento de índice 3 está em 1000 + 4 × 3 = 1012 — o acesso é O(1) (tempo constante, não depende do tamanho do array) justamente porque é uma conta, não uma busca elemento a elemento (isso é o que muda numa lista ligada, ver Lista encadeada mais abaixo, onde o acesso por posição é O(n)).

Definição: Casting de arrays

Arrays de tipos primitivos não aceitam casting entre si, mesmo entre tipos primitivos compatíveis (int[] não vira long[] via casting). Já arrays de referências seguem o polimorfismo do tipo que guardam: um String[] pode ser atribuído a uma variável Object[] sem casting (toda classe herda de Object), mas o caminho contrário exige casting explícito — e, se o array não for realmente daquele tipo em tempo de execução, lança ClassCastException:

Object[] values = new Object[2];
values[0] = "Certification";
String[] vals = (String[]) values; // ClassCastException — não é um array de String

Array multidimensional

Java não tem "array 2D" como um conceito à parte — um array multidimensional é, na prática, um array de arrays (e um array de arrays de arrays, para 3 dimensões, e assim por diante):

int[][] table = new int[10][15]; // 10 arrays, cada um com 15 posições
table[0][1] = 5;                  // linha 0, coluna 1

É possível inicializar só a primeira dimensão e deixar as demais para depois:

int[][] cube = new int[10][][]; // 10 posições, cada uma ainda null
cube[0] = new int[5][];           // preenchendo a primeira só quando precisar

Ou inicializar diretamente com valores conhecidos, aninhando chaves:

int[][] test = new int[][]{{1, 2, 3}, {3, 2, 1}, {1, 1, 1}};

Definição: Array não retangular (jagged array)

Como um array multidimensional é só um array de arrays, cada "linha" pode ter um tamanho diferente das outras — não existe obrigação de ser "quadrado" ou retangular:

int[][] weird = new int[2][];
weird[0] = new int[20];
weird[1] = new int[10];
// weird[0].length == 20, weird[1].length == 10 — tamanhos diferentes, sem erro

Pilha (Stack)

Uma pilha organiza elementos de forma que só é possível inserir e remover por um único ponto, o topo — como uma pilha de pratos: o último prato colocado é o primeiro a ser retirado.

Definição: LIFO

Last in, first out — "o último a entrar é o primeiro a sair". É o comportamento de uma pilha, e o jeito mais comum de se referir a ela (o oposto, FIFO, descreve a fila — ver abaixo).

As operações centrais de uma pilha:

Operação	Faz
push(x)	empilha x no topo
pop()	desempilha e devolve o elemento do topo
top() / peek()	devolve o elemento do topo, sem removê-lo
size()	quantidade de elementos
isEmpty()	true se a pilha está vazia

Deque<String> pilha = new ArrayDeque<>(); // Java não tem uma classe "Stack" moderna dedicada — Deque é a recomendada
pilha.push("A");
pilha.push("B");
pilha.peek(); // "B", sem remover
pilha.pop();  // "B", remove
pilha.pop();  // "A", remove

Definição: por que Deque, e não a classe Stack

Java tem uma classe java.util.Stack histórica (desde o Java 1.0), mas a própria documentação oficial recomenda evitá-la — ela estende Vector (uma lista antiga, sincronizada, mais lenta) por razões históricas, não porque faça sentido uma pilha "ser" uma lista. A alternativa recomendada é usar uma Deque (double-ended queue, fila de duas pontas) só pelo lado de pilha, com push/pop/peek — a implementação mais comum é ArrayDeque.

Onde uma pilha aparece na prática

• Pilha de chamadas de método (call stack) — cada método chamado empilha um quadro; quando retorna, é desempilhado. Ver Memória: heap e stack.
• Desfazer (ctrl+z) — cada ação editável é empilhada; desfazer é um pop.
• Balanceamento de expressões — verificar se (, [, { fecham corretamente numa expressão como A + (B * [C - D]) - {E / F}: a cada abertura, empilha o símbolo; a cada fechamento, desempilha e confere se é o par esperado. Sobrou algo na pilha no final, ou tentou desempilhar uma pilha vazia? A expressão está malformada.
• Recursão — toda chamada recursiva usa a pilha de chamadas por baixo dos panos (ver Recursividade mais abaixo); é por isso que recursão sem caso de parada estoura StackOverflowError.

Definição: Notação infixada, prefixada e pós-fixada

Três formas equivalentes de escrever uma expressão aritmética, segundo a posição do operador em relação aos operandos: infixada é a usual (1 + 2, operador entre os operandos); prefixada vem antes (+ 1 2); pós-fixada (também chamada notação polonesa reversa) vem depois (1 2 +). Calculadoras e compiladores usam pilhas para converter entre essas notações ou para avaliar uma expressão pós-fixada diretamente (empilhando operandos, e a cada operador desempilhando os dois últimos para aplicar a conta e empilhar o resultado).

Fila (Queue)

Uma fila organiza elementos de forma que a inserção e a remoção acontecem em pontos opostos — como uma fila de banco: quem chega primeiro, entra no fim da fila; quem sai primeiro, é quem está na frente.

Definição: FIFO

First in, first out — "o primeiro a entrar é o primeiro a sair". É o comportamento de uma fila comum.

Operação	Faz
enqueue(x) / offer(x)	insere x no fim da fila
dequeue() / poll()	remove e devolve o elemento da frente
peek()	devolve o elemento da frente, sem removê-lo

Queue<String> fila = new LinkedList<>(); // LinkedList implementa a interface Queue
fila.offer("A");
fila.offer("B");
fila.peek(); // "A" — o primeiro a entrar
fila.poll(); // "A", remove

Onde uma fila aparece na prática: fila de processamento (tarefas executadas na ordem em que chegaram), buffers de rede (pacotes chegando mais rápido do que são processados), percorrer uma árvore/grafo em largura (ver Árvore e Grafo abaixo).

Definição: variações de fila

Fila de prioridade (priority queue) — a ordem de saída não é por chegada, e sim por uma prioridade definida (o próximo a sair é sempre o de maior/menor prioridade, não necessariamente o mais antigo). Deque (double-ended queue) — permite inserir e remover nas duas pontas, servindo tanto de pilha quanto de fila conforme o lado usado.

Lista encadeada

Diferente de pilha e fila, uma lista não impõe nenhum comportamento de acesso — não existe "topo" nem "frente", os elementos só estão ligados linearmente, um apontando para o próximo. Cada elemento (chamado de nó) guarda dois pedaços de informação: o valor e uma referência para o próximo nó.

class No<T> {
    T valor;
    No<T> proximo;
}

Definição: Simplesmente x duplamente encadeada

Numa lista simplesmente encadeada, cada nó só conhece o próximo — navegar só é possível num sentido, do início para o fim. Numa lista duplamente encadeada, cada nó guarda referência para o próximo e para o anterior — navega nos dois sentidos, e permite começar a busca pela ponta mais próxima do índice desejado (é assim que LinkedList do Java funciona por trás dos panos).

Definição: Lista circular

Variação em que o último nó, em vez de apontar para null, aponta de volta para o primeiro — não existe mais um "fim" absoluto, útil para percorrer indefinidamente em ciclo (ex.: alternar entre jogadores num jogo de tabuleiro).

O que muda, na prática, entre um array/ArrayList e uma lista encadeada é onde cada operação é rápida:

Operação	Array / ArrayList	Lista encadeada
Acessar por índice (get(i))	O(1) — é uma conta de endereço (ver definição mais acima nesta página)	O(n) — precisa navegar nó a nó a partir de uma ponta
Inserir/remover no início	O(n) — precisa deslocar todos os elementos seguintes	O(1) — só reaponta algumas referências
Inserir/remover no fim	O(1) amortizado (ArrayList), O(n) se precisar redimensionar	O(1) se a lista guarda referência para o último nó
Inserir/remover no meio	O(n) (desloca o restante)	O(n) para achar a posição, O(1) para religar os ponteiros depois de achada

Definição: Por que escolher um sobre o outro

Se o uso predominante é acessar por posição/percorrer (ex.: iterar e ler), um array/ArrayList é mais rápido — acesso contíguo em memória também é mais amigável ao cache do processador. Se o uso predominante é inserir/remover nas pontas (ex.: implementar uma fila ou uma pilha), uma lista encadeada evita o custo de deslocar elementos. Ver ArrayList x LinkedList abaixo, na implementação concreta em Java.

Collections Framework

Um array resolve pouco: tamanho fixo, sem método de busca/remoção pronto, sem padronização entre diferentes estruturas. O Collections Framework (desde o Java 1.2) resolve isso com uma família de interfaces e implementações prontas para guardar e manipular grupos de objetos — a diferença entre as estruturas está em como os dados são organizados e em quais operações são rápidas em cada uma.

graph TD
    C["«interface» Collection"] --> L["«interface» List"]
    C --> S["«interface» Set"]
    L --> AL[ArrayList]
    L --> LL[LinkedList]
    S --> HS[HashSet]
    S --> TS[TreeSet]

Regra geral de bom senso: programe voltado para a interface (List, Set, Map), não para a implementação concreta (ArrayList, HashSet, HashMap). Declarar variáveis, atributos e retornos de método como a interface deixa o código livre para trocar a implementação depois (ex.: de ArrayList para LinkedList) sem quebrar nada que usa esse código — só o new muda.

List<Produto> produtos = new ArrayList<>(); // não List<Produto> = new List<Produto>()

Definição: Generics

Recurso (desde o Java 5) que permite parametrizar o tipo que uma estrutura vai guardar — List<Produto> só aceita Produto. Sem generics, uma lista trabalha com Object genérico, obrigando casting manual (e o risco de ClassCastException) toda vez que um valor é recuperado. Desde o Java 7, o diamond operator evita repetir o tipo genérico dos dois lados: List<Produto> produtos = new ArrayList<>();.

List

Uma List guarda elementos em ordem de inserção, permite duplicados, e acessa por índice — é o substituto direto e mais flexível de um array.

• ArrayList — implementação mais comum; mantém um array internamente (encapsulado), mas cresce dinamicamente. Mais rápida para percorrer/ler.
• LinkedList — lista duplamente encadeada (cada elemento aponta para o próximo e para o anterior); mais rápida para inserir/remover elementos nas pontas, mas O(n) para acessar por índice no meio da lista — ver a comparação completa de complexidade acima.

List<Produto> produtos = new ArrayList<>();
produtos.add(produto);
produtos.remove(produto);      // remove pelo valor
produtos.contains(produto);    // busca

Principais métodos de List/ArrayList, além de add/remove/contains:

Método	Faz
get(indice)	elemento numa posição
set(indice, valor)	substitui o elemento numa posição, devolve o antigo
add(indice, valor)	insere numa posição específica (sobrecarga de add(valor))
remove(indice)	remove pela posição — cuidado: remove(int) remove por índice, remove(Object) remove pelo valor
size()	quantidade de elementos
indexOf(valor) / lastIndexOf(valor)	posição da primeira/última ocorrência (-1 se não achar)
toArray()	converte para um array
addAll(outraColecao)	adiciona todos os elementos de outra coleção

Definição: remove(int) x remove(Object)

Em uma ArrayList<Integer>, list.remove(1) é ambíguo à primeira vista: remove o elemento na posição 1, ou remove o valor 1? A regra do Java: se o argumento é um int primitivo, chama a sobrecarga por índice; para remover pelo valor 1 (um Integer), é preciso fazer autoboxing explícito: list.remove(Integer.valueOf(1)). Com ArrayList<String> essa ambiguidade não existe (String nunca é confundida com índice).

toArray() sempre devolve um array novo: se você passar um array como argumento (toArray(new String[0])), ele é usado como está se for grande o suficiente, ou um outro é criado do mesmo tipo, caso contrário.

Definição: Cuidado ao sobrescrever equals para comparar em coleções

contains, remove e indexOf de uma coleção usam equals para decidir se um elemento "é aquele" — a implementação padrão (herdada de Object) compara só referência. Sobrescrever equals recebendo um tipo específico em vez de Object (ver Orientação a Objetos) faz um overload, não um override — a coleção continua chamando o equals(Object) original, e o comportamento de busca não muda como esperado.

Iterator

A interface Iterator permite percorrer qualquer coleção de forma padronizada, sem depender de índice (útil especialmente para coleções que não têm, como Set):

Iterator<String> iterator = strings.iterator();
while (iterator.hasNext()) {
    String current = iterator.next(); // avança e devolve o elemento
    System.out.println(current);
}

• hasNext() — true se ainda há elemento a percorrer.
• next() — devolve o elemento atual e avança para o próximo.
• remove() — remove da coleção o último elemento devolvido por next().

O enhanced-for usa Iterator por baixo dos panos — por isso funciona igual para qualquer Collection (List, Set, ...), não só para List.

Set

Um Set é uma coleção que não permite duplicados e, diferente de List, não garante ordem de inserção — modela o conceito matemático de conjunto.

• HashSet — implementação mais comum; usa uma tabela de dispersão baseada em hashCode/equals (ver Java) para decidir rapidamente se um elemento já existe — é isso que torna contains num HashSet O(1) em média, muito mais rápido que num List grande (que precisa comparar item a item, O(n)). Não garante nenhuma ordem de iteração.
• LinkedHashSet — como HashSet, mas mantém a ordem de inserção ao iterar (custo extra de manter uma lista encadeada por baixo, junto com a tabela de dispersão).
• TreeSet — mantém os elementos ordenados (usa uma árvore binária de busca por baixo dos panos), ao custo de inserção/busca O(log n) em vez de O(1).

Set<String> cupons = new HashSet<>();
cupons.add("CUP74");
cupons.add("CUP74"); // ignorado — já existe
cupons.size();        // 1

Map

Um Map associa chave → valor (um dicionário) — útil sempre que a busca precisa ser feita por uma chave única, em vez de por posição.

Map<String, Double> cupons = new HashMap<>();
cupons.put("CUP74", 10.0);
Double desconto = cupons.get("CUP74");        // 10.0
cupons.containsKey("CUP74");                   // true

Assim como Set, HashMap (a implementação mais comum) depende de hashCode/equals da chave — via tabela de dispersão — para localizar valores rapidamente. LinkedHashMap e TreeMap seguem o mesmo padrão de LinkedHashSet e TreeSet: ordem de inserção preservada, ou chaves ordenadas, respectivamente.

Definição: HashMap x Hashtable

Hashtable é a classe original de Java para mapa chave-valor (desde a versão 1.0) — hoje considerada legada. HashMap (desde o Java 1.2, parte do Collections Framework) é a substituta recomendada: mesma ideia, porém sem a sincronização desnecessária que torna Hashtable mais lenta na maioria dos usos (single-thread).

Ordenando com Comparable

Collections.sort(lista) ordena qualquer List — mas o método sort precisa saber como comparar os elementos entre si. Isso é feito implementando a interface Comparable<T> e seu método compareTo:

public abstract class Livro implements Produto, Comparable<Produto> {
    @Override
    public int compareTo(Produto outro) {
        if (this.getValor() < outro.getValor()) return -1;
        if (this.getValor() > outro.getValor()) return 1;
        return 0;
    }
}

Definição: Contrato de compareTo

Retorna um número negativo se o objeto atual (this) deve vir antes do argumento na ordenação, positivo se deve vir depois, e 0 se são equivalentes para fins de ordenação. Uma forma mais compacta e comum de escrever a mesma lógica para números: return (int) (this.getValor() - outro.getValor()); (ou Integer.compare(a, b) para tipos inteiros).

Árvore

Os TADs vistos até aqui (vetor, pilha, fila, lista) são todos lineares — um elemento após o outro. Uma árvore é o primeiro TAD hierárquico: os elementos têm uma relação de subordinação entre si, como um organograma de empresa ou uma árvore genealógica.

Definição: Árvore

Estrutura de dados onde os elementos (nós) possuem um vínculo do tipo pai e filho, criando uma relação hierárquica. Cada nó pode ter vários filhos, mas um único pai (exceto a raiz, que não tem pai nenhum).

Vocabulário essencial

• Raiz (root) — o nó inicial, único sem pai.
• Nó (node) — qualquer elemento da árvore.
• Nó interno — tem pelo menos um filho.
• Nó folha (leaf) — não tem filho nenhum (fim de um "ramo").
• Ancestral / descendente — nós que vêm antes/depois de um nó, no caminho até a raiz.
• Profundidade (depth) — a distância, em nós, da raiz até a folha mais distante.
• Subárvore — qualquer nó, junto com todos os seus descendentes, forma uma árvore menor dentro da árvore maior — é por isso que algoritmos em árvore costumam ser recursivos (ver Recursividade): resolver para uma subárvore é o mesmo problema que resolver para a árvore inteira, só que menor.

Árvore binária e árvore binária de busca

Definição: Árvore binária

Árvore em que todo nó tem, no máximo, 2 filhos — comumente chamados de filho à esquerda e filho à direita.

Definição: Árvore binária de busca (BST)

Uma árvore binária ordenada: para todo nó, os valores da subárvore à esquerda são menores que o nó, e os valores da subárvore à direita são maiores. Essa regra vale recursivamente em cada subárvore, não só no nível raiz — é o que torna a busca por um valor rápida: a cada nó visitado, dá para descartar metade dos nós restantes (esquerda ou direita), igual a uma busca binária num array ordenado.

class No {
    int valor;
    No esquerda, direita;
}

Percorrendo uma árvore: pré-ordem, em-ordem, pós-ordem

Três formas clássicas de visitar todos os nós de uma árvore binária, todas recursivas, diferindo só em quando a raiz é visitada em relação às suas subárvores:

Percurso	Ordem	Uso típico
Pré-ordem (pre-order)	raiz → esquerda → direita	copiar/serializar a árvore (a raiz vem primeiro, então dá para reconstruir a estrutura lendo em sequência)
Em-ordem (in-order)	esquerda → raiz → direita	numa BST, visita os valores em ordem crescente — é a forma de "extrair" uma lista ordenada de uma BST
Pós-ordem (post-order)	esquerda → direita → raiz	apagar a árvore com segurança (apaga os filhos antes do pai)

AVL: mantendo a árvore balanceada

Uma BST comum pode ficar desbalanceada — no pior caso (inserir valores já ordenados), ela degenera numa lista encadeada, e a busca deixa de ser rápida (O(log n)) e vira O(n).

Definição: Árvore AVL

Uma árvore binária de busca que se rebalanceia sozinha: a cada inserção ou remoção, se a diferença de profundidade entre a subárvore esquerda e a direita de algum nó passar de 1, a árvore aplica uma rotação (reorganização local dos nós) para restaurar o balanceamento. O resultado é que buscas, inserções e remoções continuam O(log n) mesmo no pior caso — a árvore nunca degenera numa lista.

Definição: AVL x árvore rubro-negra — qual usar

As duas são BSTs autobalanceadas, mas com um trade-off diferente: a AVL fica "mais balanceada" (mais rígida), o que deixa a busca mais rápida, mas como qualquer inserção/remoção tende a disparar mais rotações, ela é mais cara para escrever. A árvore rubro-negra aceita ficar "quase balanceada", fazendo menos rotações (escrita mais rápida), ao custo de buscas um pouco mais lentas. Regra prática: dados que mudam pouco e são lidos muito → AVL; dados com muita inserção/remoção → rubro-negra.

Vale notar também a escolha entre árvore binária e árvore N-ária (nó pode ter mais de 2 filhos): binárias tendem a ficar mais profundas com muitos elementos (mais chamadas recursivas, mais uso de pilha de execução); N-árias ficam mais "largas" e menos profundas, ao custo de mais memória por nó (espaço para mais ponteiros de filho).

Existem dezenas de variações especializadas além da BST/AVL — árvores B/B+ (usadas internamente por índices de banco de dados), árvore heap (ver Heap abaixo), árvore Trie (usada para autocompletar e dicionários) — cada uma otimizada para um problema específico; não existe uma única "melhor árvore".

Grafo

Uma árvore é hierárquica (todo nó tem só um pai); um grafo relaxa até essa regra — qualquer elemento pode se relacionar livremente com qualquer outro. É o TAD mais genérico e mais complexo, mas também o mais comum na prática: uma rede social, o mapa de rotas do Google Maps e a malha de conexões de uma rede de computadores são todos grafos.

Definição: Grafo

Estrutura de dados onde os elementos (vértices) podem estar livremente relacionados entre si, através de arestas. Diferente de árvore, não existe conceito de raiz nem de direção obrigatória "de cima para baixo".

Vocabulário essencial

• Vértice (nó) — o elemento do grafo (equivalente ao nó de uma árvore).
• Aresta — a conexão entre dois vértices; pode ter peso (um custo/distância associado) e pode ser um laço (loop — uma aresta que liga um vértice a ele mesmo).
• Vértices adjacentes — vértices ligados diretamente por uma aresta.
• Grau de um vértice — a quantidade de arestas que ele possui.
• Caminho — a sequência de arestas percorridas para ir de um vértice a outro.

Tipos de grafo

Tipo	Significa
Direcionado (dígrafo)	as arestas têm sentido — (A, B) é diferente de (B, A)
Não direcionado	as arestas não têm sentido — ir de A para B é o mesmo que de B para A
Ponderado	as arestas têm peso (custo, distância, ...)
Cíclico / acíclico	existe (ou não existe) algum caminho que sai de um vértice e volta a ele mesmo
Conexo	existe caminho de qualquer vértice até qualquer outro
Completo	todo vértice está conectado a todos os outros

Definição: Árvore é um tipo particular de grafo

Uma árvore é, tecnicamente, um grafo simples, acíclico e conexo — a hierarquia (raiz, pai/filho) é uma restrição adicional que o grafo genérico não impõe.

Representações

• Matriz de adjacência — uma tabela V × V (V = quantidade de vértices); a posição [A][B] marca 1 se existe aresta de A para B, 0 caso contrário. Simples de implementar e de verificar "existe aresta entre X e Y" (O(1)), mas desperdiça memória quando o grafo tem poucas arestas em relação à quantidade de vértices (grafo esparso).
• Lista de adjacência — cada vértice guarda uma lista só dos vértices com quem tem aresta. Mais econômica em memória para grafos esparsos (a grande maioria dos casos reais), ao custo de "existe aresta entre X e Y" não ser mais O(1) (precisa percorrer a lista daquele vértice).

Percorrendo um grafo: busca em profundidade x em largura

As mesmas duas estratégias de busca se aplicam tanto a árvores quanto a grafos:

Definição: Busca em profundidade (DFS — depth-first search)

A partir de um vértice inicial, avança o mais fundo possível por um caminho antes de retroceder e tentar outro. Implementação típica usa pilha (explícita, ou a pilha de execução via recursão). Mais simples de implementar, mas pode explorar caminhos bem mais longos que o necessário antes de achar o destino.

Definição: Busca em largura (BFS — breadth-first search)

A partir de um vértice inicial, visita todos os vizinhos diretos antes de avançar para os vizinhos dos vizinhos — expande "em camadas". Implementação típica usa fila. Mais custosa de implementar, mas encontra o caminho mais curto (em número de arestas) primeiro, quando o grafo não é ponderado.

Em ambos os casos, cada vértice visitado é marcado como processado, para não entrar em loop (visitar o mesmo vértice repetidamente através de um ciclo).

Problemas e algoritmos clássicos

• Caminho mínimo — menor custo (soma de pesos) para ir de um vértice a outro; é o problema que o Google Maps resolve a cada rota traçada. O algoritmo clássico é o de Dijkstra: a partir do vértice de origem, sempre avança pela aresta de menor peso ainda não avaliada, descartando os caminhos já demonstrados como piores.
• Caixeiro-viajante (travelling salesman) — encontrar a rota mais barata que visita um conjunto de vértices exatamente uma vez e retorna à origem (aplicação direta em logística de entregas). É um problema NP-difícil — não existe algoritmo eficiente conhecido para resolvê-lo exatamente em grafos grandes; soluções práticas usam heurísticas como o vizinho mais próximo (sempre segue para o vértice não visitado mais barato), que é rápido mas não garante a melhor resposta possível ("processamento guloso" — bom o suficiente na maioria dos casos, sem garantia de ótimo).
• Coloração de grafos — colorir vértices (ou regiões de um mapa) de forma que vértices adjacentes nunca tenham a mesma cor, usando o menor número de cores possível (o teorema das quatro cores prova que 4 cores sempre bastam para qualquer mapa planar).

Onde um grafo aparece na prática

Redes sociais (pessoas = vértices, conexões = arestas), mapas e rotas, topologia de redes de computadores, e máquinas de estado (cada estado é um vértice, cada transição possível é uma aresta direcionada — útil para modelar fluxos como o de um pagamento passando por "verificação → autorizado/não autorizado → entregue").

Tabela de dispersão (Hashtable)

Vetor/lista/árvore resolvem bem o acesso rápido em cenários diferentes, mas todos têm um custo em algum caso: array tem tamanho fixo, lista é O(n) para achar um elemento no meio, árvore ordenada pode ficar profunda demais. A tabela de dispersão ataca isso de outro ângulo: em vez de guardar o elemento numa posição relacionada à ordem de inserção, ela calcula a posição a partir do próprio valor (ou de uma chave associada a ele).

Definição: Tabela de dispersão (hashtable) e função hash

Estrutura que usa uma função hash — que recebe um valor (ou chave) e devolve um número — para calcular diretamente onde guardar/buscar aquele elemento, sem precisar navegar pelos outros. O resultado é acesso, inserção e remoção em média O(1), independente de quantos elementos já existem na estrutura. É a base de implementação de HashSet, HashMap e Set/Map em praticamente toda linguagem.

Definição: Colisão de hash

Quando a função hash calcula o mesmo endereço para dois valores diferentes. Colisões são inevitáveis (a quantidade de valores possíveis é sempre maior que a quantidade de endereços disponíveis) — o que muda entre implementações é a estratégia de tratamento (ex.: guardar uma lista de elementos em cada endereço, em vez de um só). Isso não é um detalhe de implementação irrelevante: é o motivo pelo qual hashCode/equals bem implementados importam tanto para o desempenho de um HashSet/HashMap (ver Orientação a Objetos) — um hashCode que gera colisão para muitos valores diferentes degrada o O(1) esperado de volta para O(n).

Heap

Heap (também chamada binary heap) é uma árvore binária com uma regra extra de ordenação, focada em um único objetivo: achar rapidamente o maior (ou o menor) elemento do conjunto.

Definição: Propriedade heap

Toda árvore binária que respeita: max-heap — todo nó pai é maior ou igual aos seus filhos; ou min-heap — todo nó pai é menor ou igual aos seus filhos. Diferente de uma BST, não existe regra de esquerda-menor/direita-maior — só importa a relação vertical (pai x filho).

Como o maior (numa max-heap) ou o menor (numa min-heap) elemento está sempre na raiz, consultá-lo é O(1). Remover a raiz exige reorganizar a árvore (movendo outro nó para o lugar dela e "afundando-o" até restaurar a propriedade heap) — é assim que uma heap implementa uma fila de prioridade de forma eficiente: o próximo elemento a sair (maior ou menor prioridade) já está sempre no topo, pronto para ser consultado.

Recursividade

Recursividade não é um TAD, mas é a técnica que torna praticável trabalhar com árvores e grafos — ambos têm uma natureza que se repete em escala menor (uma subárvore é uma árvore; navegar a partir de um vizinho é o mesmo problema de navegar a partir do vértice original), o que se encaixa naturalmente numa função que chama a si mesma.

Definição: Recursividade

Quando uma função (ou método) chama a si mesma, repetidamente, até atingir uma condição de parada. Toda solução recursiva tem três partes obrigatórias:

1. Teste de parada (caso base) — a condição que encerra a recursão. Sem essa parte, a função chama a si mesma indefinidamente.
2. Operação a ser realizada — o trabalho feito nesta chamada específica.
3. Chamada recursiva — a função chamando a si mesma para uma versão menor ou mais simples do problema original.

int fatorial(int n) {
    if (n <= 1) return 1;       // 1. caso base
    return n * fatorial(n - 1); // 2. e 3. operação + chamada recursiva
}

Definição: Por que recursão sem caso de parada estoura a pilha

Cada chamada recursiva empilha um novo quadro na pilha de execução — e só é desempilhado quando aquela chamada específica retorna. Sem um caso de parada alcançável, as chamadas se empilham indefinidamente até a memória reservada para a pilha se esgotar, lançando StackOverflowError (Java) ou equivalente.

Qualquer solução recursiva também pode ser escrita de forma iterativa (com for/while) — a escolha entre as duas é sobre clareza, não sobre capacidade: alguns problemas (percorrer uma árvore, calcular Fibonacci, calcular um fatorial, dividir um problema em subproblemas menores — divide and conquer) ficam bem mais simples de ler e escrever de forma recursiva, ao custo de usar mais memória (uma chamada de pilha por nível) do que a versão equivalente com loop.