Estruturas de dados

Visão geral: formas para guardar informação

Uma estrutura de dados tem duas partes: um jeito de guardar os itens e um pequeno conjunto de operações para usá-los: inserir, remover, buscar e, às vezes, acessar por posição. Toda escolha tem um preço. Uma estante deixa você pegar o 5º livro na hora, mas colocar um livro no meio obriga a empurrar todos os outros. Uma corrente de clipes deixa você colocar um clipe em qualquer lugar, mas para chegar ao 5º você precisa contar desde o início.

Palavras que você vai encontrar

• Nó: um pedaço de uma estrutura que guarda um valor e, em geral, os endereços de outros nós.
• [[Ponteiro|um número que diz onde algo está na memória, como o endereço de uma casa]]: o jeito como um nó aponta para outro nó. Um ponteiro que não aponta para nada se chama nulo (null).
• Chave: a parte de um item que usamos para encontrá-lo, como o nome numa lista de contatos.
• Organização sequencial: vizinhos na memória são vizinhos na estrutura. Organização encadeada: a ordem é dada por ponteiros.
• Custo: quantos passos uma operação leva quando o número de itens n cresce. O(1) quer dizer 'sempre mais ou menos igual', O(log n) quer dizer 'cresce bem devagar' e O(n) quer dizer 'cresce junto com n'.

Tipos abstratos de dados e encapsulamento

Quando você aperta o botão do controle remoto da TV, não precisa saber a eletrônica lá dentro. Só precisa saber o que cada botão faz. Um tipo abstrato de dados (TAD) é a mesma ideia para programas: ele diz o que você pode fazer com os dados (um conjunto de valores e as operações sobre eles), mas não como os dados são guardados. A parte escondida é a representação.

Interface e implementação

A interface é a lista de operações (seus nomes, seus parâmetros e o que significam). A implementação é o código e a organização da memória por trás delas. O grande ganho é a independência de representação: enquanto a interface continuar igual, você pode mudar a representação à vontade. Se uma data era guardada num vetor de três inteiros e você troca por uma struct com três campos, os programas que só chamam as funções do TAD não precisam mudar. Só quebra o código que entrava por dentro, de fora do TAD.

Isso também permite deixar uma estrutura mais rápida sem incomodar ninguém. Se uma lista procurava a primeira posição livre a cada add e agora guarda um contador privado de quantos elementos tem, quem a usa chama os mesmos métodos e só percebe que ficou mais rápida.

Encapsulamento em C

Em C, um TAD vira um módulo de dois arquivos. O cabeçalho (.h) publica um tipo opaco (um nome sem campos visíveis) e os protótipos das funções. O arquivo .c guarda a struct de verdade. Quem usa só segura ponteiros e não consegue ler os campos, porque o compilador recusa. Assim o encapsulamento é garantido pelo compilador, não pela boa vontade.

/* stack.h */
typedef struct Stack Stack;   /* opaco: nenhum campo visível */
Stack *stack_new(void);
int    stack_push(Stack *s, int x);
int    stack_pop(Stack *s, int *out);

/* stack.c */
struct Stack { int data[100]; int top; };  /* escondido */

Erros e invariantes

• Erros: o que pop deve fazer numa pilha vazia? Um TAD reutilizável só detecta o problema e devolve um indicador de sucesso ou falha. O programa que o usa decide a reação: mostrar uma mensagem, perguntar de novo ou falhar num teste. Assim o mesmo módulo serve a um programa de terminal, a uma janela ou a um teste automático. Imprimir e encerrar dentro do TAD o tornaria inútil nos outros casos.
• Invariantes: uma regra que deve ser sempre verdadeira, por exemplo 'um Conjunto não tem elementos repetidos'. Ela continua verdadeira porque toda mudança passa pelas operações do TAD.
• Exposição da representação: se uma função entrega um ponteiro para o vetor interno 'para evitar cópia', quem usa pode escrever ali e quebrar o invariante. A cura é devolver uma cópia, uma visão somente de leitura ou um iterador (um ajudante que entrega os elementos um de cada vez).

Vetores e listas: sequencial, encadeada, duplamente encadeada, circular

Uma lista é uma sequência de itens em que a ordem importa. Há duas formas principais de construí-la. Numa lista sequencial (um vetor) os itens ficam lado a lado na memória, como as cadeiras de uma fileira do cinema. Numa lista encadeada cada item mora num nó junto com o endereço do próximo nó, como numa caça ao tesouro em que cada pista diz onde está a próxima.

vetor:    [ 7 ][ 3 ][ 9 ][ 4 ]      índice 0 1 2 3

encadeada: início -> [7|*]-> [3|*]-> [9|*]-> [4|nulo]

Acesso e inserção

Num vetor, o endereço do elemento i é o início mais i vezes o tamanho de um elemento, então ler a posição i custa O(1). Numa lista encadeada cada nó só conhece o próximo, então para chegar à posição i é preciso andar i passos: O(n). Por outro lado, inserir no início de um vetor obriga todos os elementos a andar uma casa para abrir espaço (O(n)), enquanto inserir logo depois de um nó que você já tem numa lista encadeada só muda ponteiros (O(1)).

Tipos de listas encadeadas

