| Operação | Média | Pior caso |
|---|
* amortizado: em média numa longa série de operações
Visualizador de estruturas de dados
Uma estrutura de dados é uma forma de guardar dados para que as perguntas mais frequentes tenham resposta rápida. Escolha uma das onze estruturas clássicas, da pilha à árvore rubro-negra, escreva um valor e prima uma operação. Cada passo decorre no ecrã: que nó é comparado, que ligação muda, porque é que uma árvore roda ou um valor sobe, com uma frase que diz o que acontece. Os mosaicos contam o trabalho de cada operação, e uma tabela indica o seu tempo de execução. Escolha uma estrutura, escreva um valor e prima uma operação. Cada operação decorre passo a passo: os nós realçados mostram o que é comparado, movido ou alterado, e a linha por baixo da imagem diz o que acontece e porquê. Recuar, Passo, Reproduzir e Fim percorrem de novo os passos. Preencher ao acaso e Limpar recomeçam do zero, e Anular desfaz uma operação. Os mosaicos mostram o tamanho, a altura das árvores, o trabalho da última operação (comparações, sondagens ou ligações ao pai seguidas) e um valor que importa para a estrutura; a tabela indica o tempo de execução de cada operação.
Como funciona
- Escolha uma estrutura, como uma árvore binária de pesquisa, uma tabela de dispersão ou uma trie. Começa com conteúdo aleatório; Preencher ao acaso e Limpar recomeçam do zero.
- Escreva um valor e prima uma operação: empilhar, pôr na fila, inserir, apagar, pesquisar, um percurso, union ou find. Os passos decorrem sozinhos; Recuar, Passo, Reproduzir e Fim percorrem-nos de novo.
- Leia na linha por baixo da imagem o que faz cada passo, veja nos mosaicos o tamanho, a altura e o trabalho da última operação, e compare os tempos de execução na tabela.
Listas, pilhas e filas
As estruturas mais simples guardam os elementos em fila. Uma pilha só trabalha numa ponta, por isso o último elemento a entrar é o primeiro a sair, como uma pilha de pratos; uma fila acrescenta no fim e retira pela frente, como uma fila num balcão. Aqui, a fila vive num buffer circular: a frente e o fim dão a volta a um array fixo e recomeçam no início depois do fim, e quando ele enche os elementos são copiados para outro com o dobro do tamanho. Uma lista ligada une nós por ponteiros, por isso inserir na cabeça não custa nada, mas encontrar a cauda ou um índice obriga a seguir as ligações uma a uma.
Árvores, heaps, tabelas de dispersão e conjuntos
Uma árvore binária de pesquisa guarda os valores menores à esquerda e os maiores à direita, por isso uma pesquisa corta os candidatos a metade em cada passo, desde que a árvore se mantenha frondosa. As árvores AVL e rubro-negras tratam disso, com rotações que pode observar e que têm o nome do seu caso. Um heap guarda no topo só o valor menor ou maior, que é tudo o que uma fila de prioridade precisa. Uma tabela de dispersão salta diretamente para um balde calculado a partir da chave e tem de lidar com colisões; uma trie partilha os prefixos das palavras; o union-find diz em tempo quase constante se dois elementos pertencem ao mesmo conjunto.
Perguntas frequentes
Que estrutura de dados devo usar?
Depende das perguntas que faz com mais frequência. Uma pilha ou uma fila quando os elementos são tratados pela ordem de chegada ou pela ordem inversa; uma tabela de dispersão para procurar uma chave; uma árvore de pesquisa equilibrada, como uma AVL ou uma rubro-negra, quando também precisa das chaves por ordem ou da chave mais próxima; um heap quando só precisa sempre do elemento menor ou maior; uma trie para palavras e prefixos; o union-find para acompanhar grupos que se fundem.
Qual é a diferença entre uma árvore AVL e uma árvore rubro-negra?
Ambas mantêm pouco profunda uma árvore binária de pesquisa, por isso cada pesquisa, inserção e eliminação demora um tempo proporcional a log n. Uma árvore AVL é equilibrada de forma mais rigorosa, com as alturas dos dois lados de cada nó a uma de distância no máximo, por isso as pesquisas são um pouco mais rápidas. Uma árvore rubro-negra permite mais folga e precisa de menos rotações quando muda, e é por isso que muitas bibliotecas padrão a usam nos seus mapas e conjuntos ordenados.
Porque é que uma tabela de dispersão pode ser lenta no pior caso?
Se muitas chaves caírem no mesmo balde, uma pesquisa tem de as verificar uma a uma, tal como numa lista. Uma boa função de dispersão espalha as chaves de forma uniforme e a tabela cresce antes de ficar demasiado cheia, por isso uma pesquisa demora em média um tempo constante. Experimente uma tabela de tamanho 10 com números que acabam no mesmo algarismo, ou palavras que são anagramas umas das outras, para ver as colisões acumularem-se.
O que significam os números ao lado dos nós AVL?
São fatores de equilíbrio: a altura da subárvore esquerda de um nó menos a da sua subárvore direita. Numa árvore AVL, todos os fatores têm de ser −1, 0 ou +1. Quando uma inserção ou eliminação deixa um em +2 ou −2, a árvore roda nesse nó; o caso (LL, RR, LR ou RL) diz para que lado pende a altura a mais e decide entre uma e duas rotações.
Alguma coisa é enviada para um servidor?
Não. Cada operação é executada no seu navegador, e o conteúdo de cada estrutura é guardado no armazenamento local deste navegador.
Pronto para experimentar?
Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.
Ir para o editor