Estruturas de Dados Fundamentais
Estruturas de dados fundamentais são as formas organizadas de armazenar e acessar dados — arrays, listas encadeadas, tabelas hash, árvores, heaps e seus relacionados — que determinam a eficiência das operações construídas sobre elas.
Definition
Uma estrutura de dados é uma forma de organizar e armazenar dados para que as operações definidas por seu tipo abstrato de dados possam ser realizadas eficientemente; estruturas de dados fundamentais são o pequeno conjunto de estruturas de propósito geral a partir das quais a maioria das outras são construídas.
Scope
Esta área abrange os tipos abstratos de dados (listas, dicionários, filas de prioridade, conjuntos) e as estruturas concretas que os implementam, juntamente com o custo de suas operações centrais (inserir, excluir, pesquisar, atualizar) sob análise de pior caso e amortizada. Ela trata de como a escolha da estrutura molda o desempenho do algoritmo e se conecta aos paradigmas de design e algoritmos de grafos e strings que dependem dessas estruturas. Exclui as estruturas de armazenamento de banco de dados e sistema de arquivos tratadas em outros subcampos.
Sub-topics
Core questions
- Qual tipo abstrato de dados uma aplicação necessita e qual estrutura concreta o implementa melhor?
- Quais são os custos de pior caso e amortizados de cada operação em uma dada estrutura?
- Como as estruturas trocam memória por tempo, ou velocidade de leitura por velocidade de atualização?
- Como a manutenção de um invariante (ordenamento, balanceamento, a propriedade de heap) limita os custos das operações?
- Quando uma estrutura simples é preferível a uma assintoticamente mais rápida, mas mais complexa?
Key concepts
- tipo abstrato de dados
- arrays e listas encadeadas
- pilhas e filas
- tabelas hash
- árvores binárias de busca
- árvores balanceadas
- heaps e filas de prioridade
- análise amortizada
- trade-offs tempo-espaço
Key theories
- Tipos abstratos de dados versus implementações
- Um tipo abstrato de dados especifica operações e suas semânticas independentemente da representação; múltiplas estruturas de dados concretas podem implementar o mesmo ADT com diferentes perfis de desempenho, permitindo que os projetistas raciocinem sobre correção e custo separadamente.
- Análise amortizada
- Algumas estruturas (arrays dinâmicos, splay trees) têm operações ocasionalmente caras, mas operações baratas em média ao longo de uma sequência; a análise amortizada (métodos agregados, contábeis, potenciais) limita rigorosamente esse custo médio.
Clinical relevance
As estruturas de dados fundamentais são os blocos de construção de essencialmente todo o software: tabelas hash suportam dicionários e índices de banco de dados, árvores balanceadas e B-trees organizam sistemas de arquivos e bancos de dados, filas de prioridade impulsionam agendadores e simulações de eventos, e a escolha da estrutura correta frequentemente determina se um sistema é escalável.
History
As estruturas de dados fundamentais foram catalogadas em The Art of Computer Programming de Knuth, a partir de 1968. Árvores auto-balanceadas (árvores AVL, 1962; árvores rubro-negras e B-trees na década de 1970) e estruturas avançadas como heaps de Fibonacci e splay trees (década de 1980, em grande parte devido a Tarjan e colaboradores) expandiram o campo, enquanto a análise amortizada forneceu uma descrição rigorosa de seu desempenho.
Key figures
- Donald Knuth
- Robert Sedgewick
- Robert Tarjan
- Rudolf Bayer
Related topics
Seminal works
- knuth1997vol1
- cormen2009
- sedgewick2011
Frequently asked questions
- Como escolher entre uma tabela hash e uma árvore de busca balanceada?
- Tabelas hash oferecem busca e inserção esperadas de O(1), mas sem ordem, enquanto árvores de busca balanceadas oferecem operações de O(log n) e mantêm as chaves ordenadas, suportando consultas de intervalo e travessia ordenada. Escolha hashing para buscas puras de chave e uma árvore quando a ordenação ou operações de intervalo são importantes.
- O que significa custo amortizado para uma estrutura de dados?
- Custo amortizado é o custo médio por operação ao longo de uma sequência de operações no pior caso. Um array dinâmico, por exemplo, ocasionalmente paga O(n) para redimensionar, mas tem uma média de O(1) por adição porque os redimensionamentos são raros em relação às adições baratas.