• Simplesmente encadeada: cada nó tem o dado e next. O next do último nó é nulo, e um laço anda enquanto o ponteiro atual não for nulo.
• Duplamente encadeada: cada nó também tem prev. Custa mais um ponteiro por nó, mas de qualquer nó os dois vizinhos são alcançáveis em O(1), então dá para remover um nó conhecido e andar para trás.
• Circular: o último nó aponta para o primeiro, então não existe nulo. Para percorrê-la, guarde o nó inicial e pare quando encontrá-lo de novo. É boa para coisas atendidas em rodízio, como jogadores de um jogo.
• Sentinela: um nó extra sem dado do usuário que elimina casos especiais. Numa busca, você copia a chave procurada para a sentinela no fim, então o laço sempre termina e precisa de uma só comparação por passo em vez de duas. Continua linear.
• Nó cabeça (header): um primeiro nó de mentira. Remover um nó é fazer o antecessor apontar para o sucessor. O primeiro nó de verdade não tem antecessor, então sem nó cabeça ele é um caso especial. Com nó cabeça, todo nó de dados tem antecessor.

A ordem das linhas de ponteiro

Para inserir node depois de p, o endereço do antigo próximo nó existe só em p->next. Se você o sobrescreve primeiro, perde o resto da lista. Então é preciso primeiro ligar o novo nó ao resto e só depois fazer p apontar para o novo nó.

node->next = p->next;  /* 1: o novo nó guarda o resto da lista */
p->next    = node;     /* 2: só agora p aponta para o novo nó */

Organização versus alocação

São duas perguntas diferentes. Organização é como a ordem é representada: por posições vizinhas (sequencial) ou por ligações (encadeada). Alocação é quando a memória é reservada: toda de uma vez (estática) ou sob demanda (dinâmica). Uma lista guardada num vetor de tamanho fixo em que cada célula guarda o índice do sucessor é, portanto, encadeada (organização) e estática (alocação).

Um pool de nós simula malloc e free dentro de um vetor: os nós livres formam uma lista encadeada de índices (a lista de livres). getnode pega o nó da frente da lista de livres e freenode(i) coloca o nó i na frente. Ambos custam O(1) e o pool se comporta como uma pilha: o nó liberado por último é o primeiro a ser reutilizado.

Vetores dinâmicos e custo amortizado

Um vetor dinâmico cresce quando fica cheio: aloca um bloco com o dobro do tamanho e copia tudo. Um acréscimo pode custar O(n), mas dobrar o tamanho o torna raro, então o custo amortizado de acrescentar é O(1).

As cópias são 1 + 2 + 4 = 7. Cada realocação copia o dobro da anterior, mas acontece com metade da frequência, então o total é uma soma de potências de 2, sempre menor que o dobro do número de elementos. Por isso o custo médio por acréscimo fica constante.

Listas ordenadas e duas armadilhas clássicas

• Uma lista encadeada mantida ordenada por chave faz as buscas que falham pararem mais cedo (assim que você passa do lugar onde a chave estaria). Mas você continua andando nó a nó, então ela não vira logarítmica. A busca binária precisa de acesso direto por posição, que só o vetor tem.
• Remover enquanto percorre uma lista em vetor: depois de remove(i), o próximo elemento desliza para o índice i. Se o laço faz i++ em seguida, ele pula esse elemento. Para a lista [1, 5, 5, 2] e a tarefa 'remover todos os 5', o laço removeria o primeiro 5 e pularia o segundo. Corrija não incrementando depois de uma remoção, ou andando do fim para o início.
• Um cache LRU ('remover o menos usado recentemente') precisa de um mapa hash de chave para nó e de uma lista ordenada por uso. Cada acesso tira um nó do meio e o coloca na frente, e a remoção por falta de espaço tira o último nó. Ambos custam O(1) só se a lista for duplamente encadeada, porque o nó precisa conhecer os dois vizinhos para sair do seu lugar.

Pilhas

Uma pilha é uma pilha de pratos. Você coloca um prato novo em cima e também tira um do topo. Nunca puxa um prato do meio. Em computação: push coloca um elemento no topo e pop tira o do topo. O elemento removido é sempre o mais recente. Essa regra se chama LIFO: last in, first out (o último a entrar é o primeiro a sair).

   | 3 |  <- topo
   | 2 |
   | 1 |
   +---+

Implementando uma pilha

• Em vetor (estática): guarde um inteiro top com o índice do último elemento empilhado. Convenção: top == -1 quer dizer vazia e top == N - 1 quer dizer cheia, em que N é o tamanho do vetor. Teste 'cheia' antes de empilhar, para não escrever fora do vetor (overflow), e teste 'vazia' antes de desempilhar (underflow).
• Em lista simplesmente encadeada: o topo é o primeiro nó. push cria um nó que aponta para o antigo primeiro e move o ponteiro de início para ele. pop só avança o ponteiro de início. Nada é percorrido, então ambos custam O(1). Só fica cheia quando a memória acaba.

Onde aparecem as pilhas

• Chamadas de função: cada chamada empilha o endereço de retorno e as variáveis locais, e o retorno desempilha. Essa é a pilha de chamadas.
• Botões de desfazer e o botão de voltar de um navegador.
• Parênteses casados: empilhe cada abertura, e cada fechamento deve combinar com o topo.
• Inverter uma sequência: converter 13 para binário dividindo por 2 dá os bits do último para o primeiro (restos 1, 0, 1, 1 empilhados nessa ordem). Desempilhar escreve o número 1101 na ordem certa.
• Avaliar expressões escritas em notação pós-fixa.

