Estruturas de dados explicadas

Qualquer programa guarda dados em algum lado, e a forma como os guarda decide o que é rápido e o que é lento. Uma lista de um milhão de nomes pode ser percorrida nome a nome, ou organizada de modo que vinte comparações encontrem qualquer nome. As estruturas de dados são essas organizações: meia dúzia de ideias, a maioria mais antigas do que o computador pessoal, que estão dentro de cada base de dados, sistema operativo, navegador e jogo.

Uma árvore binária de pesquisa colorida a vermelho e preto, uma pilha de caixas, uma fila de baldes de dispersão com uma cadeia de chaves em colisão e setas que ligam os nós de uma lista
Uma árvore binária de pesquisa colorida a vermelho e preto, uma pilha de caixas, uma fila de baldes de dispersão com uma cadeia de chaves em colisão e setas que ligam os nós de uma lista

Para que serve uma estrutura de dados

Uma estrutura de dados escolhe-se pelas perguntas a que tem de responder. O registo de chamadas de um telefone precisa primeiro da última chamada, a fila de uma impressora primeiro do trabalho mais antigo, um dicionário do significado de uma palavra entre cem mil, um planeador de percursos do cruzamento não visitado mais próximo. Cada estrutura torna algumas operações rápidas abdicando de outras, e a notação O grande descreve essa troca: O(1) significa que o tempo não cresce com o número n de elementos, O(log n) que duplicar n acrescenta um passo, e O(n) que o tempo cresce em proporção a n.

Pilhas, filas e deques

Uma pilha acrescenta e retira na mesma ponta: último a entrar, primeiro a sair. Os históricos de anular, o botão Retroceder e as chamadas de um programa em execução são pilhas. Uma fila acrescenta no fim e retira pela frente: primeiro a entrar, primeiro a sair, como as teclas premidas ou uma fila de impressão. Uma deque permite as duas coisas nas duas pontas. As três demoram um tempo constante por operação. Uma fila é muitas vezes guardada num buffer circular, um array fixo em que a frente e o fim dão a volta depois da última posição; quando enche, os elementos são copiados para um array com o dobro do tamanho. Copiar custa O(n), mas acontece tão raramente que cada operação continua a custar O(1) em média, aquilo a que se chama um limite amortizado.

Listas ligadas

Uma lista ligada guarda cada valor num nó com um ponteiro para o nó seguinte. Inserir ou apagar só muda um ou dois ponteiros, sem deslocar nada, mas não é possível saltar para o décimo nó: seguem-se as ligações a partir da cabeça. Uma lista que só guarda a cabeça chega à cauda em O(n) passos; as listas reais costumam guardar também um ponteiro para a cauda, e as duplamente ligadas um ponteiro para trás, e é assim que se constroem um histórico de navegação ou uma cache LRU.

Árvores binárias de pesquisa

Uma árvore binária de pesquisa guarda, em cada nó, os valores menores na subárvore esquerda e os maiores na direita. Uma pesquisa compara e vai para a esquerda ou para a direita, e um percurso em ordem lê os valores ordenados. Apagar uma folha é simplesmente retirá-la, um nó com um filho é substituído por esse filho, e um nó com dois filhos pelo seu sucessor em ordem, o menor valor da sua subárvore direita. Tudo isto demora um tempo proporcional à altura da árvore: cerca de log n quando a árvore é frondosa, mas n quando os valores chegam ordenados e a árvore degenera numa lista.

Árvores AVL e rubro-negras

As árvores autoequilibradas reparam a sua forma depois de cada alteração. Uma árvore AVL, inventada por Adelson-Velsky e Landis em 1962, mantém as alturas das duas subárvores de cada nó a uma de distância no máximo; quando o fator de equilíbrio de um nó chega a ±2, uma rotação (os casos LL e RR) ou duas (LR e RL) repõem o equilíbrio. Uma árvore rubro-negra colore os nós de modo que a raiz seja preta, nenhum nó vermelho tenha um filho vermelho e todos os caminhos para baixo passem pelo mesmo número de nós pretos, o que mantém o caminho mais longo no máximo com o dobro do mais curto. Repara-se repintando e com poucas rotações no máximo, e é a árvore que está dentro do TreeMap de Java, do std::map de C++ e do escalonador do Linux.

