Computer Science › Algoritmos e Software
A probabilidade de colisão entre n chaves em m slots depende de n² relativo a m, não de n relativo a m, então colisões se tornam prováveis com aproximadamente n ≈ √m chaves, muito antes da tabela estar perto de cheia.
Nenhuma função hash fixa resiste a um adversário que a conhece, então hashing universal sorteia uma função ao acaso de uma família com P(h(x)=h(y)) ≤ 1/m para todo par de chaves distintas, restaurando o desempenho esperado O(1) mesmo contra escolha adversarial de chaves.
A construção de dois níveis FKS usa um hash universal de primeiro nível para separar chaves em n buckets, e para cada bucket busca uma função de segundo nível dimensionada quadraticamente até achar uma sem colisões internas, dando O(1) de pior caso com espaço total esperado O(n), mas só para um conjunto de chaves estático e conhecido de antemão.
Um array de bits de tamanho m mais k funções hash independentes, sem nenhuma chave armazenada, dá falsos positivos possíveis mas falsos negativos estruturalmente impossíveis, uma troca de espaço independente do tamanho das chaves.
A taxa de falso positivo de um filtro de Bloom é aproximadamente (1 - e^(-kn/m))^k, minimizada em k = (m/n)·ln(2), o que dá uma taxa que encolhe exponencialmente conforme mais bits por elemento são alocados, transformando o dimensionamento do filtro em aritmética simples.
Uma trie soletra os caracteres de uma chave um por aresta ao longo de um caminho raiz-a-nó, forçando chaves que compartilham prefixo a compartilhar caminho; é o complemento natural da hash table, trocando lookup exato O(1) por operações de prefixo eficientes.
As três operações compartilham a caminhada caractere-por-caractere; insert e search custam O(L), sem vantagem sobre hash table, mas keysWithPrefix custa O(P) mais o tamanho do conjunto correspondente, independente de quantas outras chaves existam, a razão de existir de uma trie.
Um nó de TST tem exatamente três filhos (left/mid/right) organizados como uma mini-BST sobre o caractere atual, em vez de um slot por caractere do alfabeto; troca um fator O(log N) extra por busca por custo de memória por nó independente do tamanho do alfabeto.
Autocomplete é keysWithPrefix aplicado direto a cada tecla digitada; roteamento de IP é a mesma caminhada em trie, bit a bit, mas rastreando apenas o casamento mais específico ao longo do caminho, não a coleção inteira abaixo dele.
Union-find mantém uma partição de n elementos em grupos disjuntos com duas operações, union e find (connected deriva de find(a) == find(b)); sem split, uma restrição deliberada que viabiliza implementações rápidas, e é o motor por trás de Kruskal.
Quick-find dá find O(1) mas union O(n) (relabel de array inteiro); quick-union dá union O(1) mas find O(n) (corrente degenerada); nenhuma implementação faz escolha deliberada de como combinar grupos, o que union por rank/size resolve.
Anexar sempre a raiz da árvore menor sob a maior (por size ou rank) limita a altura de toda árvore a O(log n), porque cada aumento de profundidade exige que a árvore ao menos dobre de tamanho, o mesmo argumento de dobramento usado para amortizar arrays dinâmicos.
Compressão de caminho reponta todo nó visitado durante find diretamente para a raiz, achatando a árvore para toda consulta futura sem mudar o que nenhuma operação retorna ou exigir array extra; combinada com union por rank produz o famoso limite quase constante.
Union por rank combinado com compressão de caminho dá O(m α(n)) total para m operações, onde α é o inverso de Ackermann e nunca excede 4 ou 5 para qualquer n fisicamente realizável, tornando "essencialmente tempo constante" uma afirmação rigorosa e não uma aproximação.
A propriedade de max-heap exige apenas que o valor de todo nó seja ≥ cada um de seus filhos, uma restrição puramente local entre pai e filho; isso é exatamente suficiente para garantir acesso O(1) ao máximo, o que uma fila de prioridade precisa.
Uma árvore completa faz o filho de i corresponder a 2i+1/2i+2 e o pai a (i-1)//2, derivado de numeração em ordem de nível; isso usa exatamente n posições sem sobrecarga de ponteiro, mas só funciona porque um heap garante completude.
Inserir anexa no final e faz sift-up (mantém completude); extrair-máximo troca a raiz com o último elemento, encolhe, e faz sift-down (também mantém completude); ambas custam O(log n) porque só percorrem um único caminho limitado pela altura.
Sift-down conserta a propriedade de heap em um nó cujas subárvores já são heaps válidos; heapify de baixo para cima aplica isso do último nó não-folha até a raiz, e o argumento de soma-de-altura por série geométrica mostra que isso custa O(n), não O(n log n).
Heapsort tem duas fases: heapify o array inteiro em O(n), depois extraia o máximo repetidamente para o final do mesmo array em O(log n) cada; combina o total O(n log n) do merge sort com o perfil in-place do quicksort, ao custo de instabilidade e pior localidade de cache.
Um invariante de balanceamento é uma regra local, verificável e restaurável a cada inserção/remoção que força a altura de uma árvore a O(log n) independentemente da ordem de inserção; AVL e árvores rubro-negras são duas respostas diferentes à mesma pergunta de design.
O fator de balanceamento (diferença de altura esquerda-direita) deve ficar em {−1, 0, 1} em todo nó AVL; a contagem mínima de nós por altura segue a recorrência de Fibonacci, o que prova que a regra local força altura O(log n), aproximadamente 1,44·log₂n no pior caso.
Uma rotação reatribui um número fixo de ponteiros em O(1) sem mudar a sequência em ordem de valores; os quatro casos (LL, RR, LR, RL) são determinados pelo fator de balanceamento do nó desbalanceado e de seu filho mais alto, e no máximo uma rotação é necessária por inserção.
Quatro regras de cor (cada nó vermelho ou preto, raiz preta, sem filho vermelho de nó vermelho, mesma black-height em todo caminho) limitam a altura a 2·log₂(n+1); é o esquema real por trás de TreeMap/TreeSet do Java e std::map/std::set do C++.
AVL tem árvore mais curta mas remoção pode custar O(log n) rotações; rubro-negra tem árvore mais alta mas limita inserção e remoção a poucas rotações; cargas de leitura pesada favorecem AVL, cargas de escrita pesada ou imprevisíveis favorecem rubro-negra.
Uma hierarquia de listas encadeadas ordenadas, onde cada nível superior "pula" mais elementos que o nível abaixo, atinge O(log n) esperado sem invariante de balanceamento e sem rotações, trocando garantia de pior caso por uma garantia probabilística muito favorável.
Inserção e remoção reaproveitam a mesma passada descendente da busca, registrando em um array update o último nó visitado em cada nível, sem nenhuma fase de correção separada como rotação.
A probabilidade de um elemento alcançar o nível k é (1/2)^k, o que dá altura esperada Θ(log n) e custo de busca esperado O(log n), uma garantia sobre os lançamentos de moeda internos, não sobre a entrada, tornando o pior caso impossível de ser forçado por qualquer chamador.
Um guia comparativo das oito estruturas de Estruturas de Dados I e II, mostrando qual operação cada uma resolve melhor e como reconhecer, dado um problema real, qual estrutura combina com seu gargalo específico.
Part of the Computer Science curriculum.
A probabilidade de colisão entre n chaves em m slots depende de n² relativo a m, não de n relativo a m, então colisões se tornam prováveis com aproximadamente n ≈ √m chaves, muito antes da tabela estar perto de cheia.
Nenhuma função hash fixa resiste a um adversário que a conhece, então hashing universal sorteia uma função ao acaso de uma família com P(h(x)=h(y)) ≤ 1/m para todo par de chaves distintas, restaurando o desempenho esperado O(1) mesmo contra escolha adversarial de chaves.
A construção de dois níveis FKS usa um hash universal de primeiro nível para separar chaves em n buckets, e para cada bucket busca uma função de segundo nível dimensionada quadraticamente até achar uma sem colisões internas, dando O(1) de pior caso com espaço total esperado O(n), mas só para um conjunto de chaves estático e conhecido de antemão.
Um array de bits de tamanho m mais k funções hash independentes, sem nenhuma chave armazenada, dá falsos positivos possíveis mas falsos negativos estruturalmente impossíveis, uma troca de espaço independente do tamanho das chaves.
A taxa de falso positivo de um filtro de Bloom é aproximadamente (1 - e^(-kn/m))^k, minimizada em k = (m/n)·ln(2), o que dá uma taxa que encolhe exponencialmente conforme mais bits por elemento são alocados, transformando o dimensionamento do filtro em aritmética simples.
Uma trie soletra os caracteres de uma chave um por aresta ao longo de um caminho raiz-a-nó, forçando chaves que compartilham prefixo a compartilhar caminho; é o complemento natural da hash table, trocando lookup exato O(1) por operações de prefixo eficientes.
As três operações compartilham a caminhada caractere-por-caractere; insert e search custam O(L), sem vantagem sobre hash table, mas keysWithPrefix custa O(P) mais o tamanho do conjunto correspondente, independente de quantas outras chaves existam, a razão de existir de uma trie.
Um nó de TST tem exatamente três filhos (left/mid/right) organizados como uma mini-BST sobre o caractere atual, em vez de um slot por caractere do alfabeto; troca um fator O(log N) extra por busca por custo de memória por nó independente do tamanho do alfabeto.
Autocomplete é keysWithPrefix aplicado direto a cada tecla digitada; roteamento de IP é a mesma caminhada em trie, bit a bit, mas rastreando apenas o casamento mais específico ao longo do caminho, não a coleção inteira abaixo dele.
Union-find mantém uma partição de n elementos em grupos disjuntos com duas operações, union e find (connected deriva de find(a) == find(b)); sem split, uma restrição deliberada que viabiliza implementações rápidas, e é o motor por trás de Kruskal.
Quick-find dá find O(1) mas union O(n) (relabel de array inteiro); quick-union dá union O(1) mas find O(n) (corrente degenerada); nenhuma implementação faz escolha deliberada de como combinar grupos, o que union por rank/size resolve.
Anexar sempre a raiz da árvore menor sob a maior (por size ou rank) limita a altura de toda árvore a O(log n), porque cada aumento de profundidade exige que a árvore ao menos dobre de tamanho, o mesmo argumento de dobramento usado para amortizar arrays dinâmicos.
Compressão de caminho reponta todo nó visitado durante find diretamente para a raiz, achatando a árvore para toda consulta futura sem mudar o que nenhuma operação retorna ou exigir array extra; combinada com union por rank produz o famoso limite quase constante.
Union por rank combinado com compressão de caminho dá O(m α(n)) total para m operações, onde α é o inverso de Ackermann e nunca excede 4 ou 5 para qualquer n fisicamente realizável, tornando "essencialmente tempo constante" uma afirmação rigorosa e não uma aproximação.
A propriedade de max-heap exige apenas que o valor de todo nó seja ≥ cada um de seus filhos, uma restrição puramente local entre pai e filho; isso é exatamente suficiente para garantir acesso O(1) ao máximo, o que uma fila de prioridade precisa.
Uma árvore completa faz o filho de i corresponder a 2i+1/2i+2 e o pai a (i-1)//2, derivado de numeração em ordem de nível; isso usa exatamente n posições sem sobrecarga de ponteiro, mas só funciona porque um heap garante completude.
Inserir anexa no final e faz sift-up (mantém completude); extrair-máximo troca a raiz com o último elemento, encolhe, e faz sift-down (também mantém completude); ambas custam O(log n) porque só percorrem um único caminho limitado pela altura.
Sift-down conserta a propriedade de heap em um nó cujas subárvores já são heaps válidos; heapify de baixo para cima aplica isso do último nó não-folha até a raiz, e o argumento de soma-de-altura por série geométrica mostra que isso custa O(n), não O(n log n).
Heapsort tem duas fases: heapify o array inteiro em O(n), depois extraia o máximo repetidamente para o final do mesmo array em O(log n) cada; combina o total O(n log n) do merge sort com o perfil in-place do quicksort, ao custo de instabilidade e pior localidade de cache.
Um invariante de balanceamento é uma regra local, verificável e restaurável a cada inserção/remoção que força a altura de uma árvore a O(log n) independentemente da ordem de inserção; AVL e árvores rubro-negras são duas respostas diferentes à mesma pergunta de design.
O fator de balanceamento (diferença de altura esquerda-direita) deve ficar em {−1, 0, 1} em todo nó AVL; a contagem mínima de nós por altura segue a recorrência de Fibonacci, o que prova que a regra local força altura O(log n), aproximadamente 1,44·log₂n no pior caso.
Uma rotação reatribui um número fixo de ponteiros em O(1) sem mudar a sequência em ordem de valores; os quatro casos (LL, RR, LR, RL) são determinados pelo fator de balanceamento do nó desbalanceado e de seu filho mais alto, e no máximo uma rotação é necessária por inserção.
Quatro regras de cor (cada nó vermelho ou preto, raiz preta, sem filho vermelho de nó vermelho, mesma black-height em todo caminho) limitam a altura a 2·log₂(n+1); é o esquema real por trás de TreeMap/TreeSet do Java e std::map/std::set do C++.
AVL tem árvore mais curta mas remoção pode custar O(log n) rotações; rubro-negra tem árvore mais alta mas limita inserção e remoção a poucas rotações; cargas de leitura pesada favorecem AVL, cargas de escrita pesada ou imprevisíveis favorecem rubro-negra.
Uma hierarquia de listas encadeadas ordenadas, onde cada nível superior "pula" mais elementos que o nível abaixo, atinge O(log n) esperado sem invariante de balanceamento e sem rotações, trocando garantia de pior caso por uma garantia probabilística muito favorável.
Inserção e remoção reaproveitam a mesma passada descendente da busca, registrando em um array update o último nó visitado em cada nível, sem nenhuma fase de correção separada como rotação.
A probabilidade de um elemento alcançar o nível k é (1/2)^k, o que dá altura esperada Θ(log n) e custo de busca esperado O(log n), uma garantia sobre os lançamentos de moeda internos, não sobre a entrada, tornando o pior caso impossível de ser forçado por qualquer chamador.
Um guia comparativo das oito estruturas de Estruturas de Dados I e II, mostrando qual operação cada uma resolve melhor e como reconhecer, dado um problema real, qual estrutura combina com seu gargalo específico.