Notação pós-fixa (polonesa reversa)

Na notação pós-fixa o operador vem depois dos operandos, então não precisa de parênteses nem de regras de precedência. Leia da esquerda para a direita: se vir um número, empilhe. Se vir um operador, desempilhe dois números, calcule e empilhe o resultado. O primeiro número desempilhado é o operando da direita, o que importa na subtração e na divisão.

lê 2  -> pilha: 2
lê 3  -> pilha: 2 3
lê +  -> desempilha 3, desempilha 2, empilha 2+3 -> pilha: 5
lê 4  -> pilha: 5 4
lê *  -> desempilha 4, desempilha 5, empilha 5*4 -> pilha: 20

Quais ordens de saída são possíveis?

Suponha que 1, 2, 3, 4 sejam empilhados nessa ordem, e que desempilhar possa acontecer a qualquer momento. Quando um valor sai, tudo o que foi empilhado depois dele e ainda está dentro precisa sair primeiro, na ordem inversa. Então, depois de imprimir um valor x, os valores menores ainda não impressos devem sair em ordem decrescente. Por exemplo, 2, 1, 3, 4 é possível, mas 2, 4, 1, 3 não é: depois que 4 sai, o 3 está acima do 1 e tem de sair primeiro.

Uma pilha que conhece o seu mínimo

Para obter o mínimo em O(1), mantenha uma segunda pilha de mínimos. Empilhe x nela quando estiver vazia ou quando x for menor ou igual ao topo dela. Ao desempilhar, se o valor removido for igual ao topo da segunda pilha, desempilhe também essa. A comparação precisa ser 'menor ou igual': se o mínimo 3 é empilhado duas vezes e só a primeira cópia é registrada, remover um 3 apaga o registro do outro e a resposta fica errada.

Filas e deques

Uma fila é a fila do caixa: as pessoas entram no fim e saem pela frente, então o primeiro a chegar é o primeiro a ser atendido. Isto é FIFO: first in, first out (o primeiro a entrar é o primeiro a sair). As operações são enqueue (inserir no fim) e dequeue (remover da frente). Ninguém entra nem sai pelo meio.

frente -> [ A ][ B ][ C ] <- fim
dequeue devolve A:  [ B ][ C ]
enqueue D:          [ B ][ C ][ D ]

Um deque (double-ended queue, fila de duas pontas, lido como 'dék') permite inserir e remover pelas duas pontas, mas ainda não pelo meio. Ele generaliza a pilha e a fila. Numa lista duplamente encadeada ou num vetor circular, as quatro operações custam O(1).

Fila em lista encadeada

Os elementos saem pela frente e entram pelo fim, então guarde dois ponteiros, um para cada ponta. Assim nenhuma operação percorre nós. O caso especial clássico: quando você remove o único elemento, os dois ponteiros devem voltar a nulo, senão o ponteiro do fim apontaria para um nó que não existe mais.

Fila em vetor: o truque circular

Com índices front e rear que só avançam, as células à esquerda de front são desperdiçadas a cada remoção, e logo a fila diz 'cheia' com o vetor quase vazio. Um conserto é deslocar todos os elementos para trás, mas então a remoção custa O(n). O conserto melhor é a fila circular: trate o vetor como um anel, em que depois do último índice vem o índice 0.

índice:   0     1     2     3     4     5
        [ C ] [ D ] [   ] [   ] [ A ] [ B ]
                                   ^front = 4
N = 6, front = 4, count = 4: A em 4, B em 5, C em 0, D em 1

A próxima inserção vai no índice (front + count) mod N, em que mod é o resto de uma divisão. A frente anda do mesmo jeito, front = (front + 1) mod N, a cada remoção. No anel acima, N = 6, front = 4 e 4 elementos estão guardados, então a próxima inserção é em (4 + 4) mod 6 = 2.

Filas e pilhas juntas

• Inverter uma fila: uma fila mantém a ordem de chegada, uma pilha a inverte. Se você passa os elementos de uma fila por uma pilha e de volta, a ordem deles fica invertida. Exemplo: a fila 3, 6, 9 entra na pilha como 3, 6, 9 (9 no topo) e sai como 9, 6, 3.
• Uma fila feita com duas pilhas, In e Out: enqueue empilha em In. dequeue desempilha de Out, e só quando Out está vazia ele antes move todos os elementos de In para Out, um pop e um push de cada vez. Mover inverte a ordem, e duas inversões devolvem a ordem de chegada. Cada elemento é empilhado e desempilhado no máximo duas vezes, então n operações custam O(n) no total, isto é, O(1) amortizado por operação, mesmo que um único dequeue custe O(n).

Recursão e listas generalizadas

Você já viu dois espelhos um de frente para o outro, com uma imagem dentro da imagem dentro da imagem? Recursão é quando uma função resolve um problema chamando a si mesma para uma versão menor do problema. Para funcionar, toda função recursiva precisa de duas partes: um caso base, respondido direto sem mais chamadas, e um passo recursivo que leva o problema na direção do caso base. Se uma delas falta, as chamadas se empilham na pilha de chamadas até a memória acabar (um estouro de pilha, stack overflow).

