Computer Science › Fundamentos da Ciência da Computação
A diferença entre um TAD (operações e contrato comportamental) e uma estrutura de dados (a realização concreta em memória), e por que separar essas duas coisas é o que permite trocar a implementação sem tocar no código que a usa.
Árvore binária como árvore enraizada com no máximo dois filhos rotulados esquerda/direita, os termos precisos cheia/completa/perfeita, e as duas representações reais em memória: nós com ponteiros e vetor implícito com aritmética de índice.
Pré-ordem, em-ordem e pós-ordem como o mesmo esqueleto recursivo com o processamento do nó movido de posição, por que em-ordem produz ordem crescente numa árvore binária de busca, e por que percurso em largura exige uma fila em vez de recursão.
O invariante de ABB (esquerda menor, direita maior, aplicando-se a todos os descendentes) torna busca e inserção uma única descida por comparação, e remoção exige tratar três casos estruturais, o de dois filhos via sucessor em ordem.
Toda operação numa ABB custa O(h), não automaticamente O(log n); inserção em ordem já ordenada degenera a árvore numa cadeia de altura n, o que motiva diretamente as árvores autobalanceadas.
Uma função de hash mapeia uma chave para um índice de vetor, buscando O(1) em média; colisões são inevitáveis pelo princípio da casa dos pombos assim que há mais chaves possíveis que slots, o que torna resolução de colisão obrigatória, não opcional.
Uma colisão é resolvida sondando outro slot dentro do próprio vetor; sondagem linear é simples mas produz agrupamento primário, e remoção exige lápides para não quebrar sequências de sondagem de outras chaves.
Cada slot do vetor guarda uma pequena lista encadeada de toda chave que deu hash ali; o desempenho médio se reduz a uma única variável, o comprimento médio da cadeia, que é igual ao fator de carga quando o hash é uniforme.
O fator de carga n/m governa o desempenho real de uma tabela hash; rehashing (dobrar a tabela e reinserir tudo com índices recomputados) mantém alfa limitado com custo amortizado O(1), o mesmo argumento de série geométrica usado em vetores dinâmicos.
Uma sequência representada como uma cadeia de nós espalhados na memória, onde acesso por índice custa O(n) mas inserção ou remoção junto a um nó já em mãos custa O(1) puro rewiring de ponteiros.
Um ponteiro prev adicional converte remoção e inserção junto a um nó já em mãos, incluindo na cauda, de O(n) para O(1), ao custo real de memória extra por nó.
Por que memória contígua torna acesso indexado O(1) via aritmética de endereço (base + i * size), e por que essa mesma contiguidade torna inserção e remoção no meio O(n): não há como abrir espaço num bloco já totalmente ocupado.
Como dobrar a capacidade (não incrementos fixos) garante custo amortizado O(1) por append, provado pelo método agregado somando a série geométrica de custos de cópia, e por que amortizado O(1) não é o mesmo que pior caso O(1).
Comparando vetor dinâmico e lista duplamente encadeada por operação, e por que localidade de cache, o fator constante que Big-O ignora, pode fazer duas operações O(n) idênticas divergirem drasticamente em velocidade real.
A fila definida pelo contrato FIFO, por que uma fila ingênua com vetor força um deslocamento O(n) a cada dequeue, e como o buffer circular restaura enqueue/dequeue O(1) sem mover elemento algum.
O TAD deque generaliza pilha e fila com inserção e remoção O(1) em ambas as pontas, implementado sobre buffer circular ou lista duplamente encadeada, e por que pilha e fila são apenas disciplinas de uso restritas sobre um deque.
A pilha definida só por seu contrato LIFO (push/pop/peek/isEmpty), implementada intercambiavelmente sobre vetor dinâmico ou lista encadeada, e aplicada a parênteses balanceados e avaliação de expressões pós-fixas.
A interface uniforme has_next()/next() que separa percurso de armazenamento, implementada com índice inteiro sobre vetor e referência de nó sobre lista encadeada, e o perigo real de mutar uma coleção enquanto um iterador a percorre.
Part of the Computer Science curriculum.
A diferença entre um TAD (operações e contrato comportamental) e uma estrutura de dados (a realização concreta em memória), e por que separar essas duas coisas é o que permite trocar a implementação sem tocar no código que a usa.
Árvore binária como árvore enraizada com no máximo dois filhos rotulados esquerda/direita, os termos precisos cheia/completa/perfeita, e as duas representações reais em memória: nós com ponteiros e vetor implícito com aritmética de índice.
Pré-ordem, em-ordem e pós-ordem como o mesmo esqueleto recursivo com o processamento do nó movido de posição, por que em-ordem produz ordem crescente numa árvore binária de busca, e por que percurso em largura exige uma fila em vez de recursão.
O invariante de ABB (esquerda menor, direita maior, aplicando-se a todos os descendentes) torna busca e inserção uma única descida por comparação, e remoção exige tratar três casos estruturais, o de dois filhos via sucessor em ordem.
Toda operação numa ABB custa O(h), não automaticamente O(log n); inserção em ordem já ordenada degenera a árvore numa cadeia de altura n, o que motiva diretamente as árvores autobalanceadas.
Uma função de hash mapeia uma chave para um índice de vetor, buscando O(1) em média; colisões são inevitáveis pelo princípio da casa dos pombos assim que há mais chaves possíveis que slots, o que torna resolução de colisão obrigatória, não opcional.
Uma colisão é resolvida sondando outro slot dentro do próprio vetor; sondagem linear é simples mas produz agrupamento primário, e remoção exige lápides para não quebrar sequências de sondagem de outras chaves.
Cada slot do vetor guarda uma pequena lista encadeada de toda chave que deu hash ali; o desempenho médio se reduz a uma única variável, o comprimento médio da cadeia, que é igual ao fator de carga quando o hash é uniforme.
O fator de carga n/m governa o desempenho real de uma tabela hash; rehashing (dobrar a tabela e reinserir tudo com índices recomputados) mantém alfa limitado com custo amortizado O(1), o mesmo argumento de série geométrica usado em vetores dinâmicos.
Uma sequência representada como uma cadeia de nós espalhados na memória, onde acesso por índice custa O(n) mas inserção ou remoção junto a um nó já em mãos custa O(1) puro rewiring de ponteiros.
Um ponteiro prev adicional converte remoção e inserção junto a um nó já em mãos, incluindo na cauda, de O(n) para O(1), ao custo real de memória extra por nó.
Por que memória contígua torna acesso indexado O(1) via aritmética de endereço (base + i * size), e por que essa mesma contiguidade torna inserção e remoção no meio O(n): não há como abrir espaço num bloco já totalmente ocupado.
Como dobrar a capacidade (não incrementos fixos) garante custo amortizado O(1) por append, provado pelo método agregado somando a série geométrica de custos de cópia, e por que amortizado O(1) não é o mesmo que pior caso O(1).
Comparando vetor dinâmico e lista duplamente encadeada por operação, e por que localidade de cache, o fator constante que Big-O ignora, pode fazer duas operações O(n) idênticas divergirem drasticamente em velocidade real.
A fila definida pelo contrato FIFO, por que uma fila ingênua com vetor força um deslocamento O(n) a cada dequeue, e como o buffer circular restaura enqueue/dequeue O(1) sem mover elemento algum.
O TAD deque generaliza pilha e fila com inserção e remoção O(1) em ambas as pontas, implementado sobre buffer circular ou lista duplamente encadeada, e por que pilha e fila são apenas disciplinas de uso restritas sobre um deque.
A pilha definida só por seu contrato LIFO (push/pop/peek/isEmpty), implementada intercambiavelmente sobre vetor dinâmico ou lista encadeada, e aplicada a parênteses balanceados e avaliação de expressões pós-fixas.
A interface uniforme has_next()/next() que separa percurso de armazenamento, implementada com índice inteiro sobre vetor e referência de nó sobre lista encadeada, e o perigo real de mutar uma coleção enquanto um iterador a percorre.