Heaps e filas de prioridade

Um heap binário é uma árvore binária completa guardada num array sem ponteiros: os filhos da posição i estão em 2i + 1 e 2i + 2. Num heap mínimo, cada pai é no máximo tão grande como os seus filhos, por isso o menor valor está sempre na raiz. Um valor novo vai para o fim e sobe para lá dos pais maiores; extrair a raiz leva o último valor para o topo e afunda-o. Ambas as operações custam O(log n), e um array inteiro pode ser transformado num heap em O(n). Os heaps fazem funcionar as filas de prioridade dos caminhos mais curtos de Dijkstra, das simulações de eventos e dos escalonadores dos sistemas operativos, e dão origem ao heapsort.

Tabelas de dispersão

Uma tabela de dispersão transforma uma chave num índice do array com uma função de dispersão e vai diretamente para lá. Chaves diferentes podem cair no mesmo índice: é uma colisão. O encadeamento guarda uma pequena lista em cada balde; o endereçamento aberto, como a sondagem linear, experimenta as posições seguintes até encontrar uma livre e, quando uma chave é apagada, tem de deixar uma lápide para que as pesquisas seguintes continuem a sondar. Com uma boa função de dispersão e um fator de carga (chaves por balde) mantido baixo à custa de aumentar a tabela, inserir, pesquisar e apagar custam O(1) em média. Uma função fraca, como somar os códigos dos caracteres de uma palavra, manda os anagramas para o mesmo balde. As tabelas de dispersão estão por trás do dict de Python, dos objetos de JavaScript e dos índices das bases de dados.

Tries e union-find

Uma trie, ou árvore de prefixos, guarda cadeias de caracteres com um carácter por nível, de modo que as palavras que começam da mesma maneira partilham um caminho e um nó marca onde termina uma palavra. Encontrar uma palavra de comprimento L demora L passos, seja qual for o número de palavras guardadas, e todas as palavras com um dado prefixo estão numa só subárvore: é assim que funcionam o preenchimento automático e os corretores ortográficos. O union-find guarda os elementos em conjuntos disjuntos, cada um uma árvore cuja raiz dá nome ao conjunto. Find segue as ligações ao pai até à raiz; union pendura uma raiz debaixo de outra. Com união por posto e compressão de caminhos, uma longa série de operações custa um tempo quase constante cada uma, a função de Ackermann inversa α(n), que não passa de 4 para qualquer n realista. O algoritmo de Kruskal para a árvore abrangente mínima assenta nela.

Perguntas frequentes

Qual é a diferença entre um array e uma lista ligada?

Um array guarda os elementos lado a lado na memória, por isso qualquer posição é alcançada de imediato, mas inserir no meio obriga a deslocar tudo o que vem depois. Uma lista ligada pode inserir em qualquer lado mudando ponteiros, mas chegar a uma posição obriga a percorrê-la a partir da cabeça. Os arrays também aproveitam muito melhor a cache do processador, e é por isso que na prática costumam ser mais rápidos.

O que significa tempo amortizado?

O custo médio por operação numa longa série, mesmo que uma operação isolada seja por vezes cara. Um buffer circular que duplica quando enche copia de vez em quando os seus n elementos, mas como as cópias se tornam mais raras à medida que o buffer cresce, n inserções custam O(n) no total, ou seja, O(1) cada uma em média.

Um heap é o mesmo que uma árvore binária de pesquisa?

Não. Uma árvore binária de pesquisa põe cada subárvore esquerda antes do seu nó e cada subárvore direita depois, por isso consegue listar todos os valores por ordem e encontrar qualquer valor depressa. Um heap só promete que cada pai vem antes dos seus filhos, o que basta para encontrar de imediato o mínimo ou o máximo, mas não para procurar um valor qualquer.

Como é que o union-find sabe se dois elementos estão ligados?

Segue as ligações ao pai a partir de cada elemento até à raiz da sua árvore. Se ambos chegarem à mesma raiz, estão no mesmo conjunto. A compressão de caminhos faz depois com que cada nó do caminho aponte diretamente para a raiz, por isso a pergunta seguinte sobre eles demora um só passo.

Pronto para experimentar?

Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.

Abrir o visualizador de estruturas de dados