function sum(n: number): number {
	if (n === 0) return 0;      // caso base: nada mais a somar
	return n + sum(n - 1);      // passo: um problema menor
}

Torres de Hanói

Há 3 pinos e n discos de tamanhos diferentes, e um disco grande nunca pode ficar sobre um menor. Para mover n discos do pino A para o pino C: mova os n - 1 discos de cima para o pino B (reserva), mova o maior disco para C e depois mova os n - 1 discos de B para cima de C. O número de movimentos segue T(n) = 2 T(n - 1) + 1, cuja solução é 2ⁿ - 1.

Fibonacci: quando a recursão repete trabalho

fib(n) = fib(n-1) + fib(n-2), com fib(0) = 0 e fib(1) = 1. A versão recursiva direta resolve os mesmos problemas pequenos várias vezes: na figura abaixo, fib(2) é calculado duas vezes. As chamadas no total são 9 para fib(4), e o número cresce exponencialmente quando n cresce. Guardar os resultados já calculados, ou usar um laço simples, torna o custo O(n).

              fib(4)
             /      \
        fib(3)      fib(2)
        /    \      /    \
    fib(2) fib(1) fib(1) fib(0)
    /    \
fib(1) fib(0)

Listas generalizadas

Uma lista normal guarda só coisas simples. Numa lista generalizada cada elemento é um átomo (um valor simples, como a) ou outra lista generalizada. Os parênteses mostram o aninhamento: (a, (b, c)) tem um átomo a e uma sublista (b, c). Como a definição se refere a si mesma, os algoritmos que a percorrem são naturalmente recursivos.

A profundidade também é definida recursivamente: 1 mais a maior profundidade entre as sublistas, e átomos não somam nada. Uma lista feita só de átomos tem profundidade 1. Então (a, (b, (c, d))) tem profundidade 3: a lista mais interna (c, d) tem profundidade 1, (b, (c, d)) tem 2 e a lista inteira tem 3. É o mesmo raciocínio usado para a altura de uma árvore.

Árvores binárias e percursos

Uma árvore genealógica começa com um avô, que tem filhos, que têm seus próprios filhos. Uma árvore em computação é assim, desenhada de cabeça para baixo: uma raiz no topo e galhos descendo. Uma árvore binária é uma árvore em que todo nó tem no máximo dois filhos, chamados esquerdo e direito.

Palavras sobre árvores

• Raiz: o único nó sem pai. Folha: um nó sem filhos. Os outros são nós internos.
• Grau de um nó: o seu número de filhos. As folhas têm grau 0. Numa árvore com um só nó, a raiz também é uma folha.
• Nível: a distância da raiz, em passos. Altura da árvore: o número de arestas (ligações) no caminho mais longo da raiz até uma folha. Neste resumo, uma árvore com um só nó tem altura 0.
• Subárvore: qualquer nó junto com tudo o que está abaixo dele.

Cada nível pode ter o dobro de nós do nível de cima: 1, 2, 4, 8... Então uma árvore de altura h tem h + 1 níveis e no máximo 2^(h+1) - 1 nós (altura 3 dá 15). Lendo ao contrário: n nós cabem numa altura perto de log₂ n, e é por isso que uma boa árvore é tão rápida.

Passeando pela árvore

Os três percursos em profundidade diferem só em quando visitam a raiz de cada subárvore: antes das duas subárvores (pré-ordem), entre elas (em-ordem) ou depois delas (pós-ordem). Em todos eles a subárvore esquerda é percorrida antes da direita, e a regra é aplicada recursivamente a cada subárvore.

        1
       / \
      2   3
     / \
    4   5

A pós-ordem serve quando um nó precisa primeiro das respostas dos filhos, como liberar a memória de uma árvore ou calcular a sua altura. A raiz é sempre a última, e o primeiro nó visitado é sempre uma folha. O percurso por níveis usa uma fila: visite um nó e coloque seus filhos no fim da fila. A fila guarda os nós descobertos e ainda não visitados. Se você trocar a fila por uma pilha, o mesmo algoritmo vira um percurso em profundidade.

Reconstruindo uma árvore

A pré-ordem diz qual é a raiz: o primeiro item. A em-ordem diz quais chaves estão à esquerda e quais à direita dessa raiz. Repita a separação em cada parte, e uma única árvore aparece (desde que todas as chaves sejam diferentes). Exemplo: pré-ordem D B A C E e em-ordem A B C D E. A raiz é D. Na em-ordem, A B C fica à esquerda e E à direita. Na parte esquerda, a pré-ordem B A C diz que a raiz é B, com A à esquerda e C à direita. Então a pós-ordem é A C B E D.

Árvores de expressão

A expressão a * (b + c) - d pode ser guardada com operadores nos nós internos e operandos nas folhas. O formato da árvore já diz a ordem das operações, então não precisa de parênteses. A pós-ordem escreve cada operador depois dos operandos (a b c + * d -, a notação pós-fixa, que uma pilha sabe avaliar). A pré-ordem dá a notação pré-fixa.

Fatos de contagem

• Uma árvore binária com n nós tem n - 1 ligações (todo nó, exceto a raiz, tem um pai). Com 2 ponteiros de filho por nó há 2n ponteiros, então exatamente n + 1 deles são nulos, seja qual for o formato.
• Toda árvore binária não vazia tem uma folha a mais do que nós com dois filhos. Então uma árvore com 5 nós de dois filhos tem 6 folhas, não importa quantos nós tenham um filho só.

Árvores em um vetor

Uma árvore pode ser guardada nível por nível num vetor, sem ponteiros. Com a raiz no índice 0, os filhos do nó no índice i estão em 2i + 1 e 2i + 2, e o pai está em (i - 1) div 2 (divisão inteira). Então os filhos do índice 3 estão em 7 e 8. Não desperdiça espaço só para árvores completas, porque cada nó que falta deixa um buraco.

Árvores binárias de busca

Pense numa brincadeira de adivinhação: 'estou pensando num número de 1 a 100'. Você diz 50 e eu respondo 'maior'. Com uma pergunta você descartou metade dos números. Uma árvore binária de busca (ABB) é uma árvore binária construída para jogar esse jogo. Em todo nó, todas as chaves da subárvore esquerda são menores e todas as chaves da subárvore direita são maiores (aqui as chaves são todas diferentes).

        8
       / \
      3   10
     / \
    1   6

Para buscar, compare com o nó e siga só um lado, jogando o outro fora. Para inserir, busque a chave e coloque-a como uma nova folha onde a busca termina. O custo de busca, inserção e remoção é o tamanho do caminho, no máximo a altura da árvore.

Fatos úteis

• O percurso em-ordem visita as chaves em ordem crescente, em O(n). É assim que uma ABB lista dados ordenados.
• O mínimo é achado seguindo os ponteiros da esquerda a partir da raiz até não haver filho esquerdo. O máximo é simétrico, pela direita.
• A propriedade é sobre subárvores inteiras, não só pai e filho. Um validador que só confere 'filho esquerdo menor, filho direito maior' aceita uma árvore errada, por exemplo um nó 5 com filho esquerdo 3, em que o 3 tem um filho direito 7: o 7 está na subárvore esquerda do 5, mas é maior que 5. Um validador correto leva um intervalo de valores permitidos para baixo na árvore (ir para a esquerda baixa o limite superior, ir para a direita sobe o limite inferior), ou confere se a em-ordem é crescente.

O formato depende da ordem de inserção

Uma ABB simples não faz balanceamento: uma chave nova só vira folha onde a sua busca termina. Assim, as mesmas chaves dão árvores diferentes conforme a ordem em que chegam. Se as chaves chegam já ordenadas (1, 2, 3, ..., 1000), cada chave nova é maior que todas as outras e vai à direita da última. A árvore vira uma lista encadeada de altura n - 1, e uma busca custa O(n).

1
 \
  2
   \
    3
     \
      4

Para obter a menor altura com as chaves de 1 a 7, insira primeiro a mediana (4), depois as medianas de cada metade (2 e 6), depois o resto. A árvore tem altura 2. Quando você não pode escolher a ordem, só o balanceamento automático garante uma boa altura. É isso que as árvores AVL e rubro-negras fazem.

Remoção

• Uma folha: é só cortar.
• Um filho: o filho toma o lugar do nó removido.
• Dois filhos: não dá para deixar um buraco. Troque a chave pela sua vizinha na ordem: o sucessor em-ordem (menor chave da subárvore direita) ou o antecessor (maior chave da subárvore esquerda). Essa vizinha tem no máximo um filho, então removê-la do lugar antigo cai num dos casos fáceis.

Exemplo: uma árvore com 40 na raiz, 20 e 60 abaixo, 10 e 30 sob o 20, 50 e 70 sob o 60, e 55 sob o 50. Removendo 40 pela regra do sucessor: a menor chave da subárvore direita é 50 (a mais à esquerda sob o 60). O 50 toma o lugar da raiz, e o seu lugar antigo é preenchido pelo único filho, 55, que vira filho esquerdo do 60.

Árvores AVL

Uma árvore que se inclina demais é como uma pilha de livros prestes a cair. A árvore AVL (nome dos inventores Adelson-Velsky e Landis) é uma árvore binária de busca que se conserta sozinha. A regra: em todo nó, as alturas das subárvores esquerda e direita diferem em no máximo 1. Essa regra local simples mantém a altura da árvore inteira em O(log n).

Cada nó guarda um número pequeno, o fator de balanceamento: aqui, a altura da subárvore direita menos a altura da subárvore esquerda. Numa AVL válida ele é sempre -1, 0 ou +1. Depois de uma inserção ou remoção, os fatores são atualizados na volta até a raiz. Se algum nó chega a ±2, ele é consertado com uma rotação.

A rotação

Uma rotação troca os papéis de um nó e de um de seus filhos mudando alguns ponteiros, em tempo constante. Ela muda as alturas, mas mantém a ordem da esquerda para a direita de todas as chaves, então a árvore continua sendo de busca.

    x                  y
   / \                / \
  A   y     ---->    x   C
     / \            / \
    B   C          A   B

Ambas leem:  A x B y C

Os quatro casos

Ache o primeiro nó desbalanceado subindo a partir da chave nova. Olhe o caminho até a chave nova, abaixo desse nó:

No caso interno uma rotação simples só espelharia o problema. A rotação dupla primeiro endireita o caminho e depois gira o nó desbalanceado. O neto sobe dois níveis e suas duas subárvores são divididas entre o antigo pai e o antigo avô.

  3          3           2
 /          /           / \
1    ->    2     ->    1   3
 \        /
  2      1

Para um caso externo, pegue as chaves 1, 2, 3 nessa ordem: elas formam uma corrente à direita, a raiz 1 chega a +2, e uma rotação à esquerda no 1 faz do 2 a raiz, com 1 e 3 como filhos. O conserto é local: os nós acima do ponto consertado não mudam.

Que altura ela pode ter?

A AVL mais magra de altura h tem uma subárvore de altura h - 1, outra de altura h - 2, ambas também magras, mais a raiz. A recorrência é N(h) = N(h-1) + N(h-2) + 1, que cresce como os números de Fibonacci. Por isso a altura de uma AVL com n nós é no máximo cerca de 1,44 log₂ n.

Inserção versus remoção

Depois de uma inserção, a árvore ficou mais alta em algum lugar, e um passo de rotação (simples ou dupla) devolve aquela subárvore à altura anterior, então o conserto termina ali: no máximo um passo de rotação. Depois de uma remoção, uma subárvore ficou mais baixa, e a rotação que conserta um nó pode deixar a subárvore ainda mais baixa, o que pode desequilibrar o pai. Então a remoção pode precisar conferir todos os ancestrais até a raiz, com até O(log n) passos de rotação. O custo total continua O(log n).

Árvores rubro-negras

Uma árvore rubro-negra se balanceia com cores em vez de alturas. Cada nó é pintado de vermelho ou preto, e algumas regras impedem que a árvore se incline demais. É uma regra mais frouxa que a da AVL: a árvore pode ficar um pouco mais alta, mas as atualizações pedem menos reorganização.

As regras

1. Todo nó é vermelho ou preto.
2. A raiz é preta (a convenção deste resumo).
3. As folhas vazias, chamadas NIL, são pretas.
4. Um nó vermelho só tem filhos pretos (nunca dois vermelhos seguidos).
5. Todos os caminhos de um nó até as folhas NIL abaixo dele têm o mesmo número de nós pretos.

Por que isso dá uma árvore baixa? Todos os caminhos da raiz até as folhas têm o mesmo número de pretos, e entre dois pretos cabe no máximo um vermelho. Então o caminho mais longo tem no máximo o dobro de nós do mais curto. Isso limita a altura em 2 log₂(n + 1).

Exemplo: se todo caminho da raiz até um NIL tem exatamente 2 nós pretos (sem contar o NIL), o caminho mais curto tem 2 nós (ambos pretos) e o mais longo alterna preto e vermelho, terminando num vermelho: preto, vermelho, preto, vermelho, o que dá no máximo 4 nós.

Inserção

A chave nova entra como folha e é pintada de vermelho. Um nó vermelho nunca muda a contagem de pretos de nenhum caminho, que é a regra mais delicada. No máximo uma regra pode quebrar: um nó vermelho com pai vermelho. O conserto (o fix-up) olha o tio, o irmão do pai.

Com tio vermelho nenhum caminho muda a sua contagem de pretos, porque o preto do avô só desce para os seus dois filhos. Esse é o único caso que se repete. Se chegar à raiz e a raiz ficar vermelha, ela é pintada de preto de novo, o que sobe em um a contagem de pretos de todos os caminhos ao mesmo tempo, então as regras continuam valendo.

      8B
     /  \
   5B    9B
           \
           12R

Acompanhe: 5 é a raiz (preta). O 8 vai para a direita, vermelho. Inserir 9 coloca um filho vermelho sob um pai vermelho com tio preto (NIL): uma rotação à esquerda no 5 e uma troca de cores fazem do 8 preto, com filhos vermelhos 5 e 9. Inserir 12 como filho do 9 vermelho encontra um tio vermelho (5): recolore, então 5 e 9 ficam pretos e 8 fica vermelho, e depois 8 é a raiz e é pintado de preto de novo. O 12 continua vermelho.

AVL ou rubro-negra?

As duas garantem busca, inserção e remoção em O(log n). Nas medições deste repositório, com 100.000 chaves aleatórias uma árvore simples é só cerca de duas vezes mais alta que as balanceadas (41 contra 20), mas com chaves ordenadas ela é uma corrente. Balancear é um seguro contra uma ordem de chegada que você não escolhe.

Heaps e filas de prioridade

No pronto-socorro de um hospital, quem chegou primeiro nem sempre é atendido primeiro: o caso mais urgente vai na frente. Uma fila de prioridade funciona assim: você insere itens com uma prioridade, e ela sempre entrega o de maior prioridade (não o mais antigo). O jeito usual de construí-la é um heap.

Um max-heap binário tem duas propriedades independentes. Ordem: todo nó é maior ou igual aos seus filhos, então o maior elemento está sempre na raiz. Forma: a árvore é completa, isto é, todos os níveis estão cheios, exceto possivelmente o último, que é preenchido da esquerda para a direita. Irmãos e primos não são comparados, então manter essa ordem parcial é bem mais barato do que manter tudo ordenado.

Uma árvore dentro de um vetor

Por causa da forma completa, não há buracos, e o heap cabe num vetor sem ponteiros. Com a raiz no índice 0, os filhos do índice i estão em 2i + 1 e 2i + 2, e o pai está em (i - 1) div 2.

árvore:       9            vetor: [9][5][6][1][2]
            /   \                  0  1  2  3  4
           5     6
          / \
         1   2

Inserir e remover o máximo

• Inserir: ponha o elemento na primeira posição livre do vetor (isso mantém a forma completa) e depois suba (sift up): troque com o pai enquanto for maior. Insira 8 no heap acima: ele vai para o índice 5, o pai é 6 (índice 2), 8 é maior, troca. O próximo pai é 9, para. Resultado: [9, 5, 8, 1, 2, 6]. No máximo cerca de log₂ n trocas.
• Remover o máximo: pegue a raiz. Para não deixar um buraco, mova o último elemento do vetor para a raiz e depois desça (sift down): troque com o maior dos dois filhos enquanto ele for menor que esse filho. Remova o máximo de [9, 5, 8, 1, 2, 6]: o 6 vai para a raiz, o maior filho é 8, troca. Resultado: [8, 5, 6, 1, 2]. Trocar com o maior filho é essencial: senão o novo pai poderia ser menor que o seu irmão.

Dois fatos surpreendentes

• Construir um heap é linear. Aplicar sift-down a cada nó interno, do último até a raiz, custa a cada nó a sua altura, não a altura da árvore. A maioria dos nós está perto do fundo, onde a altura é pequena, então a soma é O(n), mais barata que inserir n itens um por um (O(n log n)). É o primeiro passo do heapsort.
• A menor chave de um max-heap não fica num lugar fixo. Ela pode estar em qualquer folha. Num heap com n nós as folhas ocupam os índices de n div 2 em diante, cerca de metade do vetor. Procurar o mínimo é conferir todas elas: O(n).

Tabelas de espalhamento: colisões, fator de carga, rehashing

Imagine uma escola com um armário para cada número de chamada. Para achar o caderno do aluno 17 você não procura em todos os armários: vai direto ao armário 17. Uma tabela de espalhamento (tabela hash) faz isso para qualquer tipo de chave, até nomes. Uma função de espalhamento (hash) transforma a chave em um número, que vira um índice num vetor. Então a busca vai direto a um lugar só, em média em O(1).

Uma boa função hash é determinística (a mesma chave sempre dá o mesmo código), rápida, e espalha bem as chaves. Uma função ruim ainda é correta, mas põe muitas chaves nos mesmos lugares e deixa tudo lento.

Colisões

Há muito mais chaves possíveis do que posições, então duas chaves diferentes às vezes caem no mesmo índice. Isso é uma colisão. Toda tabela precisa de um plano para isso. Os dois clássicos:

7  -> índice 2: livre, guarda.
12 -> índice 2 ocupado, tenta 3: livre, guarda.
2  -> índices 2 e 3 ocupados, tenta 4: livre, guarda.

índice:  0    1    2    3    4
       [   ][   ][ 7 ][ 12][ 2 ]

Uma busca segue o mesmo caminho de posições: pergunta o índice 2, depois o 3, depois o 4, e para quando encontra a chave ou uma posição vazia.

Remover com endereçamento aberto: lápides

No endereçamento aberto, uma busca termina quando encontra uma posição vazia. Se você remove a chave A (que está antes de B na mesma sequência de sondagem) só esvaziando a posição dela, uma busca posterior por B para na célula vazia e diz errado 'não encontrada'. A solução é uma lápide (tombstone), uma marca especial: a busca passa por cima dela, e uma inserção pode reutilizá-la. As lápides ainda alongam as sondagens, então uma reconstrução (rehash) as descarta.

Fator de carga

O fator de carga α é o número de elementos guardados dividido pelo número de posições. Com 40 posições e 30 elementos, α = 0,75. Ele mede quão cheia está a tabela, e portanto quão provável é uma colisão. Com encadeamento, α é o tamanho médio de uma lista: uma busca que falha examina cerca de α entradas e uma que acha examina cerca de 1 + α/2. Com 300 elementos em 100 posições, α = 3, então uma busca por uma chave ausente olha cerca de 3 entradas.

Com sondagem linear, as células ocupadas se juntam em longas sequências (agrupamento primário), e uma chave que cai numa sequência precisa andar até o fim dela, deixando-a ainda maior. O número esperado de posições examinadas numa busca que falha é cerca de (1 + 1/(1 - α)²) / 2, que explode quando α chega perto de 1.

Com encadeamento, as mesmas cargas custam 0,25, 0,5, 0,75 e 0,9 entradas: uma reta. Por isso as tabelas de endereçamento aberto são redimensionadas com cargas menores (o mini-projeto deste repositório usa 0,5 para sondagem e 0,75 para encadeamento).

Rehashing

Quando α passa de um limite, a tabela cresce (em geral dobrando). Mas o índice é hash mod capacidade, então depende do tamanho: toda entrada precisa ser inserida de novo. Isso é o rehashing. Custa O(n), mas dobrar o tamanho o torna raro, então a inserção continua O(1) amortizado. Ele também encurta as listas ao separar chaves que colidiam: as chaves 3, 11 e 27 caem todas no índice 3 com 8 posições; com 16 posições, o 3 fica no 3 e o 11 e o 27 vão os dois para o 11.

equals e hashCode

Uma tabela acha um objeto em dois passos: o código hash escolhe a posição, e a igualdade decide dentro dela. Então objetos iguais devem ter o mesmo código hash. Em Java, se a classe Point sobrescreve equals mas não hashCode, set.contains(new Point(1, 2)) depois de adicionar outro new Point(1, 2) muito provavelmente devolve false: o código hash padrão é diferente, a busca olha no lugar errado, e o objeto parece sumir embora esteja guardado.

Grafos: representações, BFS e DFS

Um mapa de cidades e estradas, uma rede de amigos, os links entre páginas da web: tudo isso são grafos. Um grafo tem vértices (os pontos, como as cidades) e arestas (as linhas entre eles, como as estradas). Se as arestas têm sentido (ruas de mão única), o grafo é dirigido, e a aresta também se chama arco. O grau de um vértice é o seu número de vizinhos.

Duas formas de guardar um grafo

Seja V o número de vértices e E o número de arestas.

Um grafo é esparso quando E é muito menor que V². Com 10.000 vértices e 30.000 arestas, uma matriz precisaria de 100 milhões de células, enquanto as listas precisam de apenas dezenas de milhares de entradas. Use listas.

Num grafo não dirigido, uma aresta v–w precisa ser encontrada por qualquer ponta, então é guardada duas vezes, uma em cada lista. O tamanho total das listas, que é a soma dos graus, é sempre 2E. Um grafo com 5 arestas e sem laços tem 10 entradas.

Duas formas de caminhar num grafo

    A
   / \
  B   C
   \ /
    D --- E

• A busca em profundidade (DFS) segue um caminho até onde der, depois volta e tenta outro, como explorar um labirinto com um novelo de lã. Usa recursão ou uma pilha explícita, e os vértices na pilha são exatamente o caminho atual. A partir de A (vizinhos em ordem alfabética) a ordem é A B D C E.
• A busca em largura (BFS) visita a origem, depois todos os seus vizinhos, depois os vizinhos deles: camada por camada, como ondas na água. Usa uma fila, e cada vértice é marcado quando entra na fila, para não ser inserido duas vezes. A partir de A a ordem é A B C D E.

Num grafo sem pesos, a BFS garante que a camada em que um vértice é achado pela primeira vez é a sua distância mínima em arestas a partir da origem. Guardar o predecessor de cada vértice permite reconstruir o caminho mais curto de trás para frente.

O custo de uma caminhada depende da representação, porque o passo principal é listar os vizinhos de cada vértice. Com listas, o total é Θ(V + E). Com matriz, listar custa V para cada vértice, então Θ(V²) mesmo para um grafo com poucas arestas.

Ciclos e ordem topológica

Um ciclo é um caminho que volta ao ponto de partida. Num grafo dirigido, encontrar um vértice já visitado durante a DFS é um ciclo só se esse vértice ainda estiver no caminho atual (um ancestral). Um vértice que já terminou e é alcançado por outro caminho não fecha ciclo nenhum. Por isso a detecção usa três estados: não visitado, em andamento e terminado. Um detector que diz 'ciclo' sempre que vê um vértice visitado está errado: em A→B, A→C, B→D, C→D ele acusaria um ciclo ao chegar em D pela segunda vez, mas não existe nenhum.

Uma ordenação topológica lista os vértices de modo que, para toda aresta v→w, v vem antes de w, como a ordem de se vestir (meias antes dos sapatos). Ela existe só para grafos dirigidos sem ciclos (DAGs) e em geral não é única: vértices sem caminho entre eles podem aparecer em qualquer ordem relativa. Para as arestas A→B, A→C, B→D e C→D, A tem de ser o primeiro e D o último, mas B e C podem trocar: A B C D e A C B D são ambas válidas, então há 2 ordenações.

Juntando tudo: como escolher uma estrutura

Agora você conhece muitas formas. A habilidade está em olhar o que o programa mais faz e escolher a forma que é barata para isso. Aqui está o quadro todo lado a lado (médias, a menos que se diga outra coisa; n é o número de itens).

Perguntas para fazer

• Preciso dos itens em ordem (ordenados, ou a próxima chave maior)? Use uma árvore de busca balanceada, não uma tabela hash.
• Só preciso de busca exata por chave? Use uma tabela hash.
• Só preciso do maior ou do menor item, repetidas vezes? Use um heap.
• O último ou o primeiro item importa (LIFO ou FIFO)? Use uma pilha ou uma fila.
• Os itens estão relacionados entre si numa rede? Use um grafo, com listas se for esparso.
• O acesso por posição é importante? Use um vetor.

Erros comuns

• Achar que uma lista encadeada é sempre mais rápida que um vetor porque 'inserir é O(1)'. Chegar ao lugar custa O(n).
• Esquecer que uma ABB simples alimentada com dados ordenados vira uma corrente.
• Esquecer os casos vazio e cheio (underflow de pilha, fila com um elemento, lista vazia, primeiro nó).
• Usar uma tabela hash com uma função hash ruim ou com fator de carga alto, ou mudar os campos-chave de um objeto depois de inseri-lo.
• Confundir o TAD (o quê) com a sua implementação (o como).

Para ver essas ideias se mexendo, experimente as visualizações do VisuAlgo, onde você insere e remove chaves e acompanha, passo a passo, listas, heaps, tabelas hash, árvores AVL e rubro-negras e caminhadas em grafos. Para aulas, o curso do MIT abaixo cobre sequências, hashing, árvores binárias, AVL, heaps e busca em